每天一道算法题

起手诗

从今天起，做一个牛X的人，早起，健身，修炼算法
从今天起，关心代码质量，我有一个梦想，朝九晚五，年薪百万
从今天起，和每一个亲人通信，告诉他们我的决心
那成功的天使告诉我的
我想告诉每一个人
给每一个文件、每一个变量取一个温暖的名字
陌生人，我也为你祝福
愿你有一个灿烂的前程
愿你的头发不再减少
愿你明天仍是公司栋梁
而我，只愿朝九晚五，年薪百万

第一天 【2018-04-12】

• 写一个函数判断一个括号表达式是否平衡，例如：
  balance('[()') = false,balance('[()()[]]') = true。

function balance(str) {
    let [first, ...others] = str;
    let stack = [first]
    while(others.length) {
        let stact_last = stack[stack.length-1];
        let others_first = others.shift();
        if(!if_match(stact_last,others_first) {
            stack.push(others_first);
        }else{
            stack.pop();
        }
        return stack.length?false:true;
    }
}
function if_match(left,right) {
  return (left === '[' && right === ']') || (left === '(' && right === ')');
}

思路：
这个解法基于栈(后进先出)。首先，如果只有一个字符，则必然不平衡。
如果大于一个字符。我们把字符串中的每一个字符取出并依次放入栈中，假如最新放入栈中的字符与栈的最后一个字符匹配(match方法返回true)，则删掉栈中的最后一个。
就这样把字符串循环一遍后，如果栈中的字符被删光，则说明这个字符串是平衡的。

如图，我们可以把它想象成“消消乐”，字符串中的字符依次放到栈中,如果相邻两个不匹配，则放在栈的顶端；如果匹配，则“消掉”。

第二天 【2018-04-16】

• 实现一个斐波那契数列生成函数，fibonacci(10) = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

递归解法:
斐波那契数列的前两项是1,后面的每一项都等于前两项之和，所以用递归很容易实现，不过需要注意性能问题。
如果直接递归的话会出现大量重复计算，试想递归数字10的时候会依次递归数字9、8、7、6……，但是当再递归数字9的时候会在递归数字8、7、6……，其中8、7、6……被多次递归。所以声明了一个 catch 数组用来缓存，递归之前判断如果该项没有值才会进行递归。

function fibonacciCatch(num) {
    let cache = [1, 1];
    (function fibonacci(n) {
        return typeof cache[n] == 'number' ? cache[n] : (cache[n] = fibonacci(n - 1) + fibonacci(n - 2))
    })(num - 1);
    return cache;
}
console.log(fibonacciCatch(10))   //[ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ]

Generator解法:
下面是另一种解法，这种解法不存在多次计算问题，思路是：
首先记录前两个值，之后的每一个yeild都返回前两个值之和，当然还要更新前两个值为最新的。
对generator不了解的同学可以参考阮一峰老师的书籍：es6入门-generator

function* fibonacci(){
  let [a,b]=[1,1]
  yield a
  yield b
  while (true){
    let c = a+b
    a=b
    b=c
    yield c
  }
}
let instance = fibonacci()
let r = Array.from(Array(10),instance.next,instance).map(x=>x.value)
console.log(r) //[ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ]

飞机票：Array.from定义

飞机票：Array.map定义

第三天 【2018-04-19】

• 写一个方法，求任意长度数组的笛卡尔积。例如：
  cartesian([[1,2],['a','b']]) = [[1,'a'],[1,'b'],[2,'a'],[2,'b']]

笛卡尔乘积是指在数学中，两个集合X和Y的笛卡尓积(Cartesianproduct)又称直积，表示为X×Y，第一个对象是X的成员而第二个对象是Y的所有可能有序对的其中一个成员

function cartesion(...arys) {
    if (arys.length == 0) return []
    if (arys.length == 1) return arys
    return arys.reduce((prev, item) => {
        let t = []
        for (let i of prev) {
            for (let j of item) {
                t.push(Array.isArray(i) ? [...i, j] : [i, j])
            }
        }
        return t
    })
}
console.log(cartesion([1, 2, 3], ['a', 'b'], ['x', 'y']))
// [[1, 'a', 'x'],[1, 'a', 'y'],[1, 'b', 'x'],[1, 'b', 'y'],[2, 'a', 'x'],[2, 'a', 'y'],
// [2, 'b', 'x'],[2, 'b', 'y'],[3, 'a', 'x'],[3, 'a', 'y'],[3, 'b', 'x'],[3, 'b', 'y']]

思路：
这道题主要是训练 reduce 的用法，我们依次组合两个数组中的每一项，然后把结果作为一个整体继续和接下来的数组进行组合。
这里还需要注意es6扩展符 ... 的用法，大家可以把这个符号去掉再执行一遍程序，看看有什么不同。

飞机票：Array.prototype.reduce

第四天 【2018-04-21】

假设有一个数组，它的第 i 个元素是一个给定的股票在第 i 天的价格。设计一个算法来找到最大的利润。你可以完成尽可能多的交易（多次买卖股票）。然而，你不能同时参与多个交易（你必须在再次购买前出售股票）。

var maxProfit = function (prices) {
    if (!prices.length) return 0 //越界判断
    var max = 0
    for (var i = 0; i < prices.length; i++) {
        var diff = prices[i] - prices[i - 1]
        if (diff > 0) {
            max += diff
        }
    }
    return max
};

思路是：
1、声明一个 max 记录利润
2、从第二项开始循环数组，判断明天的价格是否高于今天
3、如果高于前一天，为了利润最大，今天应该买入，所以最大利润 max 增加相应的差价

原文地址，侵删哈