LeetCode总结

LeetCode笔记

二叉树

递归

如果从根节点向下进行需要递归一次，若将左右子树作为根节点再向下进行，需要两次递归。一般递归写成单独的函数

递归二部曲：

1.写终止递归条件：if(!root) return null/0;

2.写递归式和递归条件：**先写递归式代表自底向上执行(有return返回值)，后写递归式代表自顶向下执行

1.二叉树最大深度(树的高度)*

Alt text

1
2
3
4
5
var maxDepth = function(root) {
    if(!root) return 0;
    return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;   //返回的是数值，每次调用加一行
};
//O(n)/O(Height),时间复杂度看节点数，空间复杂度看树的高度，一般为O(n)，单支树；

2.平衡二叉树

Alt text

求一个结点的最大深度本来就要遍历整个结点并求出左右子树的深度，用一个全局的变量看有没有一个结点让flag变成false即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var isBalanced = function (root) {
    //后序遍历二叉树（左右根），从底至顶返回子树最大高度
    var flag = true;

    var isBalancedHelper = function (root) {
        if (!root) return 0;
        let l = isBalancedHelper(root.left);  //树的左子树高度
        let r = isBalancedHelper(root.right);
        if (Math.abs(l - r) > 1) flag = false;//若不平衡，赋为false****
        return Math.max(l,r) + 1;   //若左右子树平衡，返回当前树的深度，使用它们的高度判断父节点是否平衡
    }

    isBalancedHelper(root);
    return flag;
};
//O(n)/O(n)
谨记：1.在求树高的函数内，同时做判断，不能先写求树高函数，再在外面判断，那只是左右各调用一次，求的是左子树高度和右子树高度。2.***必须用flag承接，因为若是在isBalancedHelper函数内直接return，结束的是isBalancedHelper函数，不影响外面函数的返回值，所以外面函数若写死return：true，无论结果如何，都返回true。***面试时犯的错误

3. 二叉树的直径x-543

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//就是递归求左右子树高度加和的最大值，看自己方法好些
var diameterOfBinaryTree = function(root) {
    let ans = 1;
    function getDepth(rootNode){
    if(!rootNode) return 0;
    let l = getDepth(rootNode.left);
    let r = getDepth(rootNode.right);
    ans = Math.max(ans,l + r + 1);  //左节点高度+右节点高度+1(根节点)=总路径
    return Math.max(l,r) + 1;
}
    getDepth(root);
    return ans - 1;
};
**************************************************************************************
我的方法：
var diameterOfBinaryTree = function (root) {
    if (!root) return 0
    var deepTree = function (root) {   //求树的深度
        if (!root) return 0;
        return Math.max(deepTree(root.left), deepTree(root.right)) + 1;
    }
    var temp = deepTree(root.left) + deepTree(root.right)  //求除根节点的左分支、右分支高度
    //对每个节点都进行高度汇总，取最大值。求最大值时类似12，要把上一次求得的值放里比较（temp）
    return Math.max(temp, diameterOfBinaryTree(root.left), diameterOfBinaryTree(root.right))
    };
 //O(N)/O(Height)，其中N为二叉树的节点数,Height为树高度；

思路其实和上一个求平衡二叉树的相同，都是在求最大深度的过程中更新一个全局变量。

4. 翻转二叉树-226*

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 var invertTree = function(root) {
    if(!root) return null;
    [root.left,root.right] = [invertTree(root.right), invertTree(root.left)];
    return root;
};
*********************************************************************************************
我的方法：
var invertTree = function (root) {
    if (!root) return null;  //就算说树非空，后面要是用到root.left或root.right，还是要判断，也是递归边界
    let temp =  invertTree(root.right);  //从下往上遍历的，也可以从上往下，就是交换节点
    root.right = invertTree(root.left);
    root.left = temp
    return root
};
//O(n)/O(n),N为二叉树节点的数目。我们会遍历二叉树中的每一个节点，并在常数时间内交换其两棵子树。空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。在平均情况下，二叉树的高度与节点个数为对数关系，即O(logN)。而在最坏情况下，树形成链状，空间复杂度为 O(N)。

递归
目的或返回值：输入一个root为根的树，返回一个以root为根的对称树
递归式：左子树 = 以右子树为根的对称右子树
右子树 = 以左子树为根的对称左子树
递归边界： root为空直接返回

5.合并二叉树-617

Alt text

递归
目的：输入一个root1,root2,返回一个以root1为根的合并树
递归逻辑：root1.val += root2.val
递归式：左子树.left = 输入一个root1.left,root2.left，返回一个以root1.left为根的合并树
右子树相同
递归边界： root1若为空则返回root2
root2若为空则返回root1(正好与递归边界有所重叠)

执行从上至下，每次递归会生成新的值，不仅仅是完成操作，所以要承接

1
2
3
4
5
6
7
8
9
10
var mergeTrees = function(t1, t2) {
    if(t1 === null) return t2;
    if(t2 === null) return t1;
    t1.val = t1.val + t2.val;   //val代表树的值，递归条件
    t1.left = mergeTrees(t1.left,t2.left);
    t1.right = mergeTrees(t1.right,t2.right);
    return t1;
}
//O(min(m,n))/O(min(m,n))，其中m和n分别是两个二叉树的节点个数;空间：递归调用的层数不会超过较小的二叉树的最大高度，最坏情况下，二叉树的高度等于节点数。
//注：递归条件有返回值时，直接左右递归即可，没有返回值时，用左右节点承接。

6.路径总和-112**

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
var hasPathSum = function(root, sum) {
        if(root === null){   //等同于if(!root){}
            return false;
        }
        sum -= root.val;
        if(sum === 0 && !root.left && !root.right) return true;
        return hasPathSum(root.left,sum) || hasPathSum(root.right,sum);
       //此处要加‘或’符号，因为顺序调用hasPathSum(root.left,sum)/(root.right,sum)时，虽遍历全树，其实判断的只是最后一次调用hasPathSum(root.right,sum)的值，5-8-4-1，返回false，但我们只要一次true就行，所以要用||取值
};
//O(n)/O(Height),空间复杂度取决于空间栈的开销，最坏不超过O(n)
*************************************************************************************
**leetcode-113求路径总和II**，要求输出满足条件的路径，存放在数组中，nums.slice()不是很懂。
var pathSum = function (root, targetSum) {
    if (!root) return [];
    let res = [];  //1. 设置结果集
    let nums=[];   //2. 存放路径
    let dfs = function (node, sum) {
        if (!node) return [];  //3. 终止递归条件
        sum -= node.val;
        nums.push(node.val);
        if (!node.left && !node.right && sum === 0) {
            res.push(nums.slice());  //重点***需要赋新数组
        }
        dfs(node.left, sum);
        dfs(node.right, sum);
        nums.pop();   //剪枝操作，遍历到叶节点，不满足时，逐层向上剪枝
    }
    dfs(root, targetSum);
    return res;
};

目的：输入一个root,sum,判断能否以该结点为根…
递归逻辑：sum - root.val是否等于0该结点为叶子结点，若为0则返回true
递归式：若sum已经小于0则不用递归，否则对左右子树进行递归
递归边界： root 为空
注意sum可以为负值，所以不能用sum<0来结束递归

7. 路径总和 IIIx-437

Alt text

我的方法：

找所有满足条件的路径，用两个函数递归就可以遍历所有结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var pathSum = function (root, sum) {
    var ans = 0;
    var pathSumHelper = function (root, sum) {
        if (!root) {  //终止递归条件
            return;
        }
        sum -= root.val;
        if (sum === 0) {
            ans += 1;
        }
        pathSumHelper(root.left, sum);
        pathSumHelper(root.right, sum);
    }
    var traverse = function (root, sum) {
        if (!root) return;
        pathSumHelper(root, sum);  //从根节点向下找
        traverse(root.left, sum);  //改变根节点位置，第二次递归遍历
        traverse(root.right, sum);
    }
    <<<<<//pathSumHelper(root, sum);  //为啥不能这么写，因为调用总函数的话，每次ans会重置，所以另写traverse
    <<<<<//pathSum(root.left, sum);
    <<<<<//pathSum(root.right, sum);
    traverse(root, sum);  //也可以使用主函数本身递归
    return ans;
};

思路与上一个题类似，上一题必须从根节点开始向下求值，本题可从任一节点向下求值，所以第二次递归遍历是改变根节点位置。

另外一种：

1
2
3
4
5
6
7
8
9
10
11
12
var pathSum = function (root, sum) {
    function pathSumHelper(root, sum) {//以一个结点为根有多少连续的路径可以得到这个sum
        if (!root) return 0;//注意这里的递归边界
        let res = 0;
        if (root.val === sum) res++;
        res += pathSumHelper(root.left, sum - root.val) + pathSumHelper(root.right, sum - root.val);
        return res;
    }
    if (!root) return 0;
    let ans = pathSumHelper(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    return ans;
};

其实原理都一样，但是这种写法其实更好的体现了递归的思想，一定要注意这种拿到递归的返回结果返回给一个变量的方法

8.另一个树的子树xx-572

Alt text

不熟，把功能分成两层，一层为判断两个树是否相等(从根节点开始)，另外一层对树的结点进行遍历(转移到左右节点)

1
2
3
4
5
6
7
8
9
10
11
12
var isSubtree = function (s, t) {
    function isEqual(s,t){
      if(!s && !t) return true;    //后面要用到s.left和t.left/right，所以此处要判断是否为空
      if(!s || !t)return false;
      if(s.val === t.val) return isEqual(s.left,t.left) && isEqual(s.right,t.right);//左右要一起判断，如果分别递归，就是先左子树后右子树。
      else return false;
    }
    if (!s) return false;    //同上面因为只用到s，对s判断，也是终止条件
    if (isEqual(s,t)) return true;
    else return isSubtree(s.left, t) || isSubtree(s.right, t); //此处是从根节点移到左右节点继续判断
};
//O(m*n),O(max(d1,d2)),m和n是s和t的节点数，d1和d2是

9.对称二叉树xx-剑指28

Alt text

和上题类似：创新点在于“将除根节点之外的左右子树当成两棵树比较”和递归传参“(s.left，t.right)”

1
2
3
4
5
6
7
8
9
10
var isSymmetric = function(root) {
            function isSymmetricHelper(s,t){  //将除根节点之外的左右子树当成两棵树比较
            if(!s && !t) return true;
            if(!s || !t)return false;
            if(s.val === t.val) return isSymmetricHelper(s.left,t.right) && isSymmetricHelper(s.right,t.left);   //与-判断全符合条件的情况
            else return false;
            }
            if(!root) return true;
            return isSymmetricHelper(root.left,root.right);
};O(n)/O(n)

10.二叉树的最小深度-111*

Alt text

解法1:该方法类似回溯剪枝，就是穷举遍历，迭代找最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var minDepth = function(root) {
    var min = 100000000;
    function traverse(root,depth){//遍历更新全局变量
    	if(!root) return 0; //有此判断，下面if不需要
        depth += 1;
        if(!root.left && !root.right){       
            min = Math.min(min, depth);
            return;
        }
        // if(root.left)不需要了
        traverse(root.left,depth);   //****此处depth参数不可以定义，只能传，因为定义的参数只会累加，最后min         traverse(root.right,depth);  //的值就是找完左节点的高度值。传的参数在每一层函数中值是不同的，例如                                        //[1,2,3,4,5]，定义是3，传参是2.
    }
    if(!root) return 0;
    traverse(root,0);
    return min;
};

解法二：

1
2
3
4
5
6
7
8
9
var minDepth = function (root) {
    if (!root) return 0;
    let l = minDepth(root.left);
    let r = minDepth(root.right);
    //如果左子树或右子树的深度不为 0，即存在一个子树，那么当前子树的最小深度就是该子树的深度+1
    //如果左子树和右子树的深度都不为 0，即左右子树都存在，那么当前子树的最小深度就是它们较小值+1
    if (l == 0 || r == 0) return l + r + 1;
    return Math.min(l, r) + 1;
};

也不完全一样，注意对该结点的左结点或右结点为空的情况

11.左叶子之和-404

Alt text

方法1:

有左孩子，且左孩子为叶节点时累加即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var sumOfLeftLeaves = function(root) {
    if (!root) return 0;
    let ans = 0;
    function dfs(root) {   //属于前序遍历
        if (!root) return 0;
        if (root.left && !root.left.left && !root.left.right) {
            ans += root.left.val;
        }
        dfs(root.left);
        dfs(root.right);
    }
    dfs(root);
    return ans;
};

方法2:

1
2
3
4
5
6
7
8
9
var sumOfLeftLeaves = function(root) {
    if(!root) return 0;
    let ans = 0;
    if(root.left && !root.left.left && !root.left.right){  //左节点存在并为叶子节点时
        ans += root.left.val;
    }
    ans += (sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right));  //ans+=就不会重置ans=0了
    return ans;
};

方法2更好的体现了递归的思想

注意是左叶子而不是左孩子

12.最长同值路径xxx-687

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//自底向上执行，有返回值，若root值==左节点值，L+1，否则重置为0，右侧同理
var longestUnivaluePath = function (root) {
    let ans = 0;

    function helper(root) {//从一个结点开始的最长同值路径长度
        if (!root) return 0;
        //注意因为要递归到底所以不能在这个时候判断相等不相等然后结束递归
        let l = helper(root.left);
        let r = helper(root.right);
        //递归式在这里
        //左右节点和根节点同值情况，感觉少了左节点和根节点同值/右节点和根节点同值情况
        l = (root.left && root.left.val === root.val) ? l + 1 : 0;
        r = (root.right && root.right.val === root.val) ? r + 1 : 0;
        ans = Math.max(ans,l + r);
        return Math.max(l, r);  //递归的功能就是从左子树和右子树中返回一个最长同值路径
    }
    helper(root);
    return ans;
};
*****************************************************************************************
我的解法：
var longestUnivaluePath = function (root) {
    let ans = 0;
    function helper(root) {//从一个结点开始的最长同值路径长度
        if (!root) return 0;
        let maxLorRres = 0
        //注意因为要递归到底所以不能在这个时候判断相等不相等然后结束递归
        let l = helper(root.left);
        let r = helper(root.right);
        //递归式在这里
        if (root.left && root.left.val == root.val && root.right && root.right.val == root.val) {
            ans = Math.max(ans, l + r + 2);
        }
        //从左右子树中选择最长的同值路径
        if (root.left && root.left.val == root.val) {
            maxLorRres = l + 1;
        }
        if (root.right && root.right.val == root.val) {
            maxLorRres = Math.max(maxLorRres, r + 1);
        }
        //从ans与maxLorRres中更新最大值
        ans = Math.max(ans, maxLorRres);
        return maxLorRres;  //递归的功能就是从左子树和右子树中返回一个最长同值路径，此处注意
    }
    helper(root);
    return ans;
};

其实思路与求二叉树的直径和平衡二叉树类似
都是在求另外一个子目标的过程中不断更新一个最优值

13.打家劫舍 IIIx-337

Alt text

这个题是递归的美妙应用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var rob = function (root) {
    //递归式：一个结点的最高金额和（目的） = Max(子结点的最高金额之和，孙结点最高金额和 + 自己的金额)
    if (!root) return 0;
    let val = root.val;
    if (root.left) {
        val += rob(root.left.left);
        val += rob(root.left.right);
    }
    if (root.right) {
        val += rob(root.right.left);
        val += rob(root.right.right);
    }
    return Math.max(val, rob(root.left) + rob(root.right));
};

14.完全二叉树节点数-222

1
2
3
4
5
6
7
8
9
10
11
12
13
var countNodes = function (root) {
    if (!root) return 0;
    let count = 1;
    function dfs(root) {
        if (!root) return 0;
        if (root.left) count += 1;
        if (root.right) count += 1;
        dfs(root.left);
        dfs(root.right);
    }
    dfs(root);
    return count;
};

15.二叉树的所有路径

看回溯-例4

总结

  • 对于可以不从根结点开始的题目，要先抽象出一个简单的从根结点开始的函数，找到与原函数的递推关系，或者是在递归的过程中更新一个全局变量找到最优解
  • 对树进行整体搜索时，不用返回值，查找某一路径或某一条件时有返回值
  • 对于需要求路径的题目，转换为以一个结点为根的深度问题并找到与路径的递推关系
  • 对于既不要求从根结点开始，又求路径的问题，结合以上两者将问题转换为在求深度的过程中更新一个全局变量

层次遍历

1.二叉树的层平均值

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
层次遍历：1、定义空队列。2、根节点入队列。3、while循环（队列不空）。4.获取队列长度用以for循环。5.每次对队头元素判断左右节点是否为空，push进队列。6.最后出队列。
var averageOfLevels = function (root) {
    var q = [];
    var ans = [];
    q.push(root);   //***推进来的都是节点**
    while (q.length !== 0) {
        let sum = 0;
        let len = q.length;
        for (let i = 0; i < len; i++) {
            sum += q[0].val;//注意这个地方下标都为0，因为出队后下标会发生改变，运算使用val
            if (q[0].left) q.push(q[0].left);
            if (q[0].right) q.push(q[0].right);
            q.shift();//队首出队用shift()
        }
        ans.push(sum / len);
    }
    return ans;
};  //O(n)/O(n)

2.找树左下角的值

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//从右侧入队列
var findBottomLeftValue = function (root) {
    let q = [];
    q.push(root);
    let ans = root;
    while (q.length) {
        let len = q.length;
        for (let i = 0; i < len; i++) {
            ans = q[0];
            if (q[0].right) q.push(q[0].right);//注意是从右孩子开始入队
            if (q[0].left) q.push(q[0].left);
            q.shift();
        }
    }
    return ans.val;
};

3.二叉树的层次遍历102*

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var levelOrder = function (root) {
    if (!root) return [];
    let q = [];
    let ans = [];  // 存放遍历结果
    q.push(root);
    let level = 0;  // 代表当前层数
    while (q.length) {
        let len = q.length;  // 第level层的节点数量
        ans[level] = [];  // 第level层的遍历结果
        for (let i = 0; i < len; i++) {
            let temp = q.shift();  //由变量保存出来节点，后面就不用q[0]判断
            ans[level].push(temp.val);
            if (temp.left) q.push(temp.left);  //（589）
            if (temp.right) q.push(temp.right);
        }
        level++;
    }
    return ans;   //LeetCode-107若要求从底向上层次遍历的话，只需反转数组即可
                  //LeetCode-589若要求算N叉树的层次遍历，将上述（589）改为
                  for (int i = 0; i < node->children.size(); i++) { // 将节点孩子加入队列，c++的
                    if (node->children[i]) que.push(node->children[i]);
                }
};  //O(n)/O(n)

前中后序遍历

1.非递归实现二叉树的前序遍历x

1
2
3
4
5
6
7
8
9
10
11
12
13
前中后遍历：1、定义空栈。2、根节点入栈。3、while循环（栈不空），根节点出栈，右,左子树进栈(注意进栈顺序)。
var preorderTraversal = function (root) {
    let ans = [];
    let stack = [];
    if(root) stack.push(root);
    while (stack.length) {
        let temp = stack.pop();  //先出栈就要用结点承接，上题层次遍历同理
        ans.push(temp.val);
        if (temp.right) stack.push(temp.right);
        if (temp.left) stack.push(temp.left);
    }
    return ans;
};

先入根结点，再依次遍历是先入右孩子，再入左孩子

2.非递归后序遍历x

1
2
3
4
5
6
7
8
9
10
11
12
13
var postorderTraversal = function (root) {
    let ans = [];
    let stack = [];
    if (root) stack.push(root);
    while (stack.length) {
        let temp = stack.pop();
        ans.push(temp.val);
        if (temp.left) stack.push(temp.left);
        if (temp.right) stack.push(temp.right);
    }
    return ans.reverse();

};

先入根结点，再入左孩子，再入右孩子，最后再反转
思路与前序类似，就是最后要再反转

3.非递归二叉树的中序遍历*

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var inorderTraversal = function(root) {
    let stack = [];
    let ans = [];
    let node = root;
    while(node || stack.length !== 0){  //开始根节点并不入栈，所以加判断条件node
        while(node){
            stack.push(node);  //根节点在这里入栈，不要提前入
            node = node.left;  //左侧节点全部入栈
        }
        let temp = stack.pop();
        ans.push(temp.val);
        node = temp.right;
    }
    return ans;
};

根入栈后一直左孩子入栈，直到入不了了再出栈顶从栈顶的右孩子重复

二叉查找树

0.验证二叉搜索树

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var isValidBST = function (root) {  //二叉搜索树中序遍历后是递增的数组，判断后一项大于前一项即可
    let queue = [];
    function dfs(root){
        if(!root) return;  //测试用例1<size<1000
        dfs(root.left);
        queue.push(root.val);
        dfs(root.right);
    }
    dfs(root);
    for(let i=0;i<queue.length-1;i++){   //使用数组承接和在中序里判断相差不多
        if(queue[i]>=queue[i+1]) return false;
    }
    return true;
};

1.二叉搜索树的搜索*

1
2
3
4
5
6
7
//搜索某一结点，先比根节点，再递归比左右树，因为只需找到符合条件的，不必遍历整棵树，所以要return递归函数
var searchBST = function (root, val) {
    if (!root || root.val === val) return root;
    if (root.val < val) return searchBST(root.right, val);
    if (root.val > val) return searchBST(root.left, val);
    return null;
};

