前端算法-1

2.1 树 找到某节点的路径

参考答案：

查找某个节点的路径的方法通常有两种，一种是递归算法,另一种是非递归算法

定义树节点

// 树节点定义
class TreeNode{
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

构建树

// 构建树
let root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

递归算法

// 递归中序遍历二叉树
function midOrder(root) { 
    if(!root || !(root instanceof TreeNode)){
        return;
    }
    // 递归访问左子树
    midOrder(root.left);
    console.log(root.value);
    // 递归访问右子树
    midOrder(root.right);
}
midOrder(root);

非递归算法

// 非递归中序遍历二叉树
function midOrderN(root) { 
    let p = root; // p为当前遍历的节点， 初始为根
    let arr = []; // arr作为栈
    while(p || arr.length !== 0){
        if(p){
            // 遍历左子树
            arr.push(p);
            // 每遇到非空二叉树先向做走
            p = p.left;
        }else{
            // p为空，出栈
            let node = arr.pop();
            // 访问该节点
            console.log(node.value);
            // 向右走一次
            p = node.right;
        }
    }
 }
 midOrderN(root)

2.2 洗完牌抽5张判断是否为同花顺

参考答案：

题目：从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2-10为数字本身，A为1，J为11，Q为12，K为13，而大小王可以看成任意数字。

思路一:

我们需要把扑克牌的背景抽象成计算机语言。不难想象，我们可以把5张牌看成由5个数字组成的数组。大小王是特殊的数字，我们不妨把它们都当成0，这样和其他扑克牌代表的数字就不重复了。接下来我们来分析怎样判断5个数字是不是连续的。最直观的是，我们把数组排序。但值得注意的是，由于0可以当成任意数字，我们可以用0去补满数组中的空缺。也就是排序之后的数组不是连续的，即相邻的两个数字相隔若干个数字，但如果我们有足够的0可以补满这两个数字的空缺，这个数组实际上还是连续的。举个例子，数组排序之后为{0，1，3，4，5}。在1和3之间空缺了一个2，刚好我们有一个0，也就是我们可以它当成2去填补这个空缺。于是我们需要做三件事情：把数组排序，统计数组中0的个数，统计排序之后的数组相邻数字之间的空缺总数。如果空缺的总数小于或者等于0的个数，那么这个数组就是连续的；反之则不连续。最后，我们还需要注意的是，如果数组中的非0数字重复出现，则该数组不是连续的。换成扑克牌的描述方式，就是如果一副牌里含有对子，则不可能是顺子。

思路二:

1）确认5张牌中除了0，其余数字没有重复的（可以用表统计的方法）;

2) 满足这样的逻辑：（max，min分别代表5张牌中的除0以外的最大值最小值）

​ 如果没有0，则max-min=4，则为顺子，否则不是

​ 如果有一个0，则max-min=4或者3，则为顺子，否则不是

​ 如果有两个0，则max-min=4或者3或者2，则为顺子，否则不是最大值和最小值在1）中就可以获得，这样就 不用排序了

2.3 爬楼梯 编代码

参考答案：

题目描述：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

方法分析：

这道题主要是要明白该爬楼梯的规律其实就是符合斐波那契数列（Fibonacci Sequence） 规律的，问题就迎刃而解了。为什么说它是斐波那契数列呢？我们可以这样来思考：当我们从第 n-1 阶楼梯爬到第 n 阶楼梯时，需要1步；当我们从第 n-2 阶楼梯爬到第 n 阶楼梯时，需要2步.也就是说 到达第 n 阶楼梯的方法数等于到达第 n-1 阶楼梯的方法数加上到达第 n-2 阶楼梯的方法数，其正好符合斐波那契通项。

代码实现：

1. 采用递归实现

var climbStairs = function(n) {
    if(n == 1) return 1;
    if(n == 2) return 2;
    return climbStairs(n-1) + climbStairs(n-2);
};

递归是求解斐波那契数列最经典和最直接的方式，其简洁易懂；但是递归特别费时，在该题中使用会出现[超出时间限制]的错误提示。

2. 数组方式

var climbStairs = function(n) {
    let result = [1,2];
    for (let i = 2; i < n; i++) {
        result.push(result[i-1] + result[i-2]);
    }
    return result[n-1];
};

数组方式大大的减少了运行时间，我们先预设好前两项，再得到结果，返回数组最后一项即可。

3. ES6的方式

var climbStairs = function(n) {
    let a = b = 1;
    for (let i = 0; i < n; i++) {
        [a, b] = [b, a + b];
    }
    return a;
};

其中 [a, b] = [b, a + b] 表示解构赋值，其等价于

temp = a;
a = b;
b = temp + b;

2.4 怎么识别100枚硬币中的假币

参考答案：

问题描述：
在n枚外观相同的硬币中，有一枚是假币，并且已知假币与真币的重量不同，但不知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币，设计一个高效的算法来检测这枚假币(以下提供两种方法)。
解题思路1 (本例为真币重量大于假币)：
使用减治法的解题思路，将硬币分为3堆，则每堆的硬币数量为 n/3 ，但是这是在 n%3==0 的情况下才能成立，所以我们将 n 枚硬币分为 3 堆加 1 堆 余数堆(余数堆可能为0)，则可分为如下(n-n%3)/3, (n-n%3)/3, (n-n%3)/3, n%3。
如下分组：
a堆： (n-n%3)/3
b堆： (n-n%3)/3
c堆： (n-n%3)/3
d(余数堆): n%3
逻辑流程：

1. 判断n中的硬币数量，如果n>2则执行2，否则执行5.
2. 将n分为上图的四堆，拿 a 和 b 比较，如果 a == b ,则 假币在 c 或 d 中。否则假币在 a 或 b 中。
3. 如果 a == b，则拿 a 和 c 比较。如果 a == c,则假币在d(余数堆)中。将 d 再次 执行流程1，并且n=n%3。如果不等，则假币在 c 中，将 c 再次 执行流程1，并且n=(n-n%3)/3。
4. 如果 a != b，则拿 a 和 c 比较。如果 a == c,则假币在b中，将 b 再次 执行流程1，并且n=(n-n%3)/3。如果不等，则假币在 a 中，将 a 再次 执行流程 1，并且n=(n-n%3)/3。
5. 如果n==2