转型程序员freecodecamp高级算法题(个人解法)

刚刚开始自学,网上很多相关帖子上来直接报上两页菜名,初一看很有武侠小说里说书人的感觉.这本书怎样怎样,那本书如何如何(本人文笔不行,可以自行脑补网络小说各类比武桥段中龙套发言)。转了一圈下来,各类电子书下了不少,收藏夹也增长了几页。
  真正学起来,才发现需要一个好的学习路径和对应的代码练习。其中代码练习尤其地少。有人也许会说,那么多代码书,自己跟着敲一敲不就是练习么,这还学不会?刷题网站那么多,自己去刷题啊!
  我打个比方,咱们都学过数学。除了那种看一看教材解释,就能完美理解的天才;两个普通学生,一个学习完数学定义及公式后,自己出题给自己做;一个则做各类教辅习题,这两种情境下,学习效率绝对是天差地别的。再者,刷题网站的题目默认刷题者对语言已经学习完毕,重点在于对计算机原理及数学的应用。
  综上,个人感觉freecodecamp对我这种半路自学的人还是有不少帮助的。花了一段时间,按照它给的学习顺序,从新手教程一直做到了高级算法题结束。在这里自己回顾一下之前自己的解法。

Validate US Telephone Numbers

检查是否是美国电话号码。其中有很多变体写法,也要求返回正确。

function telephoneCheck(str) {
    var a = str.match(/[0-9]/g).length;
    var b = str.match(/^(?:(?:\(\d{3}\)|\d{3})[\s|-]?\d{3}[\s|-]?\d{4}$)/);
    var c = str.match(/(?:\(\d{3}\)|\d{3})[\s|-]?\d{3}[\s|-]?\d{4}$/);
    var d = str.match(/^1[^0-9]/);
    if (a === 10 && b !== null) {
        return true;
    } else if (a === 11 && c !== null && d !== null) {
        return true;
    }
    return false;
}
telephoneCheck("2 757 622-7382");

本来尝试使用一个正则直接得出结果,很可惜受限于水平原因,最后放弃了尝试。
  最后的代码里面,通过a检查传入字符串中有多少个数字,在后面的if条件判断中,分两种情况(是否带有国家代码)来判断。
  值b用来匹配不带国家代码的电话号码,前面的部分较后面来说比较复杂。需要匹配三个数字及三个数字加括号这两种情况,但一边单括号应当不能通过验证。(?:(\d{3})|\d{3})这里,使用(?:)非捕获括号,里面用 | 做了一个条件判断,从而达到匹配三个数字或三个数字加括号这两种情况。前面的用来防止匹配到带国家代码的电话(如果把b匹配放入if内,可以去掉这个,因为已经通过a的数值判断了是否带国家代码)。
  值c和值b没什么区别。
  值d用来匹配国家代码开头部分(应该可以和c合并,当时只为通关也就没改了)。

Symmetric Difference

接受两个或者多个数组。如果是两个数组,互相判定差集,把结果作为一个集合输出。如果是多个数组,用上一次的结果作为其中一个数组,和下一个做相同的操作(就是reduce啦)。

function sym1(a, b) {
    var c = [];
    for (var i in a) {
        if (b.indexOf(a[i]) === -1) {
            c.push(a[i]);
        }
    }
    for (var y in b) {
        if (a.indexOf(b[y]) === -1) {
            c.push(b[y]);
        }
    }
    return c;
}
function sym(args) {
    var d = [];
    for (var i in arguments) {
        d.push(arguments[i]);
    }
    var e = d.reduce(sym1);
    var f = [e[0]];
    for (var i = 1; i < e.length; i++) {
        if (e[i] !== e[i - 1]) {
            f.push(e[i]);
        }
    }
    return f;
}

sym([1, 2, 3], [5, 2, 1, 4]);

先写了一个reduce用的函数smy1。用indexOf判断元素是否在集合中,如果不存在就放入准备好的结果容器c中。
  接下来在主函数中用for循环arguments取出输入的所有数组,再使用reduce依次对等差分。注意这时如果输入的数组中有多个重复的值,而这个值满足差分的要求,结果的数组中也会出现很多个相同的值。但是网站左侧给出的例子要求我们不能出现重复,因此用一个for循环进行去重。

Exact Change

写一个收银程序。

function checkCashRegister(price, cash, cid) {
    var change;
    var a = 0;
    var b = [];
    var e = cash - price;
    var d = [0.01, 0.05, 0.10, 0.25, 1, 5, 10, 20, 100];
    for (var i in cid) {
        a += cid[i][1];
    }
    if ((cash - price) > a) {
        return 'Insufficient Funds';
    } else if ((cash - price) === a) {
        return 'Closed';
    }
    for (var i = d.length - 1; i >= 0; i--) {
        if (i === 0 && e <= cid[i][1]) {
            b.push([cid[i][0], Math.round(e * 100) / 100]);
            e = 0;
        } else if (e >= d[i] && e <= cid[i][1] && cid[i][1] > 0) {
            b.push([cid[i][0], Math.floor(e / d[i]) * d[i]]);
            e = e - Math.floor(e / d[i]) * d[i];
        } else if (e >= d[i] && e >= cid[i][1] && cid[i][1] > 0) {
            b.push(cid[i]);
            e = e - cid[i][1];
        }
        if (e === 0) {
            break;
        }
    }
    if (e !== 0) {
        return 'Insufficient Funds';
    }

    return b;
}