2.修剪二叉搜索树

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var trimBST = function(root, L, R) {
    //目的：返回以一个结点为根的修建后的二叉树
    //递归式：若结点值小于要求，则返回以右结点为根修剪后的二叉树
    //若结点值大于要求，则返回以左结点为根修剪后的二叉树
    //若满足要求，则将左孩子修剪后返回给左孩子，右孩子修剪后返回右孩子
    //边界条件：root为空,返回空；
    if(!root) return null;
    if(root.val < L) return trimBST(root.right,L ,R );//记得填满参数呀！！！
    if(root.val > R) return trimBST(root.left,L ,R );
    root.left = trimBST(root.left,L ,R );
    root.right = trimBST(root.right, L, R);
    return root;
};
//O(N)，其中N是给定的树的全部节点。我们最多访问每个节点一次。O(N)即使我们没有明确使用任何额外的内存，在最糟糕的情况下，我们递归调用的栈可能与节点数一样大。

注意这是二叉搜索树，左孩子的值都小于根，右孩子的值都大于根，所以若一个结点根的值大于范围，这个结点和右孩子都不能要，反之左孩子都不能要

3.寻找二叉查找树的第 k 小的元素*

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
var kthSmallest = function(root, k) {
    //二叉搜索树的两个重要性质
    //1.左子树的所有结点比根结点小，右子树的所有结点比根结点打
    //2.中序遍历后的数组仍然有序
    let ans = 0;
    let now = 0;
    function inOrder(root,k){
        if(!root) return;
        inOrder(root.left,k);
        now += 1;//用来计数是第几个数，由于有序，第几个数就是第几小
        if(now === k){
            ans = root.val;
            return;
        }
        inOrder(root.right,k);
    }
    inOrder(root,k);
    return ans;
};
*********************************************************************************
var kthSmallest = function (root, k) {
    let q=[];
    function inroder(root) {  //中序排序，存入数组,还是第一种快
        if(!root) return;
        inroder(root.left);
        q.push(root.val);
        inroder(root.right);
    }
    inroder(root);
    return q[k-1];
}

灵活运用了二叉搜索树的遍历后数组仍然有序的性质，并且运用一个计数来提前结束递归

4. 把二叉搜索树转换为累加树-538

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
var convertBST = function (root) {
//注意执行顺序，右-根-左，使用递归中序的翻转即可。
    var sum = 0;
    function midTra(root) {
        if(!root) return;
        midTra(root.right);
        sum += root.val;
        root.val = sum;
        midTra(root.left);
    }
    midTra(root);
    return root;
};

同样灵活运用了二叉搜索树中序遍历有序的性质，右中左遍历得到由大到小的序列，再通过一个变量计数积累和从而进行运算

5.二叉搜索树的最近公共祖先-剑指68I*

Alt text

1
2
3
4
5
6
//二叉搜索树规律：递归+要实现的功能
var lowestCommonAncestor = function(root, p, q) {
    if(root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left,p,q);
    if(root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right,p,q);
    return root;
};

注意返回的是结点，输入的也是结点
灵活运用了二叉搜索树的右边大，左边小的性质

6.二叉树的最近公共祖先 x-剑指68II*

Alt text

1
2
3
4
5
6
7
8
9
10
//此题为二叉树*  递归寻找左右子树值，若在左右子树中，返回根节点，若在一棵子树中，返回该递归节点。
var lowestCommonAncestor = function(root, p, q) {
    if(!root || root.val === p.val || root.val === q.val){  //终止条件+*查找条件
        return root;
    }
    let l = lowestCommonAncestor(root.left,p,q);   //l和r代表节点值*，都能找到，代表祖先是根节点
    let r = lowestCommonAncestor(root.right,p,q);
    if(l && r) return root; //两棵子树中情况
    return l ? l : r;  //在一颗子树上
};  //若查找2/4结点，运行完，l=2,r=null,返回l结点

结点值唯一的条件特别重要
其实就是往左右子树找这两个数的过程，对这些值进行一些判断返回答案

7.二叉搜索树的插入

1
2
3
4
5
6
7
8
9
10
11
var insertIntoBST = function (root, val) {
    if (root == null) {
        return new TreeNode(val);    //将新节点传给上层函数
    }
    if (val < root.val) {
        root.left = insertIntoBST(root.left, val);   //用节点承接才能加上新节点
    } else {
        root.right = insertIntoBST(root.right, val);
    }
    return root;   //返回根节点
};

7.将有序数组转换为二叉搜索树x

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
//取中间值赋给新建空结点，再截取数组，递归赋值
var sortedArrayToBST = function(nums) {
    if(nums.length === 0) return null;
    let len = nums.length;
    let mid = Math.floor(len/2);  //注意js的向下取整，**直接折半**
    let node = new TreeNode(nums[mid]);  //创建一个根节点
    let left_nums = nums.slice(0,mid);  //分成两个数组
    let right_nums = nums.slice(mid + 1);  //mid+1除去根节点了
    node.left = sortedArrayToBST(left_nums);  //递归执行赋给左右子树
    node.right = sortedArrayToBST(right_nums);
    return node;
};

js向下取整Math.floor()
向上取整Math.ceil()
直接运算是带小数的
slice方法(m,n)取下标从m至n-1
slice(m)取下标为m到结尾的值，若m大于最大下标则返回空数组

8.有序链表转换二叉搜索树

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//多一步链表转数组
var sortedListToBST = function (head) {
    function transe(head){  //该方法链表转数组
        if(head instanceof Array) return head;
        let nums = [];
        while(head !== null){
            nums[nums.length] = head.val;  //数组变长赋值，并用val取值
            head = head.next;
        }
        return nums;
    }

    let nums = transe(head);

    if (nums.length === 0) return null;
    let len = nums.length;
    let mid = Math.floor(len / 2);
    let node = new TreeNode(nums[mid]);
    let left_nums = nums.slice(0, mid);
    let right_nums = nums.slice(mid + 1);
    node.left = sortedListToBST(left_nums);
    node.right = sortedListToBST(right_nums);
    return node;
};

跟上一题思路相同，就是转化一下为数组即可

9.两数之和 IV - 输入 BST

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//查找某些值是否存在，存在返回true--使用map存储
var findTarget = function(root, k) {
   let map=new Map();  //定义一个map
   let flag=false;
   function inorder(root,k){  //递归中序遍历
       if(!root) return false;
       inorder(root.left,k);
       if(map.has(k-root.val)) flag=true;
       map.set(root.val,root.val);  //设置下标和值
       inorder(root.right,k);
   }
   inorder(root,k);
   return flag;
};

注意map的用法
这个题其实是不是二叉搜索树都没有关系，因为有可能左右子树都有

10.二叉搜索树的最小绝对差x

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//二叉搜索树多考虑中序遍历，遍历完是递增序列，对两相邻元素，只需定义pre变量即可，在根节点处进行逻辑判断
var getMinimumDifference = function (root) {
    let pre;
    let max = Number.MAX_VALUE;
    function inorder(root) {
        if (!root) return null;
        inorder(root.left);
        if (pre !== null && root.val - pre < max) {
            max = root.val - pre;
        }
        pre = root.val;
        inorder(root.right);
    }
    inorder(root);
    return max;
};

其实就是运用中序遍历的性质即可

11.二叉搜索树中的众数

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//可以中序遍历后存到hash表中，不过多用了一个O(n)的空间，代码量大，重要度小
var findMode = function (root) {
    let ans = [] //输出的承接数组
    let temp = 1 //相同元素个数的承载变量
    let pre  //前一个元素
    let count = 1 //计数有多少相同的
    function inorder(root) {
        if (!root) return []
        inorder(root.left)
        //******逻辑处理部分，可单独抽成一个函数******
        if (root.val == pre) {  //逐个与前一个比较，相同加一，不同重置
            count++
        } else {
            count = 1;
        }
        pre = root.val  //后移一位
        if (temp < count) {
            temp = count
            ans=[root.val]
        }else if(temp == count){
            ans.push(root.val)
        }
        //******逻辑处理部分******
        inorder(root.right)
    }
    inorder(root);
    return ans;
};

注意最后一次的记录要再识别一次

链表

基础之删除链表

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//创建头结点便于删除和返回新链表
var removeElements = function (head, val) {  //若要判断是否为空，需返回元素本身，不能返回[]
    let node = new ListNode();  //创建虚拟头节点，指针不动用以返回最后输出结果
    let pre = node;  //用以移动的指针
    let curr = head;  //同理
    node.next = head;
    while (curr) {
        if (curr.val == val) {
            pre.next = curr.next;
            curr = pre.next;  //删除后当前指针后移
        } else {
            pre=curr;  //两指针都后移
            curr=curr.next;
        }
    }
    return node.next;
};

链表题多采用：改指针指向、递归、栈、双指针等方式，循环使用while

1.相交链表-160*

Alt text

1
2
3
4
5
6
7
8
9
10
//让a走完a链表后再走b链表，让b走完b链表后再走a链表，会在交点相遇
var getIntersectionNode = function(headA, headB) {
    let a = headA;
    let b = headB;
    while(a !== b){
        a = (a === null) ? headB : a.next;
        b = (b === null) ? headA : b.next;
    }
    return a;
};

设 A 的长度为 a + c，B 的长度为 b + c，其中 c 为尾部公共部分长度，可知 a + c + b = b + c + a。

当访问 A 链表的指针访问到链表尾部时，令它从链表 B 的头部开始访问链表 B；同样地，当访问 B 链表的指针访问到链表尾部时，令它从链表 A 的头部开始访问链表 A。这样就能控制访问 A 和 B 两个链表的指针能同时访问到交点。

如果不存在交点，那么 a + b = b + a，以下实现代码中 l1 和 l2 会同时为 null，从而退出循环。

2. 反转链表x-剑指24*

Alt text

递归：x

1
2
3
4
5
6
7
var reverseList = function(head) {
    if(head === null || head.next === null) return head;
    let newNode = reverseList(head.next);//实际上这个newNode是为了保存最后一个结点的位置好返回最后的结果
    head.next.next = head;
    head.next = null;
    return newNode;  //返回开始节点->5
};

递归式： 以下一个结点为开头的结点进行反转然后再改变这一个结点的指针指向

迭代x

Alt text

Alt text

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
//往前指即可，三个变量，pre、current、temp保存下一个值
var reverseList = function (head) {
    let prev = null;
    let curr = head,temp;
    while (curr) {
        temp=curr.next;  //保存后一个节点值
        curr.next=prev;  //改变指针指向，反向指
        prev=curr;  //prev节点后移
        curr=temp;  //curr节点后移
    }
    return prev;
};

3.合并两个有序链表**

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
//递归比较开始节点值，若l1小，l1.next=递归(l1.next,l2),反之l2.next=...
var mergeTwoLists = function(l1, l2) {
    if(l1 === null) return l2;  //这里的l1和l2仅代表一个节点
    if(l2 === null) return l1;
    if(l1.val < l2.val){
        l1.next = mergeTwoLists(l1.next,l2);
        return l1;
    }else{
        l2.next = mergeTwoLists(l1,l2.next);
        return l2;
    }
};

一种排序的新思路，因为指针只需要改变指向即可，所以在这里用这种递归改变指针的方法就会更快不需要新创建结点

4.删除排序链表中的重复元素xx

Alt text

很妙的递归解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var deleteDuplicates = function (head) {
    if (!head || !head.next) return head;
    head.next = deleteDuplicates(head.next); 
    if (head.val === head.next.val) head.next = head.next.next;
    return head;
};
*************************************************************************************
//迭代算法
var deleteDuplicates = function (head) {
    if (!head || !head.next) return head;
    let current = head;
    while (current != null && current.next != null) {
        if (current.val == current.next.val) {
            current.next = current.next.next;
        } else {
            current = current.next;
        }
    }
    return head;
};//也可以快慢指针

若从程序执行的角度考虑就是递归到最后一个结点然后往回进行对比，递归解决链表的问题可以很好的解决由于指针的指向问题的改变引发的问题因为是从后往前进行修改
若从递归的角度看：
递归式就是将本次的next改为以下一个指针开头的不重复排序链表，然后对比这个结点的值和这个不重复链表的开头的结点的值返回结果。
递归的思考方式只需要考虑递归式

5.删除链表的倒数第N个节点xx*

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//我们可以设想假设设定了双指针 p 和 q 的话，当 q 指向末尾的 NULL，p 与 q 之间相隔的元素个数为 n 时，那么删除掉 p 的下一个指针就完成了要求。
var removeNthFromEnd = function (head, n) {
    if(!head) return head
    let preHead = new ListNode(0)  //创建头结点
    preHead.next = head  //头结点指向开始节点，**关键**
    let p = preHead, q = preHead
    for (let i = 0; i < n + 1; i++) {  //q指针后移n+1位置
       q=q.next
    }
    while(q){  //p,q一起后移到q==null，此时p后面的即为要删除的元素
        p=p.next
        q=q.next
    }
    p.next=p.next.next  //改变指针指向
    let returnHead=preHead.next  //将新的链表赋给新节点
    return returnHead
};

利用双指针找到要删除的结点的前一个结点进行删除，若删除的是头结点可以特判

6.两两交换链表中的节点

Alt text

1
2
3
4
5
6
7
8
//类似4，递归法
var swapPairs = function(head) {
    if (!head || !head.next) return head;  //!head代表没节点，!head.next代表只有一个节点
    let newHead=head.next  //原链表第二个节点存起来
    head.next=swapPairs(newHead.next)  //新链表第二个节点指向递归内容（原链表第二个节点的后一节点），递归位置不能变，递归写在前面代表从后向前执行
    newHead.next=head  //新链表第一个结点指向原链表第一个结点，写在递归之后
    return newHead  //这是新返回的第一个节点
};

和前面的题的递归思路很想，也可以用迭代重新生成一个链的方式来解决

7.链表求和

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//使用栈空间，因为要逆序运算
var addTwoNumbers = function (l1, l2) {
    let stack1 = [];
    let stack2 = [];
    let carry = 0;  //进制，非0即1
    let dummy = new ListNode();//头结点，传不传0都可**
    while (l1) {
        stack1.push(l1.val);  //节点值入栈**，注意val
        l1 = l1.next;
    }
    while (l2) {
        stack2.push(l2.val);  //节点值入栈**
        l2 = l2.next;
    }
    //进行相加
    while (stack1.length || stack2.length || carry) {   //carry为1的话，也要再执行一次，例[5][5]**
        let stack1Num = stack1.pop() || 0;//解决个数不匹配问题
        let stack2Num = stack2.pop() || 0;
        let current = (stack1Num + stack2Num + carry) % 10;
        carry = Math.floor((stack1Num + stack2Num + carry) / 10);
        
        let newNode = new ListNode(current);  //current为节点值，创建一个节点值为current的节点
        newNode.next = dummy.next;  //注意用头插法插入结点保证顺序，两步走**
        dummy.next = newNode;
    }
    return dummy.next;
};

使用栈来进行逆序的运算的思想

8.回文链表xx

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
var isPalindrome = function (head) {
    //递归反转链表
    function reverseList(head){
        let pre = null;
        let next = null;
        while(head){
            next = head.next
            head.next = pre;
            pre = head;
            head = next
        }
        return pre;
    }
    function cut(head,cutNode){//cut一个list
        while(head.next != cutNode){
            head = head.next;
        }
        head.next = null;
    }
    function isEqual(head1,head2){//判断两个list是否相等
        while(head1 && head2){
            if(head1.val != head2.val) return false;
            head1 = head1.next;
            head2 = head2.next;
        }
        return true;
    }
    if(head === null || head.next === null) return true;
    //找到要cut的结点即中间的结点！！！
    let fast = head;
    let slow = head;
    while(fast && fast.next){
        fast = fast.next.next;
        slow = slow.next;
    }
    cut(head,slow);
    return isEqual(head,reverseList(slow))
};
  • 一定要注意怎么去找的cut的结点，通过快指针比慢指针快一步的这种方法：
    对于奇数个的链表fast会指向最后一个结点，slow会指向中间的结点
    对于偶数个的链表fast会指向null, slow会指向中间偏右一个的结点
  • 是把cutnode的前一个结点的next设置为null,从而让前半部分保持正序
  • 后半部分是先以slow为起点，但是反转了过后就是以尾为起点
  • 在比较两个list的时候只比较相同的个数所以不用管奇数个结点时多出来的那一个结点

    9.分隔链表xxx

    Alt text
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    var splitListToParts = function(root, k) {
        let ans = [];
        function helper(root,length,k){
            if(k === 0) return;
            if(length === 0){
                ans.push(null);
                helper(root,length,k-1);
                return;
            }else{
            //要分的个数
            let temp = Math.ceil(length/k);
            let newNode = root;
            let head = newNode;
            let i = 1;
            while(i <= temp - 1){//剪下来这一段
                root = root.next;
                i++;
            }
            let next = root.next;
            root.next = null;//直接剪下来就好不需要重新生成
            ans.push(newNode);
            helper(next,length - temp,k-1);
            }
        }
        //求出链表的长度
        let p = root;
        let length = 0;
        while(p){
            length++;
            p = p.next;
        } 
        helper(root,length,k);
        return ans;
    };

10.奇偶链表xx-328

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var oddEvenList = function(head) {
    if(!head) return head;
    let odd = head;
    let even = head.next;
    let temp = even;
    while(even && even.next){
        odd.next = odd.next.next;
        odd = odd.next;
        even.next = even.next.next;
        even = even.next;
    }
    odd.next = temp;//最后连接奇数表和偶数表
    return head;
};

11.链表中间结点*

Alt text

1
2
3
4
5
6
7
8
9
10
//思路和判断链表是否有环一样：双指针法
var middleNode = function (head) {  //快指针每次两格，慢指针每次一格，快指针到尾，慢指针正好中间
    let slow = head,
        fast = head
    while (fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
    }
    return slow
};

队列和栈

1.用栈实现队列x*-232

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//都是调用数组方法来实现栈和队列不同的特性，如pop(),push(),shift(),没有peek()
/**
 * Initialize your data structure here.
 */
var MyQueue = function() {
    this.stack1 = [];        //都用this指向**
    this.stack2 = [];
};

MyQueue.prototype.push = function(x) {
    this.stack1.push(x);
};

MyQueue.prototype.pop = function() {
    if(this.stack2.length !== 0) return this.stack2.pop();   //stack2不空，删除并返回栈顶
    while(this.stack1.length !== 0) this.stack2.push(this.stack1.pop());  //栈为空先加入，再返回
    return this.stack2.pop();
};

MyQueue.prototype.peek = function() {
    if(this.stack2.length !== 0) return this.stack2[this.stack2.length - 1];//若stack2有元素则返回最后一个元素
    else return this.stack1[0];//否则直接返回stack1的第一个元素即可
};

MyQueue.prototype.empty = function() {
    return this.stack1.length === 0 && this.stack2.length == 0; 
};

用两个栈，把第一个栈依次出栈到第二个栈实现顺序的改变从而实现先入先出

2.用队列实现栈x*-225

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Initialize your data structure here.
 */
var MyStack = function() {
this.queue1=[];
this.queue2=[];
};

/**
 * Push element x onto stack. 
 * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function(x) {
this.queue1.push(x);
};

/**
 * Removes the element on top of the stack and returns that element.
 * @return {number}
 */
MyStack.prototype.pop = function() {
if(this.queue1.length!=0) return this.queue1.pop();
else return this.queue2.shift(); 
};

/**
 * Get the top element.
 * @return {number}
 */
MyStack.prototype.top = function() {
if(this.queue1.length!=0) return this.queue1[this.queue1.length-1];
else return this.queue2[0];
};

/**
 * Returns whether the stack is empty.
 * @return {boolean}
 */
MyStack.prototype.empty = function() {
return this.queue1.length==0&&this.queue2.length==0
};

入队后把每一个其他值都出队再入队

3.最小栈xx*

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * initialize your data structure here.
 */
var MinStack = function() {
    this.minStack = [];
    this.stack = [];
    this.min = Number.MAX_SAFE_INTEGER;//最大安全值
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.min = Math.min(x,this.min);
    this.minStack.push(this.min);
    this.stack.push(x);
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    this.minStack.pop();
    this.stack.pop();
    let len = this.minStack.length;
    this.min = len !== 0 ? this.minStack[len - 1] : Number.MAX_SAFE_INTEGER;
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    return this.stack[this.minStack.length - 1];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    return this.min;
};

用两个栈去实现，一个栈正常放数，另外一个栈每次push的时候都存放栈中的最小值。pop的时候就更新最小值为minStack的栈顶元素即可，若全都pop了要重置最小值
Number.MAX_SAFE_INTEGER代表了最大的安全值

4.有效的括号-20*

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var isValid = function (s) {
    if (s.length % 2 === 1) return false
    let stack = []
    for (let i = 0; i < s.length; i++) {
        if (s[i] == '(' || s[i] == '{' || s[i] == '[') stack.push(s[i])  //字符串可直接s[i]获取元素
        else {
            let newTop = stack[stack.length-1]  //获取栈顶元素，先不出栈
            if(newTop=='{'&&s[i]=='}'||newTop=='('&&s[i]==')'||newTop=='['&&s[i]==']'){
                stack.pop()  //如果匹配就出栈
            }else return false //不匹配返回false
        }
    }
    return stack.length==0  //最后栈为空，就是匹配完全，返回真
};

5.滑动窗口最大值*

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//不推荐这种
var maxSlidingWindow = function (nums, k) {  //自己的解法，有点复杂,不可取
    if(!nums.length) return []               //此处也可以写成nums.length===0，但不可以写nums===[]，会报
    let ans = []                             //  undefined
    let curr=[]
    for(let i=0;i<nums.length-k+1;i++){      //此处可以写成i<=nums.length-k
        curr=[]
        for(let j=i;j<k+i;j++){              //slice方法截取方便
            curr.push(nums[j])
        }
        curr.sort((a,b)=>{                   //Math.max获取最大值方便
            return a-b
        })
        ans.push(curr[k-1])
    }
    return ans
};
******************************************************************************
//通过slice函数截取数组部分值，用math.max取最大值，值得借鉴
var maxSlidingWindow = function (nums, k) {
    if (!nums.length) return []
    let res = []
    for (let i = 0; i <= nums.length - k; i++) {
        res.push(Math.max(...nums.slice(i, k + i)))
    }
    return res
};

6.每日温度x

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
常规方法：双层循环
var dailyTemperatures = function (T) {
    let result = new Array(T.length).fill(0);//注意给一个初始化解决有一些为0的问题
    for (let i = 0; i < T.length; i++) {
        let current = T[i];
        for (let j = i + 1; j < T.length; j++) {
            if (T[j] > current) {
                result[i] = j - i;
                break;  //一定要结束循环，才能取到第一个大于current的数
            }
        }
    }
    return result;
};
*****************************************************************************************
栈方法：
var dailyTemperatures = function (T) {
    let stack = [];
    let ans = new Array(T.length).fill(0);//注意给一个初始化解决有一些为0的问题
    for(let i=0;i<T.length;i++){
        //使用peek()无效，peek需要自己写方法实现
        while (stack.length !== 0 && T[stack[stack.length-1]] < T[i]) {
            let idx = stack.pop();  //后一位>前一位，出栈，直到不大于时，后一位进栈
            ans[idx] = i - idx;  //下标相减
        }
        stack.push(i);  //栈中存入下标***注意是下标
    } 
    return ans;
};

用一个栈去存储T的下标维持一个递增栈
若比栈顶的元素对应的温度大就要让它出栈，并且序号之差就是相隔的距离

7.下一个更大元素 IIx

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var nextGreaterElements = function (nums) {
    let stack = [];
    let len = nums.length;
    let ans = new Array(len).fill(-1);
    for (let i = 0; i < 2 * len; i++) {**********
        let index = i % len;//注意要取余数*********
        while (stack.length !== 0 && nums[stack[stack.length - 1]] < nums[index]) { //stack存储下标值
            let idx = stack.pop();
            ans[idx] = nums[index];
        }
        stack.push(index);
    }
    return ans;
};

思路和上一个题相似，就是要遍历数组长度2倍，下标取余即可

8.逆波兰表达式求值

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//逆波兰表达式是后缀表达式，本题要将其转成中缀表达式
var evalRPN = function (tokens) {
    let stack = [];
    for (let i of tokens) {
            switch (i) {
                case "+":
                stack.push(stack.pop() + stack.pop());
                break;
                case '-':
                let sub = stack.pop();
                stack.push(stack.pop() - sub);
                break;
                case '/':
                let divider = stack.pop();
                stack.push(parseInt(stack.pop() / divider,10));  //10 代表10进制,最好用Math.floor()
                break;
                case '*':
                stack.push(stack.pop() * stack.pop());
                break;
                default:
                stack.push(parseInt(i));
            }
        }
    return stack.pop();
};

注意：

  1. switch的语法
  2. 注意除法和减法的顺序
  3. JS中floor会向下保留整数，比如-1.2变成-2，ceil向上保留整数比如1.2-2
  4. 如果只是单纯保留整数部分就直接用parseInt即可parseInt(数字或字符串，进制)，注意默认不为10进制**

9.长度最小的子数组*

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
队列相加（也叫滑动窗口法），思想：逐个加入队列，直到满足条件，再逐个剔除，直到不满足条件时，再逐个往里加。
var minSubArrayLen = function (s, nums) {  //使用两个指针，长度取指针差值，再求最小
    let first = 0, end = 0, sum = 0, min = nums.length + 1  //min不存在情况
    while (end < nums.length) {
        sum += nums[end++]  //进入队列的加和
        while (sum >= s) {  //由题意：是 >=
            min = Math.min(min, end - first)
            sum -= nums[first++]  //大于s后，出队列找最短大于s值
        }
    }
    return min == (nums.length + 1) ? 0 : min
};  //O(n)、O(1)使用指针不必额外数组空间

10.无重复字符的最长子串**

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//滑动窗口
var lengthOfLongestSubstring = function (s) {
    let ans = 0
    let arr = []
    for (let i = 0; i < s.length; i++) {
        let index = arr.indexOf(s[i])
        if (index !== -1) { //找到相同元素，删除重复元素及之前的元素
            arr.splice(0, index + 1)
        }
        arr.push(s[i])  //要在删除相同元素的操作后推进
        ans = Math.max(ans, arr.length)
    }
    return ans
};

11.螺旋矩阵II

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
var generateMatrix = function (n) {
    let res=new Array(n);  //定义二维数组
    for(let i=0;i<n;i++){
        res[i]=new Array(n);
    }
    let startx = 0, starty = 0; // 定义每循环一个圈的起始位置
    let loop = Math.floor(n / 2); // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
    let mid = Math.floor(n / 2); // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
    let count = 1; // 用来给矩阵中每一个空格赋值
    let offset = 1; // 需要控制每一条边遍历的长度，第一圈最右的1个不遍历，左闭右开。
    let i, j;
    while (loop>0) {
        loop--;
        i = startx;
        j = starty;

        // 下面开始的四个for就是模拟转了一圈
        // 模拟填充上行从左到右(左闭右开)
        for (j = starty; j < starty + n - offset; j++) {
            res[startx][j] = count++;
        }
        // 模拟填充右列从上到下(左闭右开)
        for (i = startx; i < startx + n - offset; i++) {
            res[i][j] = count++;
        }
        // 模拟填充下行从右到左(左闭右开)
        for (; j > starty; j--) {
            res[i][j] = count++;
        }
        // 模拟填充左列从下到上(左闭右开)
        for (; i > startx; i--) {
            res[i][j] = count++;
        }

        // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
        startx++;
        starty++;

        // offset 控制每一圈里每一条边遍历的长度
        offset += 2;
    }

    // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
    if (n % 2==1) {
        res[mid][mid] = count;
    }
    return res;
};

Hash

1.数组中两个数的和为给定值*

Alt text

1
2
3
4
5
6
7
8
9
10
11
var twoSum = function (nums, target) {
    let map = new Map();
    for (let i = 0; i < nums.length; i++) {
        let temp = map.get(target - nums[i]);
        if (temp !== undefined && temp != i ) {
            return new Array(temp, i);
        }
        map.set(nums[i], i);
    }
};
注：看双指针第一题

1.1三数之和**

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//双指针：定住一个，左右指针遍历，再求和判断是否满足条件
var threeSum = function(nums) {
    let ans = [];
    if(nums.length < 3) return ans;
    nums.sort((a, b) => a - b); // 排序
    const len = nums.length;
    for (let i = 0; i < len ; i++) {   //定住的元素就是for每次循环的值
        if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
        if(i > 0 && nums[i] == nums[i-1]) continue;//将定住的元素去重，满足三个元素对数组重复元素仅使用一次
        let L = i+1;
        let R = len-1;
        while(L < R){
            const sum = nums[i] + nums[L] + nums[R];
            if(sum == 0){
                ans.push([nums[i],nums[L],nums[R]]);//推入数组形式注意([])
                while (L<R && nums[L] == nums[L+1]) L++; // 左指针元素去重，遍历过的就不遍历了
                while (L<R && nums[R] == nums[R-1]) R--; // 右指针去重，满足题意：避免重复三元组
                L++;
                R--;
            }
            else if (sum < 0) L++;
            else if (sum > 0) R--;
        }
    }        
    return ans;
};

1.2四数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
var fourSum = function (nums, target) {   //就是比三数多一层for循环和去重，依次5数之和，6数之和都能求
    let ans = [];
    if (nums.length < 4) return ans;
    nums.sort((a, b) => a - b); // 排序
    const len = nums.length;
    for (let i = 0; i < len; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;  //定住两个元素，遍历左右指针
        for (let k = i + 1; k < len; k++) {
            if (k > i + 1 && nums[k] == nums[k - 1]) continue;
            let L = k + 1;
            let R = len - 1;
            while (L < R) {
                const sum = nums[i] + nums[k] + nums[L] + nums[R];
                if (sum == target) {
                    ans.push([nums[i], nums[k], nums[L], nums[R]]);//推入数组形式注意([])
                    while (L < R && nums[L] == nums[L + 1]) L++; // 左指针元素去重
                    while (L < R && nums[R] == nums[R - 1]) R--; // 右指针去重，满足题意：避免重复三元组
                    L++;
                    R--;
                }
                else if (sum < target) L++;
                else if (sum > target) R--;
            }
        }
    }
    return ans;
};

1.3四数之和II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var fourSumCount = function (A, B, C, D) {
    let map = new Map();
    let res = 0;
    for (let i = 0; i < A.length; i++) {   //hash存两数和，再对比两数和
        for (let j = 0; j < B.length; j++) {
            let sum=A[i]+B[j];
            if(map.has(sum)) map.set(sum,map.get(sum)+1);
            else map.set(sum,1);
        }
    }
    for (let i = 0; i < C.length; i++) {
        for (let j = 0; j < D.length; j++) {
            let sum=-(C[i]+D[j]);
            if(map.has(sum)) res+=map.get(sum);
        }
    }
    return res;
};  //O(n^2)

2.判断数组是否含有重复元素

Alt text

1
2
3
4
5
6
7
8
9
var containsDuplicate = function(nums) {
    let len = nums.length;
    let map = new Map();
    for(let i = 0;i < len;i++){
        if(map.has(nums[i])) return true;
        else map.set(nums[i],i);
    }
    return false;
};

3.数组中出现次数超一半数字*

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var majorityElement = function (nums) {
    let map = new Map()
    for (let item of nums) {
        if (map.has(item)) {
            map.set(item, map.get(item) + 1)
        } else {
            map.set(item, 1)
        }
        if (map.get(item) > nums.length / 2) {
            return item
            break
        }
    }
};

4.两个数组的交集*

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
var intersection = function(nums1, nums2) {
    let numsOne=[...new Set(nums1)]  //数组去重
    let numsTwo=[...new Set(nums2)]
    let res=[]
    let map=new Map()  //hash表存储，只有这样定义才能使用map.get/map.set等方法
    for(let i=0;i<numsOne.length;i++){  //数组一存入hash表
        let item=numsOne[i]
        if(map.has(item)){   //这步没必要判断
            map.set(item,map.get(item)+1)
        }else{
            map.set(item,1)
        }
    }
    for(let i=0;i<numsTwo.length;i++){  //数组二存入hash表时判断表中是否已有该元素。
        let item=numsTwo[i]
        if(map.has(item)){
           res.push(item)
        }
    }
    return res
};
//简化版
var intersection = function(nums1, nums2) {
    let numsOne=[...new Set(nums1)];
    let numsTwo=[...new Set(nums2)];
    let res=[];
    let map=new Map();
    for(let i of numsOne){
        map.set(i,1)
    }
    for(let i of numsTwo){
        if(map.has(i)){
            res.push(i)
        }
    }
    return res;
}

5. 最长和谐子序列xx-594

Alt text

1
2
3
4
5
6
7
8
9
10
11
var findLHS = function(nums) {   //此处使用数组和hash表没区别，只有处理字符串，有26个字母限制时，使用数组比                                  //hash表省空间
    let map = [];
    for(num of nums){
        map[num] = map[num] === undefined ? 1 : map[num] + 1;
    }
    let longest = 0;
    for(num of nums){
        longest = Math.max( longest , (map[num] + map[num+1]) || 0);//注意这个地方map[num + 1]可能为undefined所以要||0
    }
    return longest;
};

注意看题目这个序列不一定连续

6. 最长连续序列xx

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
var longestConsecutive = function(nums) {
    //构建哈希表
    let map = new Map();
    for(num of nums){
        let count = map.get(num);
        if(count === undefined){
            map.set(num,1);//注意是1
        }else{
            map.set(num,count + 1);
        }
    }
    let longest = 0;
    //再遍历一次找最长的长度
    for(num of nums){
        //只有当这个值的前一个值没有出现时才可能是最长序列的开头，也可以先排序，但不推荐，时间复杂度太高
        if(map.get(num - 1) === undefined){
        let count = 0;
        while(map.get(num) !== undefined){//不为空才执行
            count++;
            num++;  //精髓：每一趟for循环时查找最远距离
        }
        longest = Math.max(count,longest); //每次遍历完一段count就比较一次
        }
    }
    return longest;
};

注意是最长的连续序列要一直递增+1才可以

7.快乐数*

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//同双指针10，就是找重复元素，hash也行，双指针也行
var isHappy = function (n) {
    let map = new Map();
    let sum;
    n = n + '';
    while (sum != 1) {
        sum = 0;
        for (let i = 0; i < n.length; i++) {
            sum += n[i] * n[i];
        }
        n=sum+'';
        if(map.has(sum)) return false;
        map.set(sum,1);
    }
    return true;
};

数组