sym([1, 2, 3], [5, 2, 1, 4]);

第一个for循环不用看,出现的原因只是代码通过了就没改。
  第二个for循环是核心代码。我的思路是用for循环对大面额到小面额依次进行判断。每次会操作两个变量,一个是结果容器b(push进一个列表,包含面额,和剩余金额),一个是e(初始量是待找金额,每次循环如果面额和余额满足要求,从e中扣除一定的钱)。如果循环中出现e=0的情况,用break语句跳出,因为此时找零已经完成。如果直到循环结束,e仍有剩余,说明钱找不开。 
  感觉代码还是乱,有修改的余地。

Inventory Update

依照一个存着新进货物的二维数组,更新存着现有库存(在 arr1 中)的二维数组. 如果货物已存在则更新数量 . 如果没有对应货物则把其加入到数组中,更新最新的数量. 返回当前的库存数组,且按货物名称的字母顺序排列。

function updateInventory(arr1, arr2) {
    var a = [];
    for (var i in arr1) {
        a.push(arr1[i][1]);
    }
    for (var i in arr2) {
        if (a.indexOf(arr2[i][1]) !== -1) {
            arr1[a.indexOf(arr2[i][1])][0] += arr2[i][0];
        } else {
            arr1.push(arr2[i]);
        }
    }
    arr1 = arr1.sort(function(a, b) {
        return a[1].charCodeAt(0) - b[1].charCodeAt(0);
    });
    return arr1;
}

用for循环遍历进货,用indexOf判断进货中货物名称是否已经在库存中存在,如果存在就更新货物数量,不存在则直接把这个数组加入库存。
  按货物名称排序我直接用在sort内写了一个匿名函数,通过比较字母的ASCII大小排序。

No repeats please

把一个字符串中的字符重新排列生成新的字符串,返回新生成的字符串里没有连续重复字符的字符串个数.连续重复只以单个字符为准
  例如, aab 应该返回 2 因为它总共有6中排列 (aab, aab, aba, aba, baa, baa), 但是只有两个 (aba and aba)没有连续重复的字符 (在本例中是 a).

function perms(str) {
    var result = [];
    var n = 0;
    var m = str.length;
    var perm = function(str, n, m) {
        if (n === m - 1) {
            result.push(str.join(''));
        } else {
            for (var i = n; i < m; i++) {
                str[i] = [str[n], str[n] = str[i]][0];
                perm(str, n + 1, m);
                str[i] = [str[n], str[n] = str[i]][0];
            }
        }
    };
    perm(str, n, m);
    return result;
}
function permAlone(str) {
    var regex = /(.)\1+/g;
    str = str.split('');
    var b = perms(str);
    var filter = b.filter(function(a) {
        return ! a.match(regex);
    });
    return filter.length;
}

一开始当成一个数学题来做,想了很久,发现其中要判断的情况太多,写出代码要很多条件判断。最后还是用全排列做了。
  我的全排列函数perms是用递归做的。思路是,有一个可用字符集合,取出其中一个,放在首位,接着更新这个字符集(集合中去除这个放在首位的字符),接着在新字符集中取出其中一个……不断循环直至其中只有一个字符。在写代码的时候变了一下实现方式,变成首字符和它后面的每一个字符依次交换,第二个字符和它后面的每一个字符依次交换,直至递归出口(倒数第二个字符)。
  注意里面的匿名函数里的闭包情况(递归中每一次重新调用自身,并没有创建一个新的变量,它们都在操作同一个str,n,m。所以交换完了要再把str还原。递归出口是把此时的str组装成一个字符串。这个操作不仅有输出格式上的考量,还有一个原因是,既然操作的都是同一个str,那么push进数组的当然也是同一个str,虽然它们身处数组,但一直在随着函数里的str的变化而变化。所以我们需要把每次递归出口的str顺序固定下来,组装字符串相当于创建了一个新的字符串对象,从而达到固定顺序的作用)。

Friendly Date Ranges

function makeDates(str) {
    var arr = [];
    str = str.split(/[^\d*]/);
    for (var i in str) {
        arr.push(parseInt(str[i], 10));
    }
    return arr;
}