1.数组扁平化，去重，排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var arr = [ [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10]
// 扁平化(多维降到一维数组)
const flat = arr.flat(Infinity);

// 去重
const unique = (array) => Array.from(new Set(array))  //new Set()后是类数组，如{1,2,2,3}，可执行数组方法
                                                      //Array.from将这种特殊的对象-类数组转成数组。
// 排序
const sort = (array) => array.sort((a, b) => a-b)
return sort

补充：flat() 方法对node版本有要求，至少需要12.0以上，通过array.some() + concat来实现这个flat()，这个对node版本的限制比较低
while(arr.some(Array.isArray)){
    arr = [].concat(...arr)
  } //console.log(arr);

2.只出现一次数字

注：不使用额外空间，所以不用map

我们将循环的数组元素存入map中，再找某元素时，无需遍历map，只需再循环一遍数组，用map.get处理，相当于遍历了map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
var singleNumber = function(nums) {  //只有一个单数，其余两两出现，找出不连续的即可，符合题意
    nums = nums.sort((a, b) => {  
        return a-b
    })
    for (let i = 0; i<nums.length;i+=2){
        if (nums[i] != nums[i+1]) {
            return nums[i]
        }
    }
};
//也可以使用两个指针，每次走两步，若两指针不相等时，返回慢指针所指的值
****************************************************************************************
map方法：好用但不符合题意
var singleNumber = function (nums) {
    let map = new Map()
    for(let i=0;i<nums.length;i++){
        let item=nums[i]
        if(map.has(item)){
            map.set(item,map.get(item)+1)
        }else{
            map.set(item,1)
        }
    }
    for(let item of nums){
        if(map.get(item)===1){
            return item
        }
    }
}

3.合并区间*

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
var merge = function (intervals) {
    if (!intervals) return [];
    intervals.sort((a,b)=> a[0]-b[0]); //按左侧,各自首部排序
    let ans = [intervals[0]];  //第一项赋值作为初始化
    for (let i = 1; i < intervals.length; i++) { // i=1开始，第二项
        if (ans[ans.length - 1][1] >= intervals[i][0]);  //第一项尾部>第二项首部时，有交集
          ans[ans.length - 1][1] = Math.max(ans[ans.length - 1][1], intervals[i][1])//第1尾部比第2尾部
        else ans.push(intervals[i]);
    }
    return ans;
};
//时间复杂度：O(nlogn)，n = intervals.length。arr.sort() 使用快速排序的平均时间复杂度为 O(nlogn) 。
//空间复杂度：O(n)，n = intervals.length。输出数组 res ，极端情况下包含数组 intervals 中所有元素。

4.有效三角形个数*

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var triangleNumber = function (nums) {
    if (nums.length < 3) return 0;
    nums.sort((a, b) => a - b);  //递增数组,写{}就得写return，不写{}不写return
    let len = nums.length;
    let count = 0;
    for (let i = len - 1; i > 1; i--) {//从后往前，固定最长边，若nums[L]+nums[R]>nums[i]，那么L后皆满足
        let L = 0;
        let R = i - 1;
        while (L < R) {
            if ((nums[L] + nums[R]) > nums[i]) {  //只需判断两数之和>第三个数即可
                count += R - L;
                R--;
            } else L++;
        }
    }
    return count;
};

字符串

字符串多用数组表映射、转ASCII值、字符串原生方法、正则表达式

1.有效的字母异位词x*

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//因为题目所只有小写字母，考虑长度26位数组更好，使用map的空间消耗要比数组大一些的，因为map要维护红黑树或者哈希表，而且还要做哈希函数。所以数组更加简单直接有效！
var isAnagram = function(s, t) {
    let maps = new  Array(26).fill(0);
    let mapt = new  Array(26).fill(0);
    for(let i of s) maps[i.charCodeAt() - 'a'.charCodeAt()]++;//注意js中字符串的相减不会自动转换为ascii码
    for(let i of t) mapt[i.charCodeAt() - 'a'.charCodeAt()]++;
    for(let i = 0;i < 26;i++){
        if(maps[i] !== mapt[i]) return false;
    }
    return true;
};
****************************************************************************************
注：LeetCode-383赎金信问题，也是数组方法更优化
var canConstruct = function (ransomNote, magazine) {
    let arr = new Array(26).fill(0);
    for (let i of magazine) {
        arr[i.charCodeAt() - 'a'.charCodeAt()]++;
    }
    for (let i of ransomNote) {
        arr[i.charCodeAt() - 'a'.charCodeAt()]--;
        if (arr[i.charCodeAt() - 'a'.charCodeAt()] < 0) return false;
    }
    return true;
}

字符串和数字的相加减总结

  1. 字符串+字符串
    始终是字符串的拼接
  2. 数字字符串 */- 数字字符串
    会把字符串强制转换为Number进行计算，number≠ASCII
    如：’123.123’ - ‘1’ = Number(‘123.123’) - Number(‘1’) = 122.123

但是Number只会转换成功那些符合数字规范的字符串，像是’123as’就会转换成NaN,最后的结果也只会是NaN

  1. 字符串 + 数字
    同样也是字符串的拼接
  2. 字符串 */- 数字
    同样将字符串用Number()强制转换再进行运算
  3. 字符串和整数间的比较

字符串与整型数字： console.log(‘21’>3) –21>3 true 将字符串数字转化为对应整型数值,再进行数值的比较

字符串之间比较：比较ascll码值 console.log(‘21’>’3’) –’21’>’3’ false

parseInt() 和 Number()的区别

parseInt(数字或者字符串,基于多少进制转换*)一般为10，默认不是10
parseInt()会转换字符串开头首部数字部分,也会保留浮点数的整数部分，不向上或者向下取整
如：123asd => 123, asd123 => NaN,‘’123.123‘ => 123, 123.12 => 123
Number()会强制转换其他类型为数字

所有类型的相加相减总结

  1. 所有类型和字符串相加都会强制转换为字符串再拼接
    ‘123’ + 1 = ‘123’ + String(1) = ‘1231’
    ‘123’ + NaN = ‘123NaN’
    ‘123’ + undefined = ‘123undefined’
  2. 其他的遇到再总结吧

2.最长回文串*

Alt text
注意只是用这些数字，并没有顺序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var longestPalindrome = function (s) {
    let maps = new Array(58).fill(0); //ASCII值是A-65，z-122，差了58位
    for (i of s) maps[i.charCodeAt() - 'A'.charCodeAt()]++; //maps数组填充0
    let count = 0;                   //计算总回文长度
    let flag = false;                 //对于回文中间字母仅取一次，一定要这么写
    for (i of maps) {
        if (i % 2 == 1) {            //i为奇数时
            if (flag == false) {
                flag = true;          //关闭开关
                count++;              //计数加一
            }
            i--;                      //关键点：*i代表字符个数*，若i=1,i--为0，i=3,i--为2，这2个也可以加上
        }
        count += i;                   //计算总的长度
    }
    return count;
};
//注：不可仅计算偶数个数+1，有时可能没有多余字符，如[b,b]

注意不需要注意顺序，最长的个数就是所有值的偶数部分或者如果有奇数的话就+1

3.同构字符串-205

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
var isIsomorphic = function(s, t) {
    let maps = new Array(123).fill(-1);   //z为122
    let mapt = new Array(123).fill(-1);
    for(let i = 0;i < s.length;i++){
        let temps = s[i].charCodeAt();
        let tempt = t[i].charCodeAt();
        if(maps[temps] != mapt[tempt]) return false;
        maps[temps] = i;
        mapt[tempt] = i;
    }
    return true;
};

用一个map存放每一个值上次出现的位置来判断值的位置相等不相等即可

4.回文子串xxx

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var countSubstrings = function(s) {
    function extendSubstrings(s,start,end){
        while(start >= 0 && end < s.length && s[start] === s[end]){
            ans++;
            start--;  //start左移要--
            end++;  //end右移要++
        }
    }
    let ans = 0;
    for(let i = 0;i < s.length;i++){
        extendSubstrings(s,i,i);  //找拥有奇数个元素的个数，1个a的个数 + 3个a的个数 + 5个a的个数...
        extendSubstrings(s,i,i+1); //偶数个a的个数，2个a的个数+4个a的个数...
    }
    return ans;
};

以每一个元素为中心（奇数）或者是以每一个元素和后一个元素一起（偶数）为中心向两侧扩展
可以使用马拉车算法对这个算法进行优化，使时间复杂度降低到O(2n)即(n)的水平

马拉车算法详解

5.回文数x

题目要求不能转换为字符串进行解决
Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var isPalindrome = function(x) {
     var str=x.toString();//转字符串
     if((str.split('').reverse().join(''))===str){//分割+翻转+组合
         return true;
     }else{
         return false;
     }
};
***********************************************************************************************
var isPalindrome = function (x) {    //不转字符串，纯数学运算
    if (x < 0 || (x % 10 == 0 && x != 0)) return false;  //负数、结尾==0都不是回文串
    let revertedNumber = 0;
    while (x > revertedNumber) {   //前一半小于，等于后一半时结束循环
        revertedNumber = x % 10 + revertedNumber * 10;   //翻转后一半的数字
        x = Math.floor(x / 10);
    }
    return x == revertedNumber || x == Math.floor(revertedNumber / 10);  //奇数个时可/10来消除影响
};

6.计数二进制子串xxx

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
var countBinarySubstrings = function (s) {
    let pre = 0;   //用变量pre承接前一组0/1的个数
    let cur = 1;
    let ans = 0;
    for (let i = 1; i < s.length; i++) {
        if (s[i] === s[i - 1]) cur++;
        else {
            ans += Math.min(pre, cur);
            pre = cur;
            cur = 1;
        }
    }
    ans += Math.min(pre, cur);//注意最后要再加一次
    return ans;
};    // O(n)/O(1)
********************************************************************************************
var countBinarySubstrings = function(s) {
    **************************
    let count=[];                 //此部分将每组0和1个数存入数组中，如[0,0,1,1,0,1,1]-count=[2,2,1,2]
    let num=1;
    let ans=0;
    for(let i = 0; i < s.length - 1; i++){
        if(s[i]==s[i+1]){
            num++;
        }else{
            count.push(num);
            num=1;
        }
    }
    count.push(num);
    **************************
     for (let j = 0; j < count.length - 1; j++) {
        ans += Math.min(count[j], count[j + 1]);   //求每两组的贡献总和
    }
    return ans;
};    // O(n)/O(n)

这种只需要保留前后两个值的问题可以不用全部保存，就直接用两个值保存然后更新即可

7.翻转字符串里的单词*

Alt text

1
2
3
4
5
var reverseWords = function (s) {                      //trim去除两端所有空格，split正则表达
    return s.trim().split(/\s+/g).reverse().join(" ")  //\s匹配空格，+匹配多个空格,g全局匹配
    //return s.trim().split(' ').filter(v=>(v !== '')).reverse().join(' ')  过滤器也可
};
//时间和空间都是O(n)，空间O(n)用来存储字符串分割之后的结果

8.字符串相加*

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var addStrings = function (num1, num2) {
    while (num1.length > num2.length) num2 = '0' + num2;
    while (num2.length > num1.length) num1 = '0' + num1;  //先补0对齐
    let res = '';  //结果字符串
    let pre = 0;   //进位
    for (let i = num1.length - 1; i >= 0; i--) {
        let sum = +num1[i] + +num2[i] + pre;  //+号将字符转数字
        if (sum > 9) {   //模10的结果 +res字符串
            pre = 1;
            res = (sum % 10) + res;
        } else {
            pre = 0;
            res = sum + res;
        }
    }
    return pre == 1 ? '1' + res : res;  //判断第一位是否要进位
};

8.1字符串转数字方法

1.字符串在运算操作中会被当做数字类型来处理：s*=1

2.字符前加‘+’：console.log(+s);

3.string的两个转换函数，只对string有效：parseInt(s); // 234 parseFloat(s); //234

4.强制类型转换：Number(s); // 234

数字转字符串：1.toString() 2.数字+任何字符串” “：console.log(num+””);

9.最长公共前缀*

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
var longestCommonPrefix = function (strs) {
    if(strs.length==0) return '';
    if(strs.length==1) return strs[0];
    let res = '';
    for (let i = 0; i < strs[0].length; i++) {  //横向比较，取第一个字符串
        for (let j = 1; j < strs.length; j++) {  //从第二个字符串开始比较
            if (strs[0][i] != strs[j][i]) return res;
        }
        res += strs[0][i];
    }
    return res;
};

双指针

定义左右指针，多是while循环判断

1.两数之和 II - 输入有序数组-167

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
//注意是升序的数组，且输出为index1<index2
var twoSum = function (numbers, target) {
    let left = 0, right = numbers.length - 1;  //双指针
    while (left < right) {                    //升序数组，从最大和最小点开始遍历
        if (numbers[left] + numbers[right] == target) {
            return [left + 1, right + 1];
        } else if (numbers[left] + numbers[right] < target) {
            left++;
        } else {
            right--;
        }
    }
};

2.两数平方和-633

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
var judgeSquareSum = function(c) {
    let right = Math.floor(Math.sqrt(c)),
        left = 0;
    
    while(left <= right){
        let sum = right * right + left * left;
        if(sum === c) return true;
        if(sum > c) right--;
        else left++;
    }
    
    return false;
};

3.反转字符串中的元音字母-345

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var reverseVowels = function(s) {
    let sArray = s.split('');
    let map = ['a','e','i','o','u','A','E','I','O','U'];
    let len = sArray.length;
    let left = 0,
        right = len - 1;
    while(left < right){
        let flagleft = map.indexOf(s[left]),
            flagright = map.indexOf(s[right]);
        if(flagleft === -1 ) left++;
        if(flagright === -1) right--;
        if(flagright !== -1 && flagleft !== -1){
            [sArray[left],sArray[right]] = [sArray[right],sArray[left]];
            left++;
            right--;
        }
    }
    return sArray.join('');
};

注意：

  1. 字符串不能改，要转换成array再改
  2. 字符串转array .split(‘分隔的字符串’)
  3. array转字符串 .join(‘要连接每个元素的字符’)

4.验证回文字符串 Ⅱx-680

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
var validPalindrome = function (s) {    //在基本的验证回文方法中，递归调用右边减一或左边加一情况。
    function isPalindrome(s, left, right) {
        while (left < right) {
            if (s[left++] != s[right--]) return false;
            //等价于 if (s[left] != s[right]) {return false;}
                       left++;right--;
        }
        return true;
    }
    let left = 0,
        right = s.length - 1;
    while (left < right) {
        if (s[left++] != s[right--]) return isPalindrome(s, left - 1, right) || isPalindrome(s, left, right + 1);//注意left++和right--过后就已经改变了
    }
    return true;
};
*******************************************************************************************
//LeetCode-125，验证回文字符串，正则+双指针
var isPalindrome = function (s) {
    s = s.replace(/[^0-9a-zA-Z]/g, '').toLowerCase()  //对于"A man, a plan, a canal: Panama"这样的
    let i = 0, len = s.length, j = len - 1            //[^..]代表未包含的，用空字符代替，再转小写
    while (i < j) {
        if (s[i] == s[j]) {
            i++;
            j--;
        } else {
            return false
        }
    }
    return true
};

很巧妙的写法不用再自己写代码判断，分离出一个功能

5.合并两个有序数组x-88*

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//双指针法,从后往前比较，填充m+n的数组，若从前到后也可，不过需要将nums1先存起来，时间复杂度O(m+n),O(m)
var merge = function (nums1, m, nums2, n) {
    let p1 = m - 1,
        p2 = n - 1,
        MAX_Length = m + n - 1;
    while (p1 >= 0 && p2 >= 0) {
        if (nums1[p1] < nums2[p2]) nums1[MAX_Length--] = nums2[p2--];
        else nums1[MAX_Length--] = nums1[p1--];
    }
    //若nums1中的值比较小，p1很快就到0索引，我们要将nums2合并到nums1中，所以此处为p2
    while(p2>=0) nums1[MAX_Length--] = nums2[p2--];
    return nums1;   //该题最后只能返回nums1，不能返回其他额外数组
};时间复杂度O(m+n),O(1),最优解
********************************************************************************************
//巧妙的数组排序
var merge = function (nums1, m, nums2, n) {
    nums1.splice(m);//由题意得:初始化nums1和nums2数组值，splice直接对原数组修改，所以不用slice(会生成新数组)
    nums2.splice(n);//删除index==n开始及之后的值
    nums1.push(...nums2);
    nums1.sort((a, b) => a - b);
};时间复杂度O((m+n)log(m+n)),O(1)

从后往前遍历这样就可以不用多用一个数组来存储遍历后的值

6.判断链表是否有环**

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
var hasCycle = function (head) {
    if (!head) return false
    let fast = head.next
    let slow = head
    while (fast && fast.next) {  //后面要用到fast.next.next，此处要判断fast.next是否为空
        slow = slow.next
        fast = fast.next.next
        if (fast == slow) {
            return true
        }
    }
    return false
};

//加强版，要求返回环入口的节点
var detectCycle = function (head) {
    if (!head) return head;
    let fast = head;
    let slow = head;
    while (fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
        if (fast == slow) {  //没有环就不可能再相遇，相遇必在环内。
            fast = head;
            while (true) {
                if (slow == fast) {
                    return slow;
                }
                fast = fast.next;
                slow = slow.next;
            }
        }
    }
    return null
};

Alt text

相遇时，慢指针走的距离：D+S1
假设相遇时快指针已经绕环 n 次，它走的距离：D+n(S1+S2)+S1
因为快指针的速度是 2 倍，所以相同时间走的距离也是 2 倍：
D+n(S1+S2)+S1 = 2(D+S1)
即 (n-1)S1+ nS2=D(n−1)S1+nS2=D
我们不关心绕了几次环，取 n = 1 这种特定情况，消掉 S1：
D=S2

怎么利用 D=S2 求入环点
在循环的过程中，快慢指针相遇，位置相同了，可以确定出相遇点
为了确定「入环点」，我们「人为制造」快慢指针在入环点相遇
让快指针从头节点出发，速度改为和慢指针一样，慢指针留在首次相遇点，同时出发
因为 D = S2D=S2 ，二者速度相同，所以会同时到达入环点。

7.通过删除字母匹配到字典里最长单词x

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
var findLongestWord = function (s, d) {
    let maxlen = 0;
    let maxS = '';
    function isEqual(s1, s2) {
        let p1 = 0,
            p2 = 0;
        let len1 = s1.length,
            len2 = s2.length;
        if (maxlen > len2 || len2 > len1) return false;
        while (p1 < len1 && p2 < len2){
            if(s1[p1] === s2[p2]){
                p1++;
                p2++;
            }else{
                p1++;
            }
        }
        if(p2 === len2) return true;
        else return false;    
    }
    for(let s2 of d){
        if(isEqual(s,s2)){
            if(s2.length === maxS.length) maxS = maxS < s2 ? maxS : s2;
            else{
                maxS = s2;
                maxlen = s2.length;
            }
        }
    }
    return maxS;
};

8.接雨水*

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//双指针法
var trap = function (height) {
    let ans = 0;
    let left = 0, right = height.length - 1;
    let left_max = 0, right_max = 0;
    while (left < right) {    //左指针和右指针相遇为界，一次遍历
        if(height[left]<=height[right]){ //找出左右较小的那一个
        ***************************************************************************
            if(height[left]>left_max){   //找出局部中左侧高于当前位置的index
                left_max=height[left];    //因为右侧已经高于左侧，所以会形成积水
            }else{
                ans+=left_max-height[left];  //用左侧最大值减去当前块为积水量
            }
        ***************************************************************************
        上面if、else区域可替换成：
            left_max = Math.max(left_max, height[left]);
            ans += left_max - height[left];
        ***************************************************************************
            left++;      //@@@left++写在外面
        }else{
            if(height[right]>right_max){  //右侧同理
                right_max=height[right];
            }else{
                ans+=right_max-height[right];
            }
            right--;
        }
    }
    return ans;     //时间复杂度O(n),空间复杂度O(1)
};

9.移除元素*

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖***.
var removeElement = function (nums, val) {  //双层for循环，但时间复杂度高
    let len = nums.length;
    for (let i = 0; i < len; i++) {
        if (nums[i] == val) {
            for (let j = i + 1; j < len; j++) {
                nums[j-1]=nums[j];
            }
            i--;
            len--;
        }
    }
    return len;
};
****************************************************************************************
//优化：双指针法：最后返回的数组长度，但打印的是删除后的数组
var removeElement = function (nums, val) {
    let len = nums.length;
    let slow = 0;let fast = 0;
    while(fast < len) {  //快慢指针一起移动，快指针所指覆盖慢指针值
        if(nums[fast]!==val){
           nums[slow]=nums[fast];
           slow++;
        }
        fast++;
    }
    return slow;
};
**************************************************************************
//LeetCode-80，删除有序数组中的重复项II：使每个元素最多出现两次 ，返回删除后数组的新长度。使用 O(1) 额外空间
var removeDuplicates = function(nums) {
    let len = nums.length;
    for (let i = 0; i < len-2; i++) {
        if (nums[i] == nums[i+2]) {
            for (let j = i + 2; j < len; j++) {
                nums[j-1]=nums[j];
            }
            i--;
            len--;
        }
    }
    return len;
};

10.快乐数*

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var isHappy = function (n) {
    function getsum(n) {  //平方和算法
        n = n + '';
        let len = n.length;
        let sum = 0;
        for (let i = 0; i < len; i++) {
            sum += n[i] ** 2;
        }
        return sum;
    }
    let slow = n;  //双指针移动
    let fast = getsum(n);
    while (fast != 1 && slow != fast) {
        slow = getsum(slow);
        fast = getsum(getsum(fast));
    }
    return fast == 1
};

排序

1.排序的方式总结(JS)

选择排序

  1. 思想
    第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。 以此类推，直到全部待排序的数据元素的个数为零。 选择排序是不稳定的排序方法。

  2. 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    function selectSort(arr) {
        let len = arr.length;
        for (let i = 0; i < len - 1; i++) {
            let minIndex = i;
            for (let j = i + 1; j < len; j++) {
                if (arr[j] < arr[minIndex]) minIndex = j;
            }
            [arr[minIndex], arr[i]] = [arr[i], arr[minIndex]];
        }
    }
    let arr = [4,3,2,1];
    selectSort(arr);
    console.log(arr);

  3. 分析

  • 时间复杂度
    * O(n2)
* 最好最坏都是O(n2)
  • 空间
    *  O(1)
  • 不稳定

插入排序

  1. 思想
    Alt text

  2. 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    function insertSort(arr) {
        let len = arr.length;
        for (let i = 1; i < len; i++) {
            let temp = arr[i];
            let j;
            for (j = i - 1; j >= 0; j--) {
                if(temp < arr[j]) [arr[j],arr[j + 1]] = [arr[j + 1], arr[j]];
                else break;
            }
            arr[j + 1] = temp;
        }
    }

    let arr = [20,3,4,2,51,23,45];
    insertSort(arr);
    console.log(arr);

  3. 分析

  • 时间复杂度
    * 平均： O(n2)
* 最差：O(n2)
* 最优：O(n)已经有序
  • 空间复杂度
    * O(1)
  • 稳定

    冒泡

1.思想
就是n-1趟排序，把最大的值浮上去
2.代码

  • 没有优化的

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    function bubbleSort(arr) {
        let len = arr.length;
        for (let i = 1; i < len; i++) {//总共排序len - 1趟
            for (let j = 0; j < len - i; j++) {    //长度-1
                if (arr[j] > arr[j + 1]) [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }

    let arr = [4,3,2,1,1,2,5,25,6,22];
    bubbleSort(arr);
    console.log(arr);

  • 优化后的冒泡排序
    就是加个标识：如果某一趟排序没有交换顺序说明已经有序无须再继续

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    function bubbleSort(arr) {
        let len = arr.length;
        for (let i = 1; i < len; i++) {//总共排序len - 1趟
            let flag = true;
            for (let j = 0; j < len - i; j++) {
                if (arr[j] > arr[j + 1]){
                    [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                    flag = false;
                }
            }
            if(flag) break;
        }
    }

    let arr = [4,3,2,1,1,2,5,25,6,22]
    bubbleSort(arr);
    console.log(arr);
  1. 分析(优化后)
  • 时间复杂度
    * O(n2)
* O(n) 最优
* O(n2)最差
  • 稳定

    二路归并x

  1. 思想
    把一个数组二分，先对左边进行二路归并，再对右边进行二路归并使左右两边有序，再把左右两边组合为一个连续的数组。需要把一个数组的连续的两个有序的部分组合称为一个有序的部分。
  2. 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function mergeSort(arr, left, right) {
    function merge(arr, l1, r1, l2, r2) {
        let p1 = l1,
            p2 = l2;

        let temp = [];

        while (p1 <= r1 && p2 <= r2) {
            if (arr[p1] < arr[p2]) temp.push(arr[p1++]);
            else temp.push(arr[p2++]);
        }

        while (p1 <= r1) temp.push(arr[p1++]);
        while (p2 <= r2) temp.push(arr[p2++]);

        for (let i = 0; i < temp.length; i++) {
            arr[i + l1] = temp[i];
        }
    }

    let mid = Math.floor((left + right) / 2);  
    if (left < right) {
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, mid + 1, right);
    }

}

arr = [4, 3, 2, 1, 1, 2, 5, 25, 6, 22]
mergeSort(arr,0,arr.length - 1);
console.log(arr);
  1. 分析
  • 时间复杂度
    * O(nlogn)
  • 空间复杂度
    * O(n)
  • 稳定

快排

  1. 思想
    调整一个序列的第一个值的位置使得让其左边的值都小于等于它，右边的值都大于等于它，然后再最左边和右边进行递归，双while循环
  2. 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function quickSort(arr, left, right) {
    function partition(arr, left, right) {
        let temp = arr[left];
        while (left < right) {
            while (arr[right] >= temp && left < right) right--;
            arr[left] = arr[right];
            while (arr[left] <= temp && left < right) left++;  //left<right要存在
            arr[right] = arr[left];
        }
        arr[left] = temp;
        return left;    
    }
    //调用分区方法
    if (left < right) {
        let mid = partition(arr, left, right);
        quickSort(arr, left, mid - 1);
        quickSort(arr, mid + 1, right);
    }
}
let arr = [4, 3, 2, 1, 1, 2, 5, 25, 6, 22]
quickSort(arr, 0, arr.length - 1);
console.log(arr);
  1. 分析
  • 时间复杂度
    * O(nlogn)
  • 不稳定

    堆排序

  1. 思想
    先建立一个大顶堆，再进行堆排序，注意堆是一棵完全二叉树，下标要从1开始，所以要调整一下下标

  2. 实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    function heapSort(arr) {
        //向下调整
        function downAdjust(left, right) {
            let lchild = left * 2;
            let rchild = lchild + 1;
            if (lchild > right) return;
            //找到lchild和rchild中的较大值，并把较大的值赋给lchild
            if (rchild <= right && arr[lchild] < arr[rchild]) [lchild, rchild] = [rchild, lchild];
            //与这个结点比较
            if (arr[left] < arr[lchild]) {
                [arr[left], arr[lchild]] = [arr[lchild], arr[left]];
                downAdjust(lchild, right);
            }
        }

        //假设arr不从1下标开始
        arr.push(arr[0]);
        var len = arr.length - 1;

        //从倒数第一个非叶子结点开始向下调整得到大顶堆
        for (let i = Math.floor(len / 2); i > 0; i--) {
            downAdjust(i, len);
        }

        //再进行堆排序
        for(let i = len; i > 0;i--){
            [arr[i],arr[1]] = [arr[1],arr[i]];
            downAdjust(1,i-1);
        }

        //再去掉这个空值
        arr.shift();
    }

    arr = [2, 3, 12, 41, 32, 12, 3];
    heapSort(arr);
    console.log(arr);

  3. 分析

  • 时间复杂度
    * O(nlogn)
  • 不稳定

    排序方式比较

    Alt text

2.调数组顺序使奇数在偶数前*

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var exchange = function (nums) { //快速排序
    let r = nums.length - 1;
    let temp;
    let i = 0, j = r;
    while (i < j) {
        while (i < j && nums[i] % 2 == 1)
            i++;
        while (i < j && nums[j] % 2 == 0) {
            j--;
        }
        if (i < j) {
            temp=nums[j];
            nums[j] = nums[i];
            nums[i]=temp;
        }
    }
    return nums;
};

3.数组中的第K个最大元素**

Alt text

解法1:直接用js内置的sort()
**注意：内置sort会把所有的东西都转换为字符串进行比较，所以要转换成数字比较

1
2
3
4
5
6
7
var findKthLargest = function (nums, k) {
    nums.sort((a,b)=>{  //转为数值比较   ***不写大括号的直接a-b
        return a-b
    })
    let len=nums.length
    return nums[len-k]  //len-k为第k大的数
};

解法2:使用大/小顶堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
var findKthLargest = function (nums, k) {
    //创建大顶堆
    //向下调整
    function downAdjust(nums, low, high) {
        let lchild = low * 2;
        let rchild = lchild + 1;
        if (lchild > high) return;
        if (rchild <= high && nums[lchild] < nums[rchild]) [lchild, rchild] = [rchild, lchild];
        if (nums[low] < nums[lchild]) {
            [nums[lchild], nums[low]] = [nums[low], nums[lchild]];
            downAdjust(nums, lchild, high);
        }
    }

    //调整为大顶堆
    nums.push(nums[0]);
    let len = nums.length - 1;
    for (let i = Math.floor(len / 2); i > 0; i--) {
        downAdjust(nums, i, len);
    }

    //通过大顶堆排序取第k个值，不用全部都排，只排到第k个即可
    for (let i = len; i > len - k; i--) {
        [nums[1], nums[i]] = [nums[i], nums[1]];
        downAdjust(nums, 1, i - 1);
    }
    return nums[len - k + 1];
};

console.log(findKthLargest([3,2,3,1,2,4,5,5,6,7,7,8,2,3,1,1,1,10,11,5,6,2,4,7,8,5,6],2));

解法3:快排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
var findKthLargest = function (nums, k) {
    //快排逆序
    //实现分配函数使nums第一个值的左边都大于它，右边都小于它，一遍快排
    let len = nums.length
    function partition(nums, l, r) {
        let temp = nums[l]   //存的是左值，不能写0
        let first = l, end = r
        while (first < end) {
            while (first < end && nums[end] > temp) end--;
            nums[first] = nums[end]
            while (first < end && nums[first] <= temp) first++;
            nums[end] = nums[first]
        }
        nums[first] = temp
        return first              //返回的是分界下标
    }

    //递归进行快排，实现全部排序
    function quick(nums, l, r) {
        if (l > r) return
        let curr = partition(nums, l, r)
        quick(nums, l, curr - 1)
        quick(nums, curr + 1, r)
    }

    quick(nums, 0, len - 1)
    return nums[len - k]
};

4.出现频率最多的 k 个元素(桶排序)x

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
var topKFrequent = function (nums, k) {
  //首先建立每个值的频率键值对
  let map = new Map();
  nums.forEach(function (item) {
      //注意只能通过.get去访问map中的值
      if (map.has(item)) map.set(item,map.get(item)+1);
      else map.set(item, 1 );
  })
  //以频率为数组下标放入一个数组中   **遍历map方法**
  let arr = [];
  map.forEach(function (value, key) {
      if (!arr[value]) arr[value] = [];
      arr[value].push(key);
  })
  //逆序遍历数组取k个元素放入result数组
  let result = [];
  let len = arr.length - 1;
  let count = 0;
  for(let i = len;i > 0;i--){
      if(arr[i]){
          //注意因为答案唯一所以不用在此处再进行一次遍历判断是否已经达到了k个
          result.push(...arr[i]);
          count += arr[i].length;
      }
      if(count == k) break;
  }
  return result;
};

//方法二：
//1.遍历数组，将数组的值作为 key, 值的个数作为 value，存入一个 map 中
//2.遍历 map，将 map 里面的 key 和 value，作为一个对象 {key:key,value:value} 存入一个数组中
//3.将对象数组根据 value 从大到小排序
//4.截取对象数组的前 K 个值，返回其 key 组成的数组即可
var topKFrequent = function(nums, k) {
    // 1.遍历数组，将所有结果存储到 map 中
    let map = new Map()
    for (let item of nums) {
        if (map.has(item)) {
            let count = map.get(item) + 1
            map.set(item, count)
        } else {
            map.set(item, 1)
        }
    }
    // 2.把数据存入一个对象数组
    let array = []
    for (let [key, value] of map) {
        array.push({
            key,
            value
        })
    }
    // 3.将对象数组根据 value 从大到小排序
    array.sort((a, b) => {
        return b.value - a.value
    })
    // 4.截取前k个，返回其key值组成的数组，这里map为数组遍历方法
    return array.slice(0,k).map(item => {
        return item.key
    })
    //和第四步同理
    //let res = []
    //for (let item of arr.slice(0,k)) {
    //   res.push(item.key)
    //}
    //return res
};

5.根据字符出现频率排序

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var frequencySort = function (s) {
    let map = new Map();
    let len = s.length;
    for (let i = 0; i < len; i++) {
        if (map.has(s[i])) map.set(s[i], map.get(s[i]) + 1);
        else map.set(s[i], 1);
    }

    let arr = [];
    map.forEach(function (val, key) {
        if (!arr[val]) arr[val] = [];  //有多个相同个数的字符，push到一个数组中
        arr[val].push(key);
    })

    let ans = '';
    for (let i = arr.length - 1; i > 0; i--) {
        if (arr[i]) {  // 新数组有空位，要判断是否存在
            arr[i].forEach(function (item) {  //一个数组中多个字符分别遍历
                for (let j = 0; j < i; j++) ans += item;  //对每一个元素都加上对应的频率次
            })
        }
    }
    return ans;
};

6.颜色分类(荷兰国旗问题)

Alt text

三路快排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
var sortColors = function (nums) {
    let zero = 0,
        one = 0,
        two = nums.length - 1;
    while (one <= two) {
        if (nums[one] === 0) {
            [nums[one], nums[zero]] = [nums[zero], nums[one]];
            one++;
            zero++;
        } else if (nums[one] === 1) {
            one++;
        } else {
            [nums[one], nums[two]] = [nums[two], nums[one]];
            two--;
        }
    }
    return nums;
};
***************************************************************************************
方法二：
var sortColors = function (nums) {  //使用数组方法将0删除再插到头部，将2删除再接到尾部
    let len = nums.length
    for (let i = 0; i < len; i++) {
        if (nums[i] === 0) {
            nums.splice(i, 1)
            nums.unshift(0)         //每次插到头部时，指针指向新插入元素
        }
        if (nums[i] === 2) {
            nums.splice(i, 1)
            nums.push(2)
            len--                   //
            i--                     //每次删除一元素，指针不动，后一元素补上
        }
    }
    return nums
};

贪心

1.分发饼干-455*

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var findContentChildren = function (g, s) {
    let Glen = g.length, Slen = s.length;
    g.sort((a, b) => a - b);  //对g，s排序
    s.sort((a, b) => a - b);
    let count = 0;
    for (let i = 0, j = 0; i < Glen && j < Slen; i++ , j++) {
        while (j < Slen && g[i] > s[j]) {  //需求大于饼干量，该饼干量无法满足任何人，作废
            j++;
        }
        if (j < Slen) {
            count++;
        }
    }
    return count;
};

2.无重叠区间x

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//找不重叠的区间，对右区间排序
var eraseOverlapIntervals = function (intervals) {
    if (intervals.length == 0) return 0
    intervals.sort((a, b) => a[1] - b[1])  //移除区间数量最少，让每个子区间右值越小，其余的空闲区间就越大
    let right = intervals[0][1]
    let count = 0
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] >= right) {
            right = intervals[i][1]  //不重叠改变指针
        } else {
            count++                  //重叠时i指针后移，自动过滤右值大的子区间
        }
    }
    return count
};
若是用左值来排序，要考虑[[1,100],[1,10],[2,20]]这种包含关系，做出判断，并删除右值大的一项[1,100]

3.用最少数量的箭引爆气球

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//找不重叠区间即可，不重叠就加一，重叠继续
var findMinArrowShots = function(points) {
    if(!points[0]) return 0;
    //先排序
    points.sort((x,y)=>{
        return x[1] - y[1];
    })

    //再找不重叠区间
    let account = 1;
    let end = points[0][1];

    for(let i = 1;i < points.length;i++){
        if(end < points[i][0]){
            account++;
            end = points[i][1];
        }
    }
    return account;
};

思路与上一个题类似，都是对重叠区间的处理问题

4.根据身高重建队列xx-406

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//先按身高从大到小排序，按照身高排序之后，优先按身高高的people的k来插入，后序插入节点也不会影响前面已经插入的节点
var reconstructQueue = function(people) {
    //按照身高降序排序，若身高相同按K升序来排序***
    people.sort((x,y)=>{
        if(x[0] !== y[0]) return y[0] - x[0];
        else return x[1] - y[1];
    })

    let ans = [];   //插入空数组
    people.forEach(function(person){
        ans.splice(person[1],0,person);  //注意splice方法进行插入，删除数组的用法
    });
    //等同于
    //for (let i = 0; i < people.length; i++) {
    //   ans.splice(people[i][1], 0, people[i])
    //}

    return ans;
};

5.买卖股票的最佳时机xx-121*

Alt text

1
2
3
4
5
6
7
8
9
var maxProfit = function(prices) {
    let profit = 0;
    let minPrice = 9999999;
    prices.forEach(function(price){
        minPrice = Math.min(minPrice,price);
        profit = Math.max(profit,price - minPrice);
    })
    return profit;
};

6.买卖股票的最佳时机 II*

Alt text

1
2
3
4
5
6
7
8
var maxProfit = function (prices) {
    let ans = 0;
    let len = prices.length;
    for (let i = 0; i < len-1; i++) {
        ans += prices[i+1] - prices[i] > 0 ? prices[i+1] - prices[i] : 0;
    }
    return ans;
};

能获得的最大收益就是所有的涨，不用考虑买入。找到递增的时间段，累加即可；

7.种花问题x

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var canPlaceFlowers = function (flowerbed, n) {
    let i = 0;
    let account = 0;
    let len = flowerbed.length;
    while (i < len) {
        if (flowerbed[i] === 1) i = i + 2;
        else {
            let pre = i === 0 ? 0 : flowerbed[i - 1];   //i为索引值，判断左右边界情况
            let next = i === len - 1 ? 0 : flowerbed[i + 1];
            if (pre === 0 && next === 0) {
                account++;
                flowerbed[i] = 1;
                i = i + 2;
            }else i++;
        }
    }
    return account >= n;
};

8.判断子序列x

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//子序列 是不要求连续的,子数组和子串一样，是需要连续的
var isSubsequence = function(s, t) {
    let len = s.length;
    let flag = true;
    for(let i = 0;i < len;i++){
        let index = t.indexOf(s[i]);
        if(index == -1){
            flag = false;
            break;
        }else{
            t = t.substring(index + 1);
        }
    }
    return flag;
};

9.非递减数列x

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//题中非递减数列定义的是：递增数列+等于，所以数组中只能有一对相邻的递减值，同时考虑改变这对值时，对前后序列的影响
//如[3,4,2,3]就不能单纯找一对递减的[4,2]
var checkPossibility = function (nums) {   //要想递增，要么前一项缩小，要么后一项增大
    let flag = nums[0] > nums[1] ? false : true;  //后悔数，用于标识改变元素一次--此处判断因后续要用到i-1
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i + 1]) {  //找到递减的一对
            if (flag) {               //若为true，代表还没改变过
                if(nums[i-1]<nums[i+1]){  //i的后一项大于i的前一项，改i值可递增（瞻前顾后法）
                    nums[i]=nums[i+1];
                    flag=false;
                }
                else if(nums[i-1]>nums[i+1]){
                    nums[i+1]=nums[i];
                    flag=false;
                }
            }else{                 //一次机会用完，还有其他递减对，所以flase
                return false;
            }
        }
    }
    return true;
};

10.最大子序和x*

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//动态规划解法
var maxSubArray = function (nums) {
    let pre = nums[0];   //数组为[-1]单个元素时
    let max = pre;
    let len = nums.length;
    for (let i = 1; i < len; i++) {
        if (pre < 0) {
            pre = nums[i];
        } else {
            pre += nums[i];
        }
        max = Math.max(pre, max);
    }
    return max;
};

11.划分字母区间xxx

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//找到每个字符的最远距离，若索引i==最远距离索引，一段结束。
var partitionLabels = function (S) {
    let len = S.length;
    let pos = [];
    let l = 0,
        r = 0;
    let ans = [];
    //用一个数组存储所有的字符最后一次出现的下标
    for (let i = 0; i < len; i++) {
        pos[S[i].charCodeAt() - 97] = i;   //97是小写字母a的ASCII值
    }
    for (let i = 0; i < len; i++) {
        //更新一个区间的右边界
        r = Math.max(r, pos[S[i].charCodeAt() - 97]);
        //如果更新了过后仍然处在右边界上说明找到了一个区间
        if (i === r) {
            ans.push(r - l + 1);
            l = i + 1;
            r = i + 1;
        }
    }
    return ans;
};
**********************************************************************************
//自己的方法
var partitionLabels = function (S) {
    let index = 0;  //存储最远下标
    let len = S.length;
    let ans = [];
    for (let i = 0; i < len; i++) {
        let indexEnd = S.lastIndexOf(S[i]);  //找到当前字符最远下标
        index = Math.max(index, indexEnd);   //记录最远下标
        if (index == i) {   //一段结束
            ans.push(i + 1);
            continue;
        }
    }
    //此时ans是累加长度
    for (let j = ans.length - 1; j > 0; j--) {  //截取长度
        ans[j] = ans[j] - ans[j - 1];
    }
    return ans;
};

12.盛最多水的容器

Alt text

双指针+贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
var maxArea = function (height) {
    function computeArea(x, y) { //求积水面积方法
        let temp = Math.min(height[x], height[y]);
        return temp * (y - x);
    }
    let left = 0;
    let right = height.length - 1;
    let max = 0;
    while(left < right){
        max = Math.max(computeArea(left,right),max);
        if(height[left] < height[right]){
            left++;
        }else{
            right--;
        }
    }
    return max;
};
********************************************************************************
//自己的方法：求面积最大，从坐标最长开始，有短边的，改变短边坐标，math.max记录最大
var maxArea = function (height) {
    let max = 0;  //记录最大面积
    let l = 0; let r = height.length - 1;
    let len = height.length - 1;  //起始和终点坐标长度
    while (l < r) {
        if (height[l] <= height[r]) {  //左边较小
            max = Math.max(max, height[l] * len);  //纪录最大面积
            l++;   //左边前进一位
            len--; //长边短一位
        } else {
            max = Math.max(max, height[r] * len);
            r--;
            len--;
        }
    }
    return max;
};

二分查找

题目让我们查找某个数优先考虑二分查找，基础是排好序的数组，时间复杂度O(logn)

因为向下取整，所以左侧一定要+1，右侧看情况：

1.若要找的值在目标值左侧，如第一题，输入8，目标值2.82842，要找的是2，那么l<=r; r=mid-1，return r，最后两指针一定重合执行最后一次; 2.若要找的值在目标值右侧，如第7题，[1,3,5,6]，目标值2，找到3对应的索引，l<r; r=mid，return l或r都行;两指针一定相邻执行最后一次；3.若单纯找某值，默认使用l<r结构；

边界问题：题5

1.x 的平方根x*

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//二分查找多是这个结构，while(l<r),let mid=...
var mySqrt = function(x) {
    let l = 0;
    let r = x;
    while(l <= r){
    //要向下取整
        let mid = Math.floor((l + r) / 2);
        let powerMin = mid * mid;
        if(powerMin > x){
            r = mid - 1;
        }else if(powerMin < x){
            l = mid + 1;
        }else{
            return mid;
        }
    }
    //注意最后都要返回r
    return r;
};

原理在于总有一次在+1或者-1后左边界或者右边界会跨过真实的平方值，而跨过之后谁跨过就不会再发生变化直到l > r，此时r指向的是真实平方值的整数部分

2.寻找比目标字母大的最小字母x

Alt text

我的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var nextGreatestLetter = function (letters, target) {
    let ans = '';
    for (let i = 0; i < letters.length; i++) {
        if (letters[i] > target) {  //可以直接比，无需转ASCII-str.charCodeAt()
            ans = letters[i];
            break;
        } else {
            continue;
        }
    }
    if (ans == '') ans = letters[0];
    return ans;
};
//时间复杂度O(n),可采用二分查找

二分查找：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var nextGreatestLetter = function (letters, target) {
    let l = 0;
    let h = letters.length - 1;
    //因为h=mid没有-1所以只能用l < h而不能取等否则会死循环
    //最后退出循环的条件一定是l===h,此时l代表着唯一有可能满足条件的位置
    //所以去判断l是否满足条件就可以判断是否存在这样的元素
    while(l < h){
        let mid = Math.floor((l + r) / 2);
        //注意此处是找到第一个大于target的值，所以是大于符号
        if(letters[mid] > target){
        //这个值有可能就是第一个大于target的值，所以不-1
            h = mid;
        }else{
            l = mid + 1;
        }
    }
    return letters[l] > target ? letters[l] : letters[0];  //都小于目标值，循环返回第一个
};
//时间复杂度O(logn)

3.有序数组中的单一元素xx

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var singleNonDuplicate = function(nums) {
    let l = 0;
    let h = nums.length - 1;
    while(l < h){
        let mid = l + Math.floor((h - l)/2);
        if(mid % 2 === 1 ){
            mid--;
        }
        if(nums[mid] === nums[mid + 1]){
            l = mid + 2;
        }else{
            h = mid;
        }
    }
    return nums[l];
};

4.第一个错误的版本

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var solution = function(isBadVersion) {
    return function(n) {
        let l = 1;
        let h = n;
        while(l < h){
            let mid = Math.floor((l + h)/2);
            if(isBadVersion(mid)){
                h = mid;
            }else{
                l = mid + 1;
            }
        }
        return l;
    };
};

5.寻找旋转排序数组中的最小值

Alt text

把这个数组看成两个部分，l和h各指向一个部分，最小值只能在右边那个部分，取mid发现若发现比nums[h]小则说明mid在l部分，要+1，否则说明mid在h部分并且可能是最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var findMin = function (nums) {
    let l = 0;
    let h = nums.length - 1;
    if(nums[0] < nums[h]) return nums[0];
    while (l < h) {            //此时l<r，没有等号时，L进一，h不退，返回时就是nums[l]
                               //有等号时，都会进位，l=mid+1;h=mid-1;返回nums[h+1]
        let mid = Math.floor((l + h) / 2);
        if(nums[mid] > nums[h]){
            l = mid + 1;   //若L不进一，最后剩两位时，会死循环，例[4,5,6,7,0,1,2]
        }else{
            h = mid;
        }
    }
    return nums[l];  //最后l和r指针重合
};

6.在排序数组中查找元素的第一个和最后一个位置

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var searchRange = function (nums, target) {
    function binarySearch(nums, target) {//第一个值为target的可能的位置
        let l = 0;
        //注意下标从nums.length开始，因为target+1的值可能比所有的值都大，而我们要找的是target+1的位置，所以target+1的位置是可能在nums.length的，所以要从nums.length开始
        //并且mid的值在此处是不可能取到nums[length]的，因为是向下取整，r又至少比l大1，并且循环条件是不取等，所以r至少比mid大1
        let r = nums.length;
        while (l < r) {
            let mid = l + Math.floor((r - l)/2);  //防溢出
            if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }

    //找到第一个值为target的下标
    let index1 = binarySearch(nums,target);
    if(nums[index1] !== target){
        return [-1,-1];
    }
    let index2 = binarySearch(nums,target + 1);
    return [index1,index2 - 1];
};

7.搜索插入位置

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var searchInsert = function (nums, target) {
    let len=nums.length;
    if(target>nums[len-1]) return len;   //最后一个元素单独判断
    let l = 0, r = nums.length - 1;
    while (l < r) {
        let mid = Math.floor(l + ((r - l) / 2));  // 防止溢出 等同于(left + right)/2;
        if (nums[mid] < target) {
            l = mid+1;
        } else  {
            r = mid;
        }
    }
    return l;
};

分治（先pass）

1.为运算表达式设计优先级

Alt text

1.基本分治方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
var diffWaysToCompute = function (input) {
    let len = input.length;
    let ans = [];
    for (let i = 0; i < len; i++) {
        if (input[i] === '+' || input[i] === '-' || input[i] === '*') {
            let l = diffWaysToCompute(input.substring(0, i));
            let r = diffWaysToCompute(input.substring(i + 1));
            for (let j = 0; j < l.length; j++) {
                for (let k = 0; k < r.length; k++) {
                    switch (input[i]) {
                        case '+':
                            ans.push(l[j] + r[k]);
                            break;
                        case '-':
                            ans.push(l[j] - r[k]);
                            break;
                        case '*':
                            ans.push(l[j] * r[k]);
                    }
                }
            }
        }
    }
    //如果全部都为数字，那就直接把这个字符串转换了过后放入数组
    //也相当于递归边界
    if(ans.length === 0){
        ans.push(parseInt(input));
    }
    return ans;
};

2.使用一个map记录每一个input的值防止重复递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
var diffWaysToCompute = function (input) {
    let map = new Map();
    function helper(input) {
        let temp = map.get(input);
        if(temp) return temp;
        let len = input.length;
        let ans = [];
        for (let i = 0; i < len; i++) {
            if (input[i] === '+' || input[i] === '-' || input[i] === '*') {
                let l = diffWaysToCompute(input.substring(0, i));
                let r = diffWaysToCompute(input.substring(i + 1));
                for (let j = 0; j < l.length; j++) {
                    for (let k = 0; k < r.length; k++) {
                        switch (input[i]) {
                            case '+':
                                ans.push(l[j] + r[k]);
                                break;
                            case '-':
                                ans.push(l[j] - r[k]);
                                break;
                            case '*':
                                ans.push(l[j] * r[k]);
                        }
                    }
                }
            }
        }
        if (ans.length === 0) {
            ans.push(parseInt(input));
        }
        map.set(input,ans);
        return ans;
    }
    return helper(input);
};

2.不同的二叉搜索树 IIx

Alt text

思路与上一个题类似

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

var generateTrees = function (n) {

  //如果n小于1则特判
    if(n < 1) return [];

    function helper(l, r) {//由l-r组成的二叉搜索树
        let ans = [];
        for (let i = l; i <= r; i++) {
            let leftChildren = helper(l,i - 1);
            let rightChildren = helper(i + 1,r);
            for(let j = 0;j < leftChildren.length;j++){
                for(let k = 0;k < rightChildren.length;k++){
                    let root = new TreeNode(i);
                    root.left = leftChildren[j];
                    root.right = rightChildren[k];
                    ans.push(root);
                }
            }
        }
//如果没有生成结点则要push一个null
        if(ans.length === 0){
            ans.push(null);
        }
        return ans;
    }

    return helper(1,n);
};

搜索

BFS

1.二进制矩阵中的最短路径

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * @param {number[][]} grid
 * @return {number}
 */
var shortestPathBinaryMatrix = function (grid) {
    let directions = [[1, -1], [1, 0], [1, 1], [0, -1], [0, 1], [-1, -1], [-1, 0], [-1, 1]];
    if (grid[0][0] === 1) return -1;
    if(grid[0][0] === 0 && grid.length === 1) return 1;
    let queue = [];
    queue.push([0, 0]);
    let dis = 1;
    while (queue.length !== 0) {
        let len = queue.length;
        dis++;
        for (let i = 0; i < len; i++) {
            let head = queue.shift();
            [x, y] = head;
            for (let i = 0; i < directions.length; i++) {
                let direction = directions[i];
                [new_x, new_y] = [x + direction[0], y + direction[1]];
                if (new_x === grid.length - 1 && new_y === grid.length - 1 && grid[new_x][new_y] === 0) {
                    return dis;
                }
                if (new_x >= 0 && new_x < grid.length && new_y >= 0 && new_y < grid.length && grid[new_x][new_y] === 0) {
                    queue.push([new_x, new_y]);
                    grid[new_x][new_y] = 1;
                }
            }
        }
    }
    return -1;
};

2.完全平方数x

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function (n) {
    //首先打表获得小于等于n的完全平方数
    function generateSquares(n) {
        let squares = [];
        for (let i = 1; i * i <= n; i++) {
            squares.push(i * i);
        }
        return squares;
    }
    let squares = generateSquares(n);

    //再BFS找到个数
    let q = [];
    let marked = [];
    q.push(n);
    marked[n] = false;
    let ans = 0;

    while (q.length !== 0) {
        let len = q.length;
        ans++;
        for (let i = 0; i < len; i++) {
            let head = q.shift();
            for (let j = 0; j < squares.length; j++) {
                let temp = head - squares[j];
                //因为递增所以一旦开始小于0后面的也小于0
                if(temp < 0){
                    break;
                }
                if(temp === 0){
                    return ans;
                }
                if(marked[temp] === undefined){
                    marked[temp] = false;
                    q.push(temp);
                }
            }
        }
    }

    return ans;
};

3.单词接龙x

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/**
 * @param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {number}
 */
var ladderLength = function (beginWord, endWord, wordList) {
    wordList.push(beginWord);
    //先判断一下endWord在词典中的位置，如果没有返回0
    let end = 0;
    let start = wordList.length - 1;
    for (; end < wordList.length; end++) {
        if (wordList[end] === endWord) {
            break;
        }
    }
    if (end === wordList.length) {
        return 0;
    }

	//再进行BFS
    let g = buildGraphic(wordList);//打一张临接表存储
    let q = [];
    let marked = [];
    q.push(start);
    marked[start] = false;
    let ans = 0;
    while (q.length !== 0) {
        ans++;
        let len = q.length;
        for (let i = 0; i < len; i++) {
            let f = q.shift();
            if (f === end) {
                return ans;
            }
            for (let temp of g[f]) {
                if (marked[temp] === undefined) {
                    marked[temp] = false;
                    q.push(temp);
                }
            }
        }
    }
    return 0;


    //打表生成一个邻接表来存储每一个在wordList中的单词的连接关系
    function buildGraphic(wordList) {
        let graph = [];
        for (let i = 0; i < wordList.length; i++) {
            graph[i] = [];
            for (let j = 0; j < wordList.length; j++) {
                if (isConnect(wordList[i], wordList[j])) {//如果相连
                    graph[i].push(j);
                }
            }
        }
        return graph;
    }

    //判断两个字符串能否改变一个字符就相等
    //注意：完全相等返回false
    function isConnect(x, y) {
        let temp = 0;
        for (let i = 0; i < x.length; i++) {
            if (x[i] !== y[i]) {
                if (temp > 1) {
                    return false;
                } else {
                    temp++;
                }
            }
        }
        return temp === 1;
    }

};

DFS

1.岛屿的最大面积*

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
var maxAreaOfIsland = function (grid) {
    directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    let m = grid.length;
    let n = grid[0].length;
    let result = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            result = Math.max(result, dfs(grid, i, j));
        }
    }

    return result;

    function dfs(grid, x, y) {
        if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] === 0) {
            return 0;
        }
        grid[x][y] = 0;
        let ans = 1;
        for (let direction of directions) {
            let new_x = x + direction[0];
            let new_y = y + direction[1];
            ans += dfs(grid, new_x, new_y);
        }
        return ans;
    }
};

2.岛屿数量

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {

    directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    let m = grid.length;
    let n = grid[0] ? grid[0].length : 0;
    let result = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            result += dfs(grid, i, j);
        }
    }

    return result;

    function dfs(grid, x, y) {
        if (x < 0 || y < 0 || x >= m || y >= n || grid[x][y] === '0') {
            return 0;
        }
        grid[x][y] = '0';
        for (let direction of directions) {
            let new_x = x + direction[0];
            let new_y = y + direction[1];
            dfs(grid, new_x, new_y);
        }
        return 1;
    }
};

3.朋友圈x

Alt text

注意
1:这个是一个nXn的对称矩阵
2:朋友的传递看的是整行或整列不是矩阵相邻

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * @param {number[][]} M
 * @return {number}
 */
var findCircleNum = function (M) {
    let len = M.length;
    let result = 0;
    let visited = [];
    for (let i = 0; i < len; i++) {
        if (visited[i] === undefined) {
            dfs(M, i);
            result++;
        }
    }

    return result;

    function dfs(M, x) {
        visited[x] = true;
        for (let i = 0; i < len; i++) {
            if (M[x][i] === 1 && visited[i] === undefined) {
                M[x][i] = 0;
                dfs(M, i);
            }
        }
    }
};

4.被围绕的区域x

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solve = function (board) {
    let directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    let m = board.length;
    let n = board[0] ? board[0].length : 0;
    for (let i = 0; i < m; i++) {
        dfs(board, i, 0);
        dfs(board, i, n - 1);
    }
    for (let i = 0; i < n; i++) {
        dfs(board, 0, i);
        dfs(board, m - 1, i);
    }
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (board[i][j] === 'T') {
                board[i][j] = 'O';
            } else if (board[i][j] === 'O') {
                board[i][j] = 'X';
            }
        }
    }

    return board;

    function dfs(board, x, y) {
        if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] !== 'O') {
            return;
        }
        board[x][y] = 'T';
        for (let direction of directions) {
            dfs(board, x + direction[0], y + direction[1]);
        }
    }
};

注意：
1:边界上的O和与边界O相连的O是不会被围绕的，剩下的都是会被围绕的
2:所以可以先求出所有边界O组成的联通区域先设成T，再遍历一次矩阵把O改为X，T改为O

5.太平洋大西洋水流问题x

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * @param {number[][]} matrix
 * @return {number[][]}
 */
var pacificAtlantic = function (matrix) {
    if (matrix == null || matrix.length === 0) {
        return [];
    }
    let directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    let m = matrix.length;
    let n = matrix[0].length;
    let ans = [];
    let canReachPcf = generateArray(m, n);
    let canReachAlt = generateArray(m, n);
    for (let i = 0; i < m; i++) {
        dfs(i, 0, canReachPcf);
        dfs(i, n - 1, canReachAlt);
    }
    for (let i = 0; i < n; i++) {
        dfs(0, i, canReachPcf);
        dfs(m - 1, i, canReachAlt);
    }
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (canReachPcf[i][j] === true && canReachAlt[i][j] === true) {
                ans.push([i, j]);
            }
        }
    }

    return ans;

    function generateArray(m, n) {
        let res = [];
        for (let i = 0; i < m; i++) {
            res.push([]);
        }
        return res;
    }

    function dfs(x, y, canReach) {

        if (canReach[x][y] === true) {
            return;
        }
        canReach[x][y] = true;
        for (let direction of directions) {
            let new_x = x + direction[0];
            let new_y = y + direction[1];
            if (new_x < 0 || new_x >= m || new_y < 0 || new_y >= n || matrix[x][y] > matrix[new_x][new_y]) {
                continue;
            }
            dfs(new_x, new_y, canReach);
        }
    }
};

注意二维数组的创建问题
同样是从边缘出发，找到能流到边缘的类

回溯

一种优先搜索算法，枚举搜索尝试过程中找到解决方法，时间复杂度O(2^n)。

1.电话号码的字母组合*

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
var letterCombinations = function(digits) {
    if(digits.length === 0) return [];
    let hash = [0,1,'abc','def','ghi','jkl','mno','pqrs','tuv','wxyz'];
    let ans = [];
    let temp = [];
    dfs(digits);
    return ans;
    
    //写个递归函数
    function dfs(digits){
        //给一个递归终止条件
        if(digits.length === 0){
            ans.push(temp.join(''));  //数组转字符串
            return;
        }

        let c = digits[0];
        let s = hash[parseInt(c)];

        let len = s.length;
        for(let i = 0;i < len;i++){
            temp.push(s[i]);
            dfs(digits.substring(1)); //(start,end)不包括end截取
            temp.pop();  //在原数组上删除最后一个，若有变量承接，承接删除的元素
        }
    }
};

2.复原IP地址*

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
var restoreIpAddresses = function(s) {
    let ans = [];
    let temp = [];
    backTracking(s,0);
    return ans;
    
    function backTracking(s,intNumber){
		//若已有4组数且无剩余数字则添加返回，否则结束函数执行
        if(intNumber === 4){
            if(s.length === 0){
                ans.push(temp.join('.'));
            }
            return;
        }
        let len = s.length;
        for(let i = 0;i < len;i++){
            let part = s.substring(0,i + 1);  //此处注意
            //注意不能有两位数是0开头的
            if(part[0] === '0' && part.length > 1){
                break;
            }
            part = parseInt(part);
            //>255则剪枝
            if(part > 255){
                break;
            }
            temp.push(part);
            backTracking(s.substring(i + 1),intNumber + 1);
            temp.pop();
        }
    }

};

3.单词搜索x

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
    let directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    let m = board.length;
    let n = board[0].length;
    let visited = generateArray(m, n);
    //遍历整个board利用回溯法解决该问题
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (backtracking(visited, i, j, 0)) {
                return true;
            };
        }
    }
    return false;


    //以某一个字母开始能不能通过DFS找到字符串的方式
    function backtracking(visited, i, j, index) {

        if (i >= m || i < 0 || j >= n || j < 0 || visited[i][j] === true || board[i][j] !== word[index]) {
            return false;
        }

        //为true的递归边界
        if (index === word.length - 1) {
            return true;
        }

        visited[i][j] = true;

        for (let d of directions) {
            let new_i = i + d[0];
            let new_j = j + d[1];
            if (backtracking(visited, new_i, new_j, index + 1)) {
                return true;
            };
        }

        //因为是有可能从一个起点开始只能满足部分的要求，所以如果这个点不行的话要把visited修改为false;
        visited[i][j] = false;

        return false;
    }

    function generateArray(m, n) {
        let res = [];
        for (let i = 0; i < m; i++) {
            res.push(new Array(n).fill(false));
        }
        //记得返回
        return res;
    }
};

4.二叉树的所有路径**

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
var binaryTreePaths = function(root) {
    let ans = [];
    let temp = [];
    helper(root);
    return ans;

    //回溯：回溯的本质就是遍历，就是在遍历的过程中去增加一些条件来筛选排序或者返回到上一层
    //这种依托于另外一个功能的实现，在这个实现的基础上进行调整或者功能的组合在树中是应用得非常广泛的
    function helper(root){
        if(!root){
            return;
        }
        if(!root.left && !root.right){
            temp.push(root.val);
            ans.push(temp.join("->"));
            temp.pop();
            return;
        }
        temp.push(root.val);
        helper(root.left);
        helper(root.right);
        temp.pop();
    }
};
*******************************************************************************
//前序遍历更简单点
var binaryTreePaths = function (root) {
    let ans = [];
    function dfs(root, path) {  //传了参数，就不需要剪枝了，每层函数path不同的
        if (root) {
            path += root.val.toString();
            if (root.left == null && root.right == null) {
                ans.push(path);
            } else {
                path += '->';
                dfs(root.left, path);
                dfs(root.right, path);
            }
        }
    }
    dfs(root, '');
    return ans;
};

5.全排列

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var permute = function (nums) {
    let len = nums.length;
    let pos = new Array(len).fill(0);
    let temp = [];
    let ans = [];
    backtracking(0);//添加参数
    return ans;

    function backtracking(index) {
        if(index >= len){
            //注意push进去的是指针，要重新创建一个一样的数组放进去才行
            let t = temp.slice(0);
            ans.push(t);
            return;
        }
        for (let i = 0; i < len; i++) {
            if(pos[i] === 0){
                temp[i] = nums[index];
                pos[i] = 1;
                backtracking(index + 1);
                pos[i] = 0;
            }
        }
    }
};

6.有重复值的全排列

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
var permuteUnique = function (nums) {
    let len = nums.length;
    let visited = new Array(len).fill(0);
    nums.sort(function(x,y){
        return x - y;
    })
    let ans = [];
    let temp = [];
    backtracking(0);
    return ans;

    function backtracking(index) {
        if (index >= len) {
            ans.push(temp.slice(0));
            return;
        }
        //对index位选一个数字放进去
        for (let i = 0; i < len; i++) {
            // 防止重复
            if (i !== 0 && nums[i] === nums[i - 1] && !visited[i - 1]) {
                continue;  
            }
            //如果下标为i的数字没有放进去
            if (visited[i] === 0) {
                visited[i] = 1;
                temp.push(nums[i]);
                //然后递归排下一个位置
                backtracking(index + 1);
                temp.pop();
                visited[i] = 0;
            }
        }
    }
};

7.组合

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var combine = function (n, k) {
    let result = [];
    let temp = [];
    backtracking(n, 1, 1 ,k);
    return result;
    
    function backtracking(n, num, start, k) {
        if (num > k) {
            result.push(temp.slice(0));
            return;
        }
        for (let i = start; i <= n; i++) {
            temp.push(i);
            backtracking(n, num + 1, i + 1, k);
            temp.pop();
        }
    }
};

递归从这一次的数字+1开始，即start = i + 1

8.组合求和

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    candidates.sort(function(x,y){
        return x - y;
    })
    let len = candidates.length;
    let temp = [];
    let ans = [];
    let marked = new Array(len).fill(0);
    backtracking(0,0);
    return ans;

    function backtracking(sum,start){
        if(sum === target){
            ans.push(temp.slice(0));
            return;
        }
        if(sum > target) return;
        for(let i  = start;i < len;i++){
            if(i > 0 && candidates[i] === candidates[i-1] && marked[i - 1] === 0){
                continue;
            }
            marked[i] = 1;     
            temp.push(candidates[i]);
            backtracking(sum + candidates[i],i);
            temp.pop();
            marked[i] = 0;
        }
    }

};

9.组合总和 IIx

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function (candidates, target) {
    let temp = [];
    let ans = [];
    let len = candidates.length;
    let marked = new Array(len).fill(0);

    candidates.sort(function (x, y) {
        return x - y;
    })


    backtracking(0, 0);

    return ans;

    function backtracking(start, sum) {

        if (sum === target) {
            ans.push(temp.slice(0));
            return;
        }


        for (let i = start; i < len; i++) {
            if (i > 0 && candidates[i - 1] === candidates[i] && marked[i - 1] === 0) {
                continue;
            }
            if (sum < target) {
                temp.push(candidates[i]);
                sum += candidates[i];
                marked[i] = 1;
                backtracking(i + 1, sum);
                temp.pop();
                sum -= candidates[i];
                marked[i] = 0;
            }
        }
    }

};

10.组合总和 III

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
var combinationSum3 = function (k, n) {
    let result = [];
    let temp = [];

    backtracking(n, 0, 1, k, 0);

    return result;



    function backtracking(n, num, start, k, sum) {

        if (num === k) {
            if (sum === n) {
                result.push(temp.slice(0));
            }
            return;
        }

        if (sum > n) {
            return;
        }

        for (let i = start; i <= 9; i++) {
            if (sum < n) {
                temp.push(i);
                backtracking(n, num + 1, i + 1, k, sum + i);
                temp.pop();
            }
        }

    }

};

11.子集

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    let temp = [];
    let ans = [];
    let len = nums.length;

    backtracking(0);

    return ans;

    function backtracking(i){
        if(i === len){
            ans.push(temp.slice(0));
            return;
        }
        temp.push(nums[i]);
        backtracking(i + 1);
        temp.pop();
        backtracking(i + 1);
    }

};

12.子集 II

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function (nums) {
    nums.sort(function (x, y) {
        return x - y;
    })
    let len = nums.length;
    let temp = [];
    let ans = [];
    let marked = new Array(len).fill(0);

    backtracking(0,0);

    return ans;

    function backtracking(k,start) {//已经放了k个位置和起始下标
        if(k === len){
            ans.push(temp.slice(0));
            return;
        }
        for (let i = start; i <= len; i++) {

            if(i > 0 && nums[i] === nums[i - 1] && marked[i - 1] === 0){
                continue;
            }

            if (i === len) {
                backtracking(k + 1,i);
            } else {
                temp.push(nums[i]);
                marked[i] = 1;
                backtracking(k + 1, i + 1);
                temp.pop();
                marked[i] = 0;
            }

        }
    }
};

重复元素的处理套路，先排序，如果这个数和前一个相等并且前一个没有用到则跳过避免重复，这里使用了一个i === len来判断是否需要在k位置放入元素

13.分割回文串

Alt text
方法1: 使用了回溯法，遍历每一个子字符串长度为1，2，3…情况
即第一个字符串长度1，2，3…len
第二个为2,3,4…len
…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function (s) {
    let temp = [];
    let ans = [];
    let len = s.length;

    backtracking(0, len - 1);

    return ans;

    function backtracking(start, end) {
        if (start > end) {
            ans.push(temp.slice(0));
            return;
        }
        for (let i = start; i <= end; i++) {
            if (isPalindrome(start, i)) {
                temp.push(s.slice(start, i + 1));
                backtracking(i + 1, end);
                temp.pop();
            }
        }
    }

    function isPalindrome(start, i) {
        while (start < i) {
            if (s[start] !== s[i]) {
                return false;
            }
            start++;
            i--;
        }
        return true;
    }
};

方法2:分治

将大问题分解为小问题，利用小问题的结果，解决当前大问题。

这道题的话，举个例子。

aabb
先考虑在第 1 个位置切割，a | abb
这样我们只需要知道 abb 的所有结果，然后在所有结果的头部把 a 加入
abb 的所有结果就是 [a b b] [a bb]
每个结果头部加入 a，就是 [a a b b] [a a bb]

aabb
再考虑在第 2 个位置切割，aa | bb
这样我们只需要知道 bb 的所有结果，然后在所有结果的头部把 aa 加入
bb 的所有结果就是 [b b] [bb]
每个结果头部加入 aa,就是 [aa b b] [aa bb]

aabb
再考虑在第 3 个位置切割，aab|b
因为 aab 不是回文串，所有直接跳过

aabb
再考虑在第 4 个位置切割，aabb |
因为 aabb 不是回文串，所有直接跳过

最后所有的结果就是所有的加起来
[a a b b] [a a bb] [aa b b] [aa bb]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function (s) {
    return partitionHelper(s);

    function partitionHelper(s) {

        let ans = [];
        let len = s.length;

        for (let i = 0; i < len; i++) {
            let l = s.slice(0, i + 1);
            if (isPalindrome(l) === false) continue;
            let r = partitionHelper(s.slice(i + 1, len));
            for (let j = 0; j < r.length; j++) {
                r[j].unshift(l);
                let temp = r[j];
                ans.push(temp.slice(0));
            }
        }

        if (ans.length === 0) ans.push([]);
        return ans;
    }


    function isPalindrome(s) {
        let start = 0;
        let end = s.length - 1;
        while (start < end) {
            if (s[start] !== s[end]) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
};

方法3:分治 + 动态规划
先打表生成dp数组存储位置start,end的对应字符串是否是回文的
就是利用了动态规划的思想判断是否一个字符串是回文字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function (s) {
    let dp = generateArray(s.length, s.length);
    //生成dp[start][end]是否为回文序列的dp数组
    for (let len = 1; len <= s.length; len++) {//长度为len
        for (let i = 0; i <= s.length - len; i++) {//起始下标为i
            let j = i + len - 1;
            dp[i][j] = s[i] === s[j] && (len < 3 || dp[i + 1][j - 1]) ? 1 : 0;
        }
    }

    return partitionHelper(0, s.length - 1);

    function partitionHelper(start, end) {

        let ans = [];

        for (let i = start; i <= end; i++) {
            let l = s.slice(start, i + 1);
            if (dp[start][i] === 0) continue;
            let r = partitionHelper(i + 1, end);
            for (let j = 0; j < r.length; j++) {
                r[j].unshift(l);
                let temp = r[j];
                ans.push(temp.slice(0));
            }
        }

        if (ans.length === 0) ans.push([]);
        return ans;
    }

    function generateArray(m, n) {
        let res = [];
        for (let i = 0; i < m; i++) {
            res.push(new Array(n).fill(0));
        }
        return res;
    }
};

动态规划(DP)

斐波那契数列*

1.斐波那契数列*

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var fib = function (n) {
    if(n<=1) return n;
    let dp = [];
    dp[0] = 0;
    dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
};//时间复杂度O(n),空间复杂度O(n),因为需要记录整个序列。

var fib = function (n) {
    if (n <= 1) return n;
    let dp = [];
    dp[0] = 0;
    dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        let sum = dp[0] + dp[1];  //仅用两个值即可
        dp[0] = dp[1];
        dp[1] = sum;
    }
    return dp[1];
};//时间复杂度O(n),空间复杂度O(1)。
2.爬楼梯

Alt text

方法1:若n=5，爬1级，则剩下4级要爬；爬2级，则剩下3级要爬；爬4级有几种方式？爬3级有几种方式？于是，爬 5 级楼梯的方式数 = 爬 4 级楼梯的方式数 + 爬 3 级楼梯的方式数。逐渐向下划分：1级时，1种，2级时，2种，作为基础层。题目要求正整数，所以不划分0级和1级。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var climbStairs = function (n) {
    let dip = [];
    dip[1] = 1;
    dip[2] = 2;  //基础层
    for (let i = 3; i <= n; i++) {  //向上一直找到n
        dip[i] = dip[i - 1] + dip[i - 2];
    }
    return dip[n];
};//时间复杂度O(n),空间复杂度O(n)
//面试官要求优化的话：
for (let i = 3; i <= n; i++) {
        let sum = dp[1] + dp[2];  //仅用两个值即可
        dp[1] = dp[2];
        dp[2] = sum;
    }

递归式：f(n) = f(n-1) + f(n-2);

3.最小花费爬楼梯

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var minCostClimbingStairs = function (cost) {
    let dp = [];
    let len = cost.length;
    dp[0] = cost[0];  //数组下标从0开始
    dp[1] = cost[1];
    for (let i = 2; i <= len; i++) {
        dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
    }
    return Math.min(dp[len - 1], dp[len - 2]);  //注意最后一步可以理解为不用花费，所以取倒数第一步，第二步的最小值
}; 

//同样的，for循环中还可以优化成，空间复杂度O(n)
let dpi = min(dp[0], dp[1]) + cost[i];
    dp[0] = dp[1]; // 记录一下前两位
    dp[1] = dpi;
4.打家劫舍

Alt text

正向递推（最优）

此处动态规划方程：dp[n] = MAX( dp[n-1], dp[n-2] + num )，num为最后一位。

1
2
3
4
5
6
7
8
9
10
11
var rob = function (nums) {
    let len = nums.length;
    if (len == 0) return 0;
    let dp = [];
    dp[0] = 0;
    dp[1] = nums[0];
    for (let i = 2; i <= len; i++) {
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
    }
    return dp[len];
};
4.打家劫舍 II

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//掐头去尾，考虑两种情况：偷第1间；不偷第1间，偷最后1间，这两种情况就包括了两间都不偷的情况。所以我们可以将数组分为含有第1间房和不含第1间房的两个数组。
var rob = function (nums) {
    let len = nums.length;
    if (len == 0) return 0;
    if (len == 1) return nums[0];  //特殊情况
    let nums1 = nums.slice(0, len - 1);
    let nums2 = nums.slice(1);
    
    //在两个数组上运用常规打家劫舍问题
    function rober(nums) {
        let dp = [];
        dp[0] = 0;
        dp[1] = nums[0];
        for (let i = 2; i <= nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        return dp[nums.length];
    }
    let ans1 = rober(nums1);
    let ans2 = rober(nums2);
    return Math.max(ans1, ans2);
};

与上一个题的思路类似，只是分成两种情况来比大小

5.母牛生产

Alt text
每一年成熟的牛 = 去年成熟的牛 + 3年前成熟的牛生产出的牛（3年后成熟了）

1
2
3
4
5
6
7
8
9
10
var rob = function (n) {
    let dp = [];
    dp[1] = 1;  //第一年1头
    dp[2] = 2;  //第二年2头
    dp[3] = 3;  //第三年3头
    for (let i = 4; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 3];
    }
    return dp[n];
}

矩阵的最小路径和

1.找第一行，第一列的边界情况——2.双层for循环——3.动态方程

1.最小路径和

Alt text

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//动态规划方程：当前项最小路径和 = 当前项值 + 上项或左项中的最小值
// grid[i][j] += Math.min( grid[i - 1][j], grid[i][j - 1] )
var minPathSum = function (grid) {
    let row = grid.length;  //行数
    let col = grid[0].length;  //列数
    let dp = grid;  //二维数组没办法直接定义
    //grid的第一行与第一列 分别没有上项与左项 故单独处理计算起项最小路径和，第一行：
    for (let j = 1; j < col; j++) {
        dp[0][j] += dp[0][j - 1];
    }
    //第一列：
    for (let i = 1; i < row; i++) {
        dp[i][0] += dp[i - 1][0];
    }
    //二维数组，双循环
    for (let i = 1; i < row; i++) {  //首先行数
        for (let j = 1; j < col; j++) {
            dp[i][j] += Math.min(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[row - 1][col - 1];
};

方法2:正向递推

  • 一维dp

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    var minPathSum = function (grid) {
        let m = grid.length;
        let n = grid[0].length;
        //只需要用一个一维的数组保存纵向上的结果即可
        let dp = new Array(n).fill(0);

        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                if (j === 0) {
                    dp[j] = dp[j];
                } else if (i === 0) {
                    dp[j] = dp[j - 1];
                }else{
                    dp[j] = Math.min(dp[j],dp[j - 1]);
                }
                dp[j] += grid[i][j];
            }
        }
        return dp[n-1];
    };

  • 也可以选择直接在原数组上修改就不占多余的空间

    2.不同路径

    Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//第一行和第一列都可以设置为1，此方法从第二行第二列开始逐行向右计算路径。
var uniquePaths = function (m, n) {
    let dp = new Array(n).fill(1);
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[j] += dp[j - 1];
        }
    }
    return dp[n - 1];
};  //时间复杂度(m*n)，空间复杂度O(n)

//和上题思路一样
var uniquePaths = function (m, n) {
    let dp = new Array(m);  //构建二维数组，先构建一维数组，再for循环
    for (let i = 0; i < m; i++) {
        dp[i] = new Array(n);
        dp[i][0] = 1;
    }
    for (let s = 1; s < n; s++) { //从1开始了
        dp[0][s] = 1;
    }
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
};   //时间复杂度(m*n)，空间复杂度O(m*n)
3.有障碍的不同路径

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
var uniquePathsWithObstacles = function (obstacleGrid) {
    let m = obstacleGrid.length;
    let n = obstacleGrid[0].length;
    let dp = obstacleGrid;
    if (dp[0][0] == 1) return 0;   //第一格有障碍情况，特殊处理
    dp[0][0] = 1;  //第一格单独提出赋值
    for (let i = 1; i < m; i++) {  //第二格起遍历该列
        if (dp[i][0] == 0) {
            dp[i][0] = dp[i - 1][0];  //遇到0，把前值赋给它————此处有利于处理一列有多个障碍情况**
        } else {
            dp[i][0] = 0;   //遇到1，赋值为0
        }
    }
    for (let j = 1; j < n; j++) {  //第一行处理
        if (dp[0][j] == 0) {
            dp[0][j] = dp[0][j - 1];
        } else {
            dp[0][j] = 0;
        }
    }
    for (let i = 1; i < m; i++) {  //第二行第二列起逐行遍历
        for (let j = 1; j < n; j++) {
            if (dp[i][j] == 1) {
                dp[i][j] = 0;
                continue;
            }
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
}

数组区间(未看)

1.区域和检索 - 数组不可变

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @param {number[]} nums
 */
var NumArray = function (nums) {
  this.nums = nums;
  this.sum = [nums[0]];
  for (let i = 1; i < nums.length; i++) {
      this.sum[i] = this.sum[i - 1] + nums[i];
  }
};

/** 
* @param {number} i 
* @param {number} j
* @return {number}
*/
NumArray.prototype.sumRange = function (i, j) {
  return this.sum[j] - this.sum[i] + this.nums[i];
};

/**
 * Your NumArray object will be instantiated and called as such:
 * var obj = new NumArray(nums)
 * var param_1 = obj.sumRange(i,j)
 */

i - j的区间和等于 0-j的和 减去 0-i的和 + nums[i]

2.等差数列划分

Alt text
方法一：参照求回文字符串的方法，但是这里这种方法很慢是O（n2）级别的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {number[]} A
 * @return {number}
 */
var numberOfArithmeticSlices = function (A) {
    let len = A.length;
    let dp = new Array(len).fill(1);
    let ans = 0;

    for (let l = 3; l <= len; l++) {//l为len
        for (let i = 0; i < len - l + 1; i++) {//起始位置为i
            let gap1 = A[i + l - 1] - A[i + l - 2];
            let gap2 = A[i + 1] - A[i];
            dp[i] = gap1 === gap2 && dp[i] === 1 ? 1 : 0;
            if (dp[i] === 1) {
                ans++;
            }
        }
    }

    return ans;
};

方法二：起始不需要关心起点在哪里，只需要关心终点在哪里就可以了
递归式：以i为结束的等差子数组个数:dp[i] = dp[i - 1] + 1如果A[i] - A[i - 1] === A[i - 1] - A[i - 2]，这里的1是指A[i] A[i-1] A[i - 2]
否则就为0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {number[]} A
 * @return {number}
 */
var numberOfArithmeticSlices = function (A) {
    let len = A.length;
    let dp = new Array(len).fill(0);
    let ans = 0;

    for (let i = 2; i < len; i++) {//以i为结尾的字符串
        if (A[i] - A[i - 1] === A[i - 1] - A[i - 2]) {
            dp[i] = dp[i - 1] + 1;
            ans += dp[i];
        } else {
            dp[i] = 0;
        }
    }

    return ans;
};

分割整数

1.定义数组——2.初始化dp[0]/dp[1]——3.双层for循环——4.动态方程

1. 整数拆分x

Alt text

方法1:用数组保存结果，但是过不了时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var integerBreak = function (n) {
    let dp = [];
    function helper(n) {
        if (n === 2) return 1;
        if(dp[n] !== undefined){
            return dp[n];
        }
        let ans = 0;
        for (let i = 1; i < n; i++) {
            ans = Math.max(integerBreak(n - i) * i, (n - i) * i, ans);
        }
        dp[n] = ans;
        return ans;
    }
    return helper(n);
};

方法2:正向递推,从递推边界开始向上走

1
2
3
4
5
6
7
8
9
10
11
//此题公式：dp[i] = Math.max(dp[i],dp[i - j] * j,j * (i - j));  为何j不用拆分，不写成dp[j]的形式，因j是从1开始遍历，拆分j的情况，在遍历j的过程中其实都计算过了。
var integerBreak = function (n) {
    let dp = new Array(n + 1).fill(0);  //后面用dp[i]，此处不能dp=[]，要赋初始值0.
    dp[2] = 1; //dp[0]dp[1]在拆分中是没有意义的，不做定义
    for(let i = 3;i <= n;i++){  //该遍历用于计算从3到n，每个数的最大乘积
        for(let j = 1;j < i;j++){  //该遍历用于计算具体某个数的最大乘积
            dp[i] = Math.max(dp[i],dp[i - j] * j,j * (i - j));  //此处用了dp[i]来比，所以要给dp初始值
        }
    }
    return dp[n];
};O(n^2)和O(n)
2.完全平方数x

Alt text
方法: 使用dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var numSquares = function (n) {
    //首先获得小于等于n的完全平方数
    function generateSquares(n) {
        let squares = [];
        for (let i = 1; i * i <= n; i++) {
            squares.push(i * i);
        }
        return squares;
    }

    let squares = generateSquares(n);
    let dp = new Array(n + 1).fill(9999999);
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;//给一个初始值
    for (let i = 3; i <= n; i++) {//从3开始的每一个数都要求一次
        for (let j = 0; squares[j] <= i; j++) {//遍历所有小于i的完全平方数
            dp[i] = Math.min(dp[i - squares[j]] + 1, dp[i]);
        }
    }
    return dp[n];
};

方法2:贪心 + DP（以后再看）

3.解码方法

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * @param {string} s
 * @return {number}
 */
var numDecodings = function (s) {

    if (s[0] === '0') return 0;
    let len = s.length;
    let dp = new Array(len).fill(0);

    dp[0] = s[0] === '0' ? 0 : 1;

    for (let i = 1; i < len; i++) {

        let temp = parseInt(s[i - 1] + s[i]);

        if (s[i] === '0') {
            if (s[i - 1] === '0' || temp > 26) {
                return 0;
            }
            dp[i] = dp[i - 2] || 1;
        }else{
            if(s[i - 1] === '0' || temp > 26){
                dp[i] = dp[i - 1];
            }else{//注意若没有0且可以组成新数的递归关系，即s[i]都可以加到dp[i-1]中，s[i] + s[i-1]都可以加到dp[i-2]中
                dp[i] = dp[i - 1] + (dp[i - 2]||1);
            }
        }

    }
    return dp[len - 1];
};

最长递增子序列

1. 最长上升子序列

Alt text
方法1:DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function (nums) {
    if(nums.length === 0) return 0;
    let dp = new Array(nums.length).fill(1);
    dp[0] = 1;
    let ans = 1;
    for (let i = 1; i < nums.length; i++) {
        let temp = 0;
        for(let j = 0;j < i;j++){
            if(nums[i] > nums[j]){
                temp = Math.max(temp,dp[j]);
            }
        }
        dp[i] = temp + 1;
        ans = Math.max(ans,dp[i]);
    }
    return ans;
};

方法2: 二分查找（之后补上）

2. 最长数对链

Alt text
思路与上一题类似，但是需要先排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * @param {number[][]} pairs
 * @return {number}
 */
var findLongestChain = function (pairs) {

    let len = pairs.length;
    //首先以每一个pair的第一个元素排序
    pairs.sort(function (x, y) {
        return x[0] - y[0];
    })

    let dp = new Array(len).fill(1);
    let ans = 1;

    for (let i = 0; i < len; i++) {
        for (let j = i - 1; j >= 0; j--) {
            if (pairs[i][0] > pairs[j][1]) {
                dp[i] = Math.max(dp[j] + 1, dp[i]);
                ans = Math.max(ans,dp[i]);
            }
        }
    }

    return ans;
};
3.摆动序列x

Alt text
方法1:与上一个题思路类似的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * @param {number[]} nums
 * @return {number}
 */
var wiggleMaxLength = function (nums) {

    if(nums.length === 0) return 0;

    let len = nums.length;
    let dp = new Array(len).fill(0);
    dp[0] = 1;
    let ans = 1;


    for (let i = 1; i < len; i++) {
        for (let j = i - 1; j >= 0; j--) {
            let sub1 = nums[i] - nums[j];
            let sub2 = j < 1 ? -sub1 : nums[j] - nums[j - 1];
            if (sub1 * sub2 < 0){
                dp[i] = Math.max(dp[j] + 1,dp[i]);
                ans = Math.max(ans,dp[i]);
            }
        }
    }

    return ans;

};

方法2:
up[i] 存的是目前为止最长的以第 i 个元素结尾的上升摆动序列的长度(不一定要取i)。
down[i] 记录的是目前为止最长的以第 i 个元素结尾的下降摆动序列的长度(不一定要取i)。
Alt text
Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {number[]} nums
 * @return {number}
 */
var wiggleMaxLength = function (nums) {

    if(nums.length === 0) return 0;

    let up = 1;
    let down = 1;
    let len = nums.length;

    for(let i = 1;i < len;i++){
        if(nums[i] > nums[i - 1]){
            up = down + 1;
        }else if(nums[i] < nums[i-1]){
            down = up + 1;
        }
    }

    return Math.max(up,down);

};

方法：贪心（之后补充）

最长公共子序列

1.最长公共子序列

Alt text

Alt text

注意这类问题要确定最后一个元素是确定取还是不取

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var longestCommonSubsequence = function (text1, text2) {
    let len1 = text1.length;
    let len2 = text2.length;
    let dp = generateArray(len1 + 1, len2 + 1);

    for (let i = 0; i < len1; i++) {
        for (let j = 0; j < len2; j++) {
            if (text1[i] === text2[j]) {
                dp[i + 1][j + 1] = dp[i][j] + 1;
            } else {
                dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
            }
        }
    }
    return dp[len1][len2];

    function generateArray(m, n) {
        let res = [];
        for (let i = 0; i < m; i++) {
            res.push(new Array(n).fill(0));
        }
        return res;
    }

};

01背包

有一个容量为 N 的背包，要用这个背包装下物品的价值最大，这些物品有两个属性：体积 w 和价值 v。

定义一个二维数组 dp 存储最大价值，其中 dp[i][j] 表示前 i 件物品体积不超过 j 的情况下能达到的最大价值。设第 i 件物品体积为 w，价值为 v，根据第 i 件物品是否添加到背包中，可以分两种情况讨论：

第 i 件物品没添加到背包，总体积不超过 j 的前 i 件物品的最大价值就是总体积不超过 j 的前 i-1 件物品的最大价值，dp[i][j] = dp[i-1][j]。
第 i 件物品添加到背包中，dp[i][j] = dp[i-1][j-w] + v。
第 i 件物品可添加也可以不添加，取决于哪种情况下最大价值更大。因此，0-1 背包的状态转移方程为：
Alt text

1.二维的01背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//二维01背包问题
// W 为背包总体积
// N 为物品数量
// weights 数组存储 N 个物品的重量
// values 数组存储 N 个物品的价值
function knapsack(W, N, weights, values) {
  let dp = generate2DimentionArray(N,W);
  for (let i = 1; i <= N; i++) {
    let w = weights[i - 1];
    let val = values[i - 1];
    for (let j = 1; j <= W; j++) {
      if (j >= w) {         //不拿        //拿了
        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w] + val);
      } else {
        dp[i][j] = dp[i-1][j];  //不拿该物体
      }
    }
  }

  return dp[N][W];

  function generate2DimentionArray(N,W) {
    let arr = new Array(N + 1);
    for (let i = 0; i < N + 1; i++) {
      arr[i] = (new Array(W + 1).fill(0));
    }
    return arr;
  }
}

console.log(knapsack(10,4,[3,4,10,2],[1,2,100,4]));

2.空间优化（注意对体积要从大到小遍历）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function knapsack(W, N, weights, values) {
    let dp = new Array(W + 1).fill(0);
    for (let i = 1; i <= N; i++) {
        let w = weights[i - 1];
        let v = values[i - 1];
        for (let j = W; j >= 1; j--) {
            if (j >= w) {
                dp[j] = Math.max(dp[j], dp[j - w] + v);
            }
        }
    }
    return dp[W];
}

console.log(knapsack(10, 4, [3, 4, 10, 2], [1, 2, 100, 4]));
1.分割等和子集

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var canPartition = function (nums) {
    let len = nums.length;
    let sum = 0;
    for (let i = 0; i < len; i++) {
        sum += nums[i];
    }
    if (sum % 2 === 1) return false;
    let W = sum / 2;

    let dp = new Array(W + 1).fill(false);//注意是重量
    dp[0] = true;
    //如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒叙遍历！
    for (let i = 1; i < len; i++) {
        for (let j = W; j >= nums[i]; j--) {  // 每一个元素一定是不可重复放入，所以从大到小遍历
            dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
        }
    }
    if (dp[W] == W) return true;
    return false;
};  //O(n)和O(n)
2.目标和

Alt text

方法1:DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var findTargetSumWays = function (nums, S) {
    let len = nums.length;
    let ans = 0;
    dfs(0,0);

    function dfs(i, sum) {
        if (i === len) {
            if (sum === S) {
                ans++;
            }
            return;
        }
        sum += nums[i];
        dfs(i + 1, sum);
        sum = sum - nums[i] * 2;
        dfs(i + 1, sum);

    }
    return ans;
};

方法2:动态规划
该问题可以转换为 Subset Sum 问题，从而使用 0-1 背包的方法来求解。

可以将这组数看成两部分，P 和 N，其中 P 使用正号，N 使用负号，有以下推导：

sum(P) - sum(N) = target
sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
2 * sum(P) = target + sum(nums)

因此只要找到一个子集，令它们都取正号，并且和等于 (target + sum(nums))/2，就证明存在解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var findTargetSumWays = function (nums, S) {
    let len = nums.length;
    let sum = 0;
    for (let i = 0; i < len; i++) {
        sum += nums[i];
    }

    if (sum < S || (sum + S) % 2 === 1) return 0;//如果sum < S也不可能达成目标并且避免了数组开的过大

    let W = (sum + S) / 2;
    let dp = new Array(W + 1).fill(0);
    dp[0] = 1;//这里是数个数所以是从1开始

    for (let i = 0; i < len; i++) {
        for (let j = W; j >= nums[i]; j--) {
            dp[j] = dp[j] + dp[j - nums[i]];//注意递归式，不选的个数加上选的个数
        }
    }

    return dp[W];
};
3.一和零

Alt text
资源为多维的01背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * @param {string[]} strs
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var findMaxForm = function (strs, m, n) {

    function generateArray(m, n) {
        let res = [];
        for (let i = 0; i < m; i++) {
            res.push(new Array(n).fill(0));
        }
        return res;
    }

    let len = strs.length;
    let dp = generateArray(m + 1, n + 1);
    
    for (let i = 0; i < len; i++) {
        //数str中的01个数
        let ones = 0;
        let zeros = 0;

        for (let item of strs[i]) {
            if (item === '0') zeros++;
            else ones++;
        }

        for (let j = m; j >= zeros; j--) {//多维也要从后往前遍历
            for (let k = n; k >= ones; k--) {
                dp[j][k] = Math.max(dp[j][k], dp[j - zeros][k - ones] + 1);
            }
        }
    }

    return dp[m][n];
};
4.零钱兑换

Alt text
完全背包问题:背包容量无限

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function (coins, amount) {
    if(amount === 0) return 0;
    let dp = new Array(amount + 1).fill(0);
    for(let coin of coins){
        for(let i = coin;i <= amount;i++){
            if(i === coin){
                dp[i] = 1;
            }else if(dp[i] === 0 && dp[i - coin] !== 0){
                dp[i] = dp[i - coin] + 1;
            }else if(dp[i] !== 0 && dp[i - coin] !== 0){
                dp[i] = Math.min(dp[i],dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] == 0 ? -1 : dp[amount];
};

递推式：dp[coin][i] = Math.min(dp[coin - 1][i],dp[coin][i-coins[amount]] + 1)

5.零钱兑换 II

Alt text
/**

  • @param {number} amount

  • @param {number[]} coins

  • @return {number}

  • /
    var change = function (amount, coins) {

    let dp = new Array(amount + 1).fill(0);
    dp[0] = 1;
    for (let coin of coins) {

    for (let i = coin; i <= amount; i++) {
    dp[i] += dp[i - coin];
}

    }

    return dp[amount];

};

6.单词拆分

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function(s, wordDict) {
    let len = s.length;
    let dp = new Array(len + 1).fill(false);
    dp[0] = true;
    for(let i = 1;i <= len;i++){//要从包的容量遍历起，这样才能考虑顺序
        for(let word of wordDict){
            if(i >= word.length && s.slice(i - word.length, i) === word){
                dp[i] = dp[i] || dp[i - word.length];
            }
        }
    }
    return dp[len];
};
7.组合总和 Ⅳ

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var combinationSum4 = function(nums, target) {
    let dp = new Array(target + 1).fill(0);
    dp[0] = 1;
    for(let i = 1;i <= target;i++){
        for(let num of nums){
            if(num <= i){
                dp[i] += dp[i - num];
            }
        }
    }
    return dp[target];
};

股票问题

base case：
dp[-1][k][0] = dp[i][0][0] = 0
dp[-1][k][1] = dp[i][0][1] = -infinity

状态转移方程：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])

k=1(也可以用贪心来解决)

dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])
dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][0] - prices[i])
= max(dp[i-1][1][1], -prices[i])
解释：k = 0 的 base case，所以 dp[i-1][0][0] = 0。

现在发现 k 都是 1，不会改变，即 k 对状态转移已经没有影响了。
可以进行进一步化简去掉所有 k：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], -prices[i])
Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
    let dp_0 = 0;
    let dp_1 = Number.MIN_SAFE_INTEGER;//因为第0天还没有开始交易又持有的情况不可能发生
    prices.forEach(function (price) {
        dp_0 = Math.max(dp_0, dp_1 + price);
        dp_1 = Math.max(dp_1, -price);
    })
    return dp_0;
};
k=无穷(也可以用贪心来解决)

Alt text
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let dp_0 = 0;
    let dp_1 = Number.MIN_SAFE_INTEGER;
    prices.forEach((price)=>{
        let temp = dp_0;
        dp_0 = Math.max(dp_0,dp_1 + price);
        dp_1 = Math.max(dp_1,temp - price);
    })
    return dp_0;
};
k = +infinity with cooldown

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-2][0]-prices[i])
Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let dp_0 = 0;
    let dp_1 = Number.MIN_SAFE_INTEGER;
    let dp_pre_0 = 0;
    prices.forEach((price)=>{
        let temp = dp_0;
        dp_0 = Math.max(dp_0,dp_1+price);
        dp_1 = Math.max(dp_1,dp_pre_0-price);
        dp_pre_0 = temp;
    })
    return dp_0;
};
k = +infinity with fee

Alt text
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee)
dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number[]} prices
 * @param {number} fee
 * @return {number}
 */
var maxProfit = function(prices, fee) {
    let dp_0 = 0;
    let dp_1 = Number.MIN_SAFE_INTEGER;
    prices.forEach(function(price){
        let temp = dp_0;
        dp_0 = Math.max(dp_0,dp_1 + price - fee);
        dp_1 = Math.max(dp_1,temp - price);
    })
    return dp_0;
};
k=2

Alt text
dp[i][2][0] = max(dp[i-1][2][0], dp[i-1][2][1] + prices[i])
dp[i][2][1] = max(dp[i-1][2][1], dp[i-1][1][0] - prices[i])
dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])
dp[i][1][1] = max(dp[i-1][1][1], - prices[i])
根据公示只需要4个变量就可以，并且先算k=2，再算k=1会有更好的效果，不用一个临时变量来进行存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
    let dp_2_0 = 0;
    let dp_2_1 = Number.MIN_SAFE_INTEGER;
    let dp_1_0 = 0;
    let dp_1_1 = Number.MIN_SAFE_INTEGER;
    prices.forEach(function (price) {
        dp_2_0 = Math.max(dp_2_0, dp_2_1 + price);
        dp_2_1 = Math.max(dp_2_1, dp_1_0 - price);
        dp_1_0 = Math.max(dp_1_0, dp_1_1 + price);
        dp_1_1 = Math.max(dp_1_1, -price);
    })
    return dp_2_0;
};
k=任意值

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * @param {number} k
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (k, prices) {
    let temp = prices.length / 2;
    if (k >= temp) {//如果k值大于prices的长度除2，问题退化为k为无限

        let dp_0 = 0;
        let dp_1 = Number.MIN_SAFE_INTEGER;

        prices.forEach(function (price) {
            let temp = dp_0;
            dp_0 = Math.max(dp_0, dp_1 + price);
            dp_1 = Math.max(dp_1, temp - price);
        })
        return dp_0;

    } else {

        let len = prices.length;
        let dp = createArray(len + 1, k + 1);
        //初始化dp[0][k][1] = -infinity,dp[i][0][1] = -infinity
        for (let i = 0; i <= k; i++) {
            dp[0][i][1] = Number.MIN_SAFE_INTEGER;
        }
        for (let i = 0; i <= len; i++) {
            dp[i][0][1] = Number.MIN_SAFE_INTEGER;
        }
        //再计算最优解
        for (let i = 1; i <= len; i++) {
            for (let j = k; j >= 1; j--) {//从大到小从小到大都可以
                dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i - 1]);
                dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i - 1]);
            }
        }
        //返回结果
        return dp[len][k][0];

    }

    function createArray(m, n) {
        return (new Array(m).fill(0)).map(() => {
            return (new Array(n).fill(0)).map(() => {
                return (new Array(2).fill(0));
            })
        })
    }
};

字符串编辑

Alt text

两个字符串的删除操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function(word1, word2) {
    let len1 = word1.length;
    let len2 = word2.length;
    let dp = createArray(len1+1,len2+1);

	//求解最大公共子串
    for(let i = 1;i <= len1;i++){
        for(let j = 1;j <= len2;j++){
            if(word1[i-1] === word2[j-1]){
                dp[i][j] = Math.max(dp[i-1][j-1] + 1,dp[i-1][j]);
            }else{
                dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }

    return len1 + len2 - 2 * dp[len1][len2];//最小删除数是总长度-2*最大公共子串

    function createArray(m,n){
        return (new Array(m).fill(0)).map(function(){
            return new Array(n).fill(0);
        })
    }
};
编辑距离

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function (word1, word2) {
    let len1 = word1.length;
    let len2 = word2.length;
    let dp = createArray(len1 + 1, len2 + 1);
    //初始化dp[0][i] = i, dp[i][0] = i
    for (let i = 0; i <= len1; i++) {
        dp[i][0] = i;
    }
    for (let i = 0; i <= len2; i++) {
        dp[0][i] = i;
    }
    for (let i = 1; i <= len1; i++) {
        for (let j = 1; j <= len2; j++) {
            if(word1[i - 1] === word2[j - 1]){
                dp[i][j] = Math.min(dp[i-1][j-1],dp[i-1][j] + 1,dp[i][j-1]+1);
            }else{
                dp[i][j] = Math.min(dp[i-1][j-1]+1,dp[i-1][j] + 1,dp[i][j-1]+1);
            }
        }
    }
    return dp[len1][len2];

    function createArray(m, n) {
        return (new Array(m).fill(0)).map(function () {
            return new Array(n).fill(0);
        })
    }
};
只有两个键的键盘

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var minSteps = function(n) {
    //递归边界
    if(n === 1) return 0;
    //先找到n的最大因子
    let mid = Math.ceil(Math.sqrt(n));
    let factor1 = 1;
    let factor2 = n;
    for(let i = n - 1;i >= mid;i--){
        if(n % i === 0){
            factor2 = i;
            factor1 = n / i;
            break;
        }
    }
    //若该因子为n即该数为素数，则直接返回n
    if(factor2 === n){
        return n;
    }else{//如果不为素数，则递归
        return factor1 + minSteps(factor2);
    }
};

本文标题:LeetCode总结

文章作者:智宏伟

发布时间:2021年05月08日 - 16时09分

最后更新:2021年05月08日 - 16时41分

原始链接:http://zhi.com/2021/05/08/LeetCode笔记/

许可协议: "署名-非商用-相同方式共享 3.0" 转载请保留原文链接及作者。

文章目录
  1. 1. LeetCode笔记
    1. 1.1. 二叉树
      1. 1.1.1. 递归
        1. 1.1.1.1. 1.二叉树最大深度(树的高度)*
        2. 1.1.1.2. 2.平衡二叉树
        3. 1.1.1.3. 3. 二叉树的直径x-543
        4. 1.1.1.4. 4. 翻转二叉树-226*
        5. 1.1.1.5. 5.合并二叉树-617
        6. 1.1.1.6. 6.路径总和-112**
        7. 1.1.1.7. 7. 路径总和 IIIx-437
        8. 1.1.1.8. 8.另一个树的子树xx-572
        9. 1.1.1.9. 9.对称二叉树xx-剑指28
        10. 1.1.1.10. 10.二叉树的最小深度-111*
        11. 1.1.1.11. 11.左叶子之和-404
        12. 1.1.1.12. 12.最长同值路径xxx-687
        13. 1.1.1.13. 13.打家劫舍 IIIx-337
        14. 1.1.1.14. 14.完全二叉树节点数-222
        15. 1.1.1.15. 15.二叉树的所有路径
        16. 1.1.1.16. 总结
      2. 1.1.2. 层次遍历
        1. 1.1.2.1. 1.二叉树的层平均值
        2. 1.1.2.2. 2.找树左下角的值
        3. 1.1.2.3. 3.二叉树的层次遍历102*
      3. 1.1.3. 前中后序遍历
        1. 1.1.3.1. 1.非递归实现二叉树的前序遍历x
        2. 1.1.3.2. 2.非递归后序遍历x
        3. 1.1.3.3. 3.非递归二叉树的中序遍历*
      4. 1.1.4. 二叉查找树
        1. 1.1.4.1. 0.验证二叉搜索树
        2. 1.1.4.2. 1.二叉搜索树的搜索*
        3. 1.1.4.3. 2.修剪二叉搜索树
        4. 1.1.4.4. 3.寻找二叉查找树的第 k 小的元素*
        5. 1.1.4.5. 4. 把二叉搜索树转换为累加树-538
        6. 1.1.4.6. 5.二叉搜索树的最近公共祖先-剑指68I*
        7. 1.1.4.7. 6.二叉树的最近公共祖先 x-剑指68II*
        8. 1.1.4.8. 7.二叉搜索树的插入
        9. 1.1.4.9. 7.将有序数组转换为二叉搜索树x
        10. 1.1.4.10. 8.有序链表转换二叉搜索树
        11. 1.1.4.11. 9.两数之和 IV - 输入 BST
        12. 1.1.4.12. 10.二叉搜索树的最小绝对差x
        13. 1.1.4.13. 11.二叉搜索树中的众数
    2. 1.2. 链表
      1. 1.2.1. 基础之删除链表
      2. 1.2.2. 1.相交链表-160*
      3. 1.2.3. 2. 反转链表x-剑指24*
        1. 1.2.3.1. 递归：x
        2. 1.2.3.2. 迭代x
      4. 1.2.4. 3.合并两个有序链表**
      5. 1.2.5. 4.删除排序链表中的重复元素xx
      6. 1.2.6. 5.删除链表的倒数第N个节点xx*
      7. 1.2.7. 6.两两交换链表中的节点
      8. 1.2.8. 7.链表求和
      9. 1.2.9. 8.回文链表xx
      10. 1.2.10. 9.分隔链表xxx
      11. 1.2.11. 10.奇偶链表xx-328
      12. 1.2.12. 11.链表中间结点*
    3. 1.3. 队列和栈
      1. 1.3.1. 1.用栈实现队列x*-232
      2. 1.3.2. 2.用队列实现栈x*-225
      3. 1.3.3. 3.最小栈xx*
      4. 1.3.4. 4.有效的括号-20*
      5. 1.3.5. 5.滑动窗口最大值*
      6. 1.3.6. 6.每日温度x
      7. 1.3.7. 7.下一个更大元素 IIx
      8. 1.3.8. 8.逆波兰表达式求值
      9. 1.3.9. 9.长度最小的子数组*
      10. 1.3.10. 10.无重复字符的最长子串**
      11. 1.3.11. 11.螺旋矩阵II
    4. 1.4. Hash
      1. 1.4.1. 1.数组中两个数的和为给定值*
        1. 1.4.1.1. 1.1三数之和**
        2. 1.4.1.2. 1.2四数之和
        3. 1.4.1.3. 1.3四数之和II
      2. 1.4.2. 2.判断数组是否含有重复元素
      3. 1.4.3. 3.数组中出现次数超一半数字*
      4. 1.4.4. 4.两个数组的交集*
      5. 1.4.5. 5. 最长和谐子序列xx-594
      6. 1.4.6. 6. 最长连续序列xx
      7. 1.4.7. 7.快乐数*
    5. 1.5. 数组
      1. 1.5.1. 1.数组扁平化，去重，排序
      2. 1.5.2. 2.只出现一次数字
      3. 1.5.3. 3.合并区间*
      4. 1.5.4. 4.有效三角形个数*
    6. 1.6. 字符串
      1. 1.6.1. 1.有效的字母异位词x*
        1. 1.6.1.1. 字符串和数字的相加减总结
        2. 1.6.1.2. parseInt() 和 Number()的区别
        3. 1.6.1.3. 所有类型的相加相减总结
      2. 1.6.2. 2.最长回文串*
      3. 1.6.3. 3.同构字符串-205
      4. 1.6.4. 4.回文子串xxx
      5. 1.6.5. 5.回文数x
      6. 1.6.6. 6.计数二进制子串xxx
      7. 1.6.7. 7.翻转字符串里的单词*
      8. 1.6.8. 8.字符串相加*
        1. 1.6.8.1. 8.1字符串转数字方法
      9. 1.6.9. 9.最长公共前缀*
    7. 1.7. 双指针
      1. 1.7.1. 1.两数之和 II - 输入有序数组-167
      2. 1.7.2. 2.两数平方和-633
      3. 1.7.3. 3.反转字符串中的元音字母-345
      4. 1.7.4. 4.验证回文字符串 Ⅱx-680
      5. 1.7.5. 5.合并两个有序数组x-88*
      6. 1.7.6. 6.判断链表是否有环**
      7. 1.7.7. 7.通过删除字母匹配到字典里最长单词x
      8. 1.7.8. 8.接雨水*
      9. 1.7.9. 9.移除元素*
      10. 1.7.10. 10.快乐数*
    8. 1.8. 排序
      1. 1.8.1. 1.排序的方式总结(JS)
        1. 1.8.1.1. 选择排序
        2. 1.8.1.2. 插入排序
        3. 1.8.1.3. 冒泡
        4. 1.8.1.4. 二路归并x
        5. 1.8.1.5. 快排
        6. 1.8.1.6. 堆排序
        7. 1.8.1.7. 排序方式比较
      2. 1.8.2. 2.调数组顺序使奇数在偶数前*
      3. 1.8.3. 3.数组中的第K个最大元素**
      4. 1.8.4. 4.出现频率最多的 k 个元素(桶排序)x
      5. 1.8.5. 5.根据字符出现频率排序
      6. 1.8.6. 6.颜色分类(荷兰国旗问题)
    9. 1.9. 贪心
      1. 1.9.1. 1.分发饼干-455*
      2. 1.9.2. 2.无重叠区间x
      3. 1.9.3. 3.用最少数量的箭引爆气球
      4. 1.9.4. 4.根据身高重建队列xx-406
      5. 1.9.5. 5.买卖股票的最佳时机xx-121*
      6. 1.9.6. 6.买卖股票的最佳时机 II*
      7. 1.9.7. 7.种花问题x
      8. 1.9.8. 8.判断子序列x
      9. 1.9.9. 9.非递减数列x
      10. 1.9.10. 10.最大子序和x*
      11. 1.9.11. 11.划分字母区间xxx
      12. 1.9.12. 12.盛最多水的容器
    10. 1.10. 二分查找
      1. 1.10.1. 1.x 的平方根x*
      2. 1.10.2. 2.寻找比目标字母大的最小字母x
      3. 1.10.3. 3.有序数组中的单一元素xx
      4. 1.10.4. 4.第一个错误的版本
      5. 1.10.5. 5.寻找旋转排序数组中的最小值
      6. 1.10.6. 6.在排序数组中查找元素的第一个和最后一个位置
      7. 1.10.7. 7.搜索插入位置
    11. 1.11. 分治（先pass）
      1. 1.11.1. 1.为运算表达式设计优先级
      2. 1.11.2. 2.不同的二叉搜索树 IIx
    12. 1.12. 搜索
      1. 1.12.1. BFS
        1. 1.12.1.1. 1.二进制矩阵中的最短路径
        2. 1.12.1.2. 2.完全平方数x
        3. 1.12.1.3. 3.单词接龙x
      2. 1.12.2. DFS
        1. 1.12.2.1. 1.岛屿的最大面积*
        2. 1.12.2.2. 2.岛屿数量
        3. 1.12.2.3. 3.朋友圈x
        4. 1.12.2.4. 4.被围绕的区域x
        5. 1.12.2.5. 5.太平洋大西洋水流问题x
    13. 1.13. 回溯
      1. 1.13.0.1. 1.电话号码的字母组合*
      2. 1.13.0.2. 2.复原IP地址*
      3. 1.13.0.3. 3.单词搜索x
      4. 1.13.0.4. 4.二叉树的所有路径**
      5. 1.13.0.5. 5.全排列
      6. 1.13.0.6. 6.有重复值的全排列
      7. 1.13.0.7. 7.组合
      8. 1.13.0.8. 8.组合求和
      9. 1.13.0.9. 9.组合总和 IIx
      10. 1.13.0.10. 10.组合总和 III
      11. 1.13.0.11. 11.子集
      12. 1.13.0.12. 12.子集 II
      13. 1.13.0.13. 13.分割回文串
  2. 1.14. 动态规划(DP)
    1. 1.14.0.1. 斐波那契数列*
      1. 1.14.0.1.1. 1.斐波那契数列*
      2. 1.14.0.1.2. 2.爬楼梯
      3. 1.14.0.1.3. 3.最小花费爬楼梯
      4. 1.14.0.1.4. 4.打家劫舍
      5. 1.14.0.1.5. 4.打家劫舍 II
      6. 1.14.0.1.6. 5.母牛生产
    2. 1.14.0.2. 矩阵的最小路径和
      1. 1.14.0.2.1. 1.最小路径和
      2. 1.14.0.2.2. 2.不同路径
      3. 1.14.0.2.3. 3.有障碍的不同路径
    3. 1.14.0.3. 数组区间(未看)
      1. 1.14.0.3.1. 1.区域和检索 - 数组不可变
      2. 1.14.0.3.2. 2.等差数列划分
    4. 1.14.0.4. 分割整数
      1. 1.14.0.4.1. 1. 整数拆分x
      2. 1.14.0.4.2. 2.完全平方数x
      3. 1.14.0.4.3. 3.解码方法
    5. 1.14.0.5. 最长递增子序列
      1. 1.14.0.5.1. 1. 最长上升子序列
      2. 1.14.0.5.2. 2. 最长数对链
      3. 1.14.0.5.3. 3.摆动序列x
    6. 1.14.0.6. 最长公共子序列
      1. 1.14.0.6.1. 1.最长公共子序列
    7. 1.14.0.7. 01背包
      1. 1.14.0.7.1. 1.分割等和子集
      2. 1.14.0.7.2. 2.目标和
      3. 1.14.0.7.3. 3.一和零
      4. 1.14.0.7.4. 4.零钱兑换
      5. 1.14.0.7.5. 5.零钱兑换 II
      6. 1.14.0.7.6. 6.单词拆分
      7. 1.14.0.7.7. 7.组合总和 Ⅳ
    8. 1.14.0.8. 股票问题
      1. 1.14.0.8.1. k=1(也可以用贪心来解决)
      2. 1.14.0.8.2. k=无穷(也可以用贪心来解决)
      3. 1.14.0.8.3. k = +infinity with cooldown
      4. 1.14.0.8.4. k = +infinity with fee
      5. 1.14.0.8.5. k=2
      6. 1.14.0.8.6. k=任意值
    9. 1.14.0.9. 字符串编辑
      1. 1.14.0.9.1. 两个字符串的删除操作
      2. 1.14.0.9.2. 编辑距离
      3. 1.14.0.9.3. 只有两个键的键盘
,