function makeFriendlyDates(arr) {
    var month = ['', 'January', 'February', 'March', 'April', 'May', 'June', 'July', 'August', 'September', 'October', 'November', 'December'];
    var days = [];
    var array = [];
    for (var z = 0; z < 31; z++) {
        if (z >= 10 && z <= 20) {
            days.push('th');
        } else {
            if (z % 10 === 1) {
                days.push('st');
            } else if (z % 10 === 2) {
                days.push('nd');
            } else if (z % 10 === 3) {
                days.push('rd');
            } else {
                days.push('th');
            }
        }
    }
    for (var i in arr) {
        array.push(makeDates(arr[i]));
    }
    var a = array[1][0] - array[0][0];
    var b = array[1][1] - array[0][1];
    var c = array[1][2] - array[0][2];
    for (var y in array) {
        array[y][0] = [array[y][2], array[y][2] = array[y][0]][0];
        array[y][0] = [array[y][1], array[y][1] = array[y][0]][0];
        replace(array[y]);
    }
    function replace(array) {
        array[0] = month[array[0]];
        array[1] = String(array[1]) + days[array[1]];
        array[2] = String(array[2]);
        if (array.length === 3) {
            array[1] = array[1] + ',';
        }
    }
    if (a * 360 + b * 30 + c >= 360) {} else if (a * 360 + b * 30 + c > 30 && array[0][2] === '2016') {
        array[1] = array[1].splice(0, 2);
        array[0] = array[0].splice(0, 2);
    } else if (a * 360 + b * 30 + c > 30) {
        array[1] = array[1].splice(0, 2);
        array[0] = array[0].splice(0, 3);
    } else if (a * 360 + b * 30 + c > 0) {
        array[1] = [array[1][1]];
        array[0] = array[0].splice(0, 2);
    } else if (a === 0 && b === 0 && c === 0) {
        array = [array[0]];
    }
    return array.map(function(a) {
        return a.join(' ').replace(/,$/, '');
    });
}

把一大堆条件判断从人类语言转换成代码。。。。。。。这就是我写这题的感觉,也许出题人的初衷不是这个?

Make a Person

var Person = function(name) {
    var a = [name.split(' ')[0], name.split(' ')[1]];
    this.getFirstName = function() {
        return a[0];
    };
    this.getLastName = function() {
        return a[1];
    };
    this.getFullName = function() {
        return a[0] + ' ' + a[1];
    };
    this.setFirstName = function(b) {
        a[0] = b;
    };
    this.setLastName = function(b) {
        a[1] = b;
    };
    this.setFullName = function(b) {
        a[0] = b.split(' ')[0];
        a[1] = b.split(' ')[1];
    };
};
var bob = new Person('Bob Ross');
bob.getFirstName();

匿名函数function(name)在类建立时就被调用,它用来建立一个类空间,其中的内容即是建立的类的内容。变量a用一个数组来储存和修改Firstname及Lastname(把function(name)传递进类空间的name给spilt成两块),给属性赋予匿名函数,通过闭包操作变量a。这六个函数大同小异,精简成一个的话,会非常简洁,同时可以清晰地看到两个要点。第一是通过函数建立类,第二是闭包的使用。

Map the Debris

返回一个数组,其内容是把原数组中对应元素的平均海拔转换成其对应的轨道周期.

function orbitalPeriod(arr) {
    var GM = 398600.4418;
    var earthRadius = 6367.4447;
    function change(avgAlt) {
        var r = earthRadius + avgAlt;
        var b = Math.pow(r, 3) / GM;
        var T = 2 * Math.PI * Math.pow(b, 0.5);
        return Math.round(T);
    }
    var result = [];
    for (var i in arr) {
        var a = change(arr[i].avgAlt);
        var dict = {};
        dict.name = arr[i].name;
        dict.orbitalPeriod = a;
        result.push(dict);
    }
    return result;
}

用代码把数学公式算一下。外加一点点数据的取出。不太清楚为什么要放在高级算法里。

Pairwise

举个例子:有一个能力数组[7,9,11,13,15],按照最佳组合值为20来计算,只有7+13和9+11两种组合。而7在数组的索引为0,13在数组的索引为3,9在数组的索引为1,11在数组的索引为2。
所以我们说函数:pairwise([7,9,11,13,15],20) 的返回值应该是0+3+1+2的和,即6。

function pairwise(arr, arg) {
  var count=0;
  var red=[];
  for(var i=0;i<arr.length;i++){
    for(var y=i+1;y<arr.length;y++){
      if(red.indexOf(i)!==-1||red.indexOf(y)!==-1){
        continue;
      }
      else if(arr[i]+arr[y]===arg){
        count+=i;
        count+=y;
        red.push(i);
        red.push(y);
      }
    }
  }
  return count;
}

题目下面的提示是reduce,我的思路里面没有用到,自己尝试用reduce想了一下,感觉有点阻力。
  我的思路,遍历每个值,每次遍历中再对目前值之后的值进行一次遍历。目的是每个值和它之后所有的值匹配,如果它们的和等于目标值,则把下标累加到变量count上。题目中还有一个值得注意的点,就是当两个值匹配后,它们便不会和其他值匹配了。这里我通过一个变量red,作为一个池子,来储存已经匹配过的变量的下标。再循环中先进行条件判断,若取出的值不在池中才进行下一步匹配(使用continue来实现,continue:跳过次循环直接执行下一次循环,也可以使用一个if,判断条件里用&&把“求和是否满足要求”及“下标是否在池中”连起来)。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 202,802评论 5 476
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,109评论 2 379
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 149,683评论 0 335
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,458评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,452评论 5 364
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,505评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,901评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,550评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,763评论 1 296
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,556评论 2 319
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,629评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,330评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,898评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,897评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,140评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,807评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,339评论 2 342

推荐阅读更多精彩内容