然矣
2024春招冲刺算法百题
文景色 | Ella 岚杉
  2024-04-15 00:00:00   2024-05-13 11:31:08    18.3k 字  80 分钟

前言

算法刷题之旅继续！！！

其实是被机考考得太差打击到了，不得不继续刷题

现在刷的题库「2024春招冲刺百题计划」以及会有一些每日一题和补充相应类别比较特殊重要的题目

语言是javascript，会按照题型分类刷，只记录中等及以上的题目解法，简单题一般只会记录一些特殊规律做法

真实水平是不看题解，只能做出简答题

目前还未刷完，持续更新~

模拟

54.螺旋矩阵

题目
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

解析
一层一层的回旋记录

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
/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {
    let res=[];
    if(matrix.length==0){
        return res;
    }
    let t=0,b=matrix.length-1,l=0,r=matrix[0].length-1;
    while(true){
        for(let i=l;i<=r;i++){
            res.push(matrix[t][i]);
        }
        if(++t>b)break;
        for(let i=t;i<=b;i++){
            res.push(matrix[i][r]);
        }
        if(--r<l)break;
        for(let i=r;i>=l;i--){
            res.push(matrix[b][i]);
        }
        if(--b<t)break;
        for(let i=b;i>=t;i--){
            res.push(matrix[i][l]);
        }
        if(++l>r)break;
    }
    return res;
};

59.螺旋矩阵Ⅱ

题目
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

解析
是前面一道题的逆过程

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} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {
    let matrix=new Array(n).fill(0).map(()=>new Array(n).fill(0));
    let t=0,b=n-1,l=0,r=n-1;
    let e=1;
    while(e<=n*n){
        for(let i=l;i<=r;i++){
            matrix[t][i]=e++;
        }
        ++t;
        for(let i=t;i<=b;i++){
            matrix[i][r]=e++;
        }
        --r;
        for(let i=r;i>=l;i--){
            matrix[b][i]=e++;
        }
        --b;
        for(let i=b;i>=t;i--){
            matrix[i][l]=e++;
        }
        ++l;
    }
    return matrix;
};

289.生命游戏

题目
给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为 活细胞 （live），或 0 即为 死细胞 （dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。

解析
这里有坑，如果直接在原数组上更新，会导致出错，因为每一次更新是所有节点同时更新，依赖的是上一轮的状态，如果挨个挨个更新，会导致前面更新后的状态影响后续节点更新。如果把原数组复制一遍，额外使用的空间过多

减少空间使用的方法是用额外的状态来标识节点情况

本题可以简化成四种判断条件，用二进制位来表示，1代表活，0代表死，最后一位是更新前的状态，倒数第二位是更新后的状态，后面变化状态只需要右移一位

  • 原来是活的，最后是活的 11
  • 原来是活的，最后是死的 01
  • 原来是死的，最后是活的 10
  • 原来是死的，最后是死的 00

我的状态belike：原来是死的，最后是死的

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
/**
 * @param {number[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var gameOfLife = function(board) {
    const neighbors=[0,-1,1];
    let rows=board.length,cols=board[0].length;
    for(let i=0;i<rows;i++){
        for(let j=0;j<cols;j++){
            let live=0;
            for(let m=0;m<3;m++){
                for(let n=0;n<3;n++){
                    if(!(neighbors[n]==0&&neighbors[m]==0)){
                        let r=i+neighbors[n];
                        let c=j+neighbors[m];
                        if(r<rows&&r>=0&&c<cols&&c>=0){
                            live+=1&board[r][c];
                        }
                    }
                }
            }
            if(board[i][j]==1){
                board[i][j]+=(live==2||live==3)?2:0;
            }else{
                board[i][j]+=(live==3)?2:0;
            }

        }
    }
    for(let i=0;i<rows;i++){
        for(let j=0;j<cols;j++){
            board[i][j]>>=1;
        }}
};

48.旋转图像

题目
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

解析

先上下翻转，再对角线翻转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var rotate = function(matrix) {
    const n = matrix.length;
    // 水平翻转
    for (let i = 0; i < Math.floor(n / 2); i++) {
        for (let j = 0; j < n; j++) {
            [matrix[i][j], matrix[n - i - 1][j]] = [matrix[n - i - 1][j], matrix[i][j]];
        }
    }
    // 主对角线翻转
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
        }
    }
};

1515.换水问题

题目

超市正在促销，你可以用 numExchange 个空水瓶从超市兑换一瓶水。最开始，你一共购入了 numBottles 瓶水。

如果喝掉了水瓶中的水，那么水瓶就会变成空的。

给你两个整数 numBottles 和 numExchange ，返回你 最多 可以喝到多少瓶水。

解析

小学的我薄纱大学的我

本题是简单题，换水过程相当于每一次换水损失numExchange个瓶子，但得到一个瓶子，总损失量numExchange-1，保证到最后累计拥有的瓶子减去损失瓶子不足以再换就行
numBottles-n(numExchange-1)<numExchange

1
2
3
var numWaterBottles = function(numBottles, numExchange) {
    return numBottles >= numExchange ? Math.floor((numBottles - numExchange) / (numExchange - 1)) + 1 + numBottles : numBottles;
};

栈

94.二叉树中序遍历(非递归)

题目
给定一个二叉树的根节点 root ，返回 它的 中序 遍历

解析
递归很简单，这里用迭代和莫里斯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//迭代
var inorderTraversal = function(root) {
    const res = [];
    const stk = [];
    while (root || stk.length) {
        //先找到最左节点，依次入栈
        while (root) {
            stk.push(root);
            root = root.left;
        }
        //挨个出栈，按照左中右的顺序push进res
        root = stk.pop();
        res.push(root.val);
        root = root.right;
    }
    return res;
};

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 inorderTraversal = function(root) {
    const res = [];
    let predecessor = null;

    while (root) {
        if (root.left) {
            // predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
            predecessor = root.left;
            while (predecessor.right && predecessor.right !== root) {
                predecessor = predecessor.right;
            }

            // 让 predecessor 的右指针指向 root，继续遍历左子树
            if (!predecessor.right) {
                predecessor.right = root;
                root = root.left;
            }
            // 说明左子树已经访问完了，我们需要断开链接
            else {
                res.push(root.val);
                predecessor.right = null;
                root = root.right;
            }
        }
        // 如果没有左孩子，则直接访问右孩子
        else {
            res.push(root.val);
            root = root.right;
        }
    }

    return res;
};

2007.从双倍数组中还原原数组

题目
一个整数数组 original 可以转变成一个 双倍 数组 changed ，转变方式为将 original 中每个元素 值乘以 2 加入数组中，然后将所有元素 随机打乱 。

给你一个数组 changed ，如果 change 是 双倍 数组，那么请你返回 original数组，否则请返回空数组。original 的元素可以以 任意 顺序返回。

解析

  1. O(nlogn)
    这个做法主要是先排序，保证在遍历changed数组时先遇到的一定是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
var findOriginalArray = function(changed) {
    if(changed.length%2==1){
        return [];
    }
    changed.sort((a, b) => a - b);
    const count = {};
    for (const num of changed) {
        count[num] = (count[num] || 0) + 1;
    }
    const res = [];
    for (const a of changed) {
        if (count[a] === 0) {
            continue;
        }
        count[a]--;
        if (!count[a * 2]) {
            return [];
        }
        count[a * 2]--;
        res.push(a);
    }
    return res;
};

  1. O(n)

很巧妙的消消乐思路，不用排序

举个例子就是 1,2,3,6,8,16。用1消掉2,3消掉6,8消掉16，只要当前x对应的在数组里就先跳过，等到不在数组就查找2x是否在数组里，在的话一起消掉

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 findOriginalArray = function(changed) {
    if(changed.length%2==1){
        return [];
    }
     const cnt = new Map();
    for (const x of changed) {
        cnt.set(x, (cnt.get(x) ?? 0) + 1);
    }

    // 单独处理 0
    const cnt0 = cnt.get(0) ?? 0;
    if (cnt0 % 2) {
        return [];
    }
    cnt.delete(0);
    const ans = Array(cnt0 / 2).fill(0);

    for (let x of cnt.keys()) {
        // 如果 x/2 在 cnt 中，则跳过
        if (cnt.has(x / 2)) {
            continue;
        }
        // 把 x, 2x, 4x, 8x, ... 全部配对
        while (cnt.has(x)) {
            // 每次循环，把 cntX 个 x 和 cntX 个 2x 配对
            const cntX = cnt.get(x);
            const cnt2x = cnt.get(x * 2) ?? 0;
            // 无法配对，至少要有 cntX 个 2x
            if (cntX > cnt2x) {
                return [];
            }
            ans.push(...Array(cntX).fill(x));
            if (cntX < cnt2x) {
                // 还剩下一些 2x
                cnt.set(x * 2, cnt2x - cntX);
                x *= 2;
            } else {
                x *= 4;
            }
        }
    }
    return ans;
};

402.移掉k位数字

题目
给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

解析

贪心+单调栈

如果只删一个数，一定是删除从左往右第一个比下一个数大的数，最终能得到的数最小。给定一个长度为 n 的数字序列 ，从左往右找到第一个位置 i（i>0）使得 ，并删去 ；如果不存在，说明整个数字序列单调不降，删去最后一个数字即可。

然后再对剩下的序列继续删除一个数，直到删除了k次

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 removeKdigits = function(num, k) {
    const stk = [];
    for (const digit of num) {
        while (stk.length > 0 && stk[stk.length - 1] > digit && k) {
            stk.pop();
            k -= 1;
        }
        stk.push(digit);
    }

    for (; k > 0; --k) {
        stk.pop();
    }

    let ans = "";
    let isLeadingZero = true;
    for (const digit of stk) {
        if (isLeadingZero && digit === '0') {
            continue;
        }
        isLeadingZero = false;
        ans += digit;
    }
    return ans === "" ? "0" : ans;
};

316.去除重复字母

题目
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

解析

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 removeDuplicateLetters = function(s) {
    const vis = new Array(26).fill(0);
    const num = _.countBy(s);
    
    const sub = new Array();
    for (let i = 0; i < s.length; i++) {
        const ch = s[i];
        //ascll码的妙用
        if (!vis[ch.charCodeAt() - 'a'.charCodeAt()]) {
            while (sub.length > 0 && sub[sub.length - 1] > ch) {
                if (num[sub[sub.length - 1]] > 0) {
                    vis[sub[sub.length - 1].charCodeAt() - 'a'.charCodeAt()] = 0;
                    sub.pop();
                } else {
                    break;
                }
            }
            vis[ch.charCodeAt() - 'a'.charCodeAt()] = 1;
            sub.push(ch);
        }
        num[ch]--;
    }
    return sub.join('');
};

321.拼接最大数

题目
给你两个整数数组 nums1 和 nums2，它们的长度分别为 m 和 n。数组 nums1 和 nums2 分别代表两个数各位上的数字。同时你也会得到一个整数 k。

请你利用这两个数组中的数字中创建一个长度为 k <= m + n 的最大数，在这个必须保留来自同一数组的数字的相对顺序。

返回代表答案的长度为 k 的数组。

解析

本题的思路是两个数组都返回一个保持原数组顺序的从大到小的单调栈，然后两个单调栈进行合并，保证相对顺序不变和位数限制k的情况下最大的数

但是跟普通的单调栈又有区别，就是单调栈内的元素不是全部有序的！因为限制了单调栈返回的元素，其实就是数组里有序的数量小于数组应该返回的数量，这个时候为了达到数量，后面的元素直接入栈，类似在有序元素后面拼接无序元素凑数

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
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number} k
 * @return {number[]}
 */
var maxNumber = function(nums1, nums2, k) {
    const m = nums1.length, n = nums2.length;
    const maxSubsequence = new Array(k).fill(0);
    let start = Math.max(0, k - n), end = Math.min(k, m);
    for (let i = start; i <= end; i++) {
        const subsequence1 = new MaxSubsequence(nums1, i);
        const subsequence2 = new MaxSubsequence(nums2, k - i);
        const curMaxSubsequence = merge(subsequence1, subsequence2);
        if (compare(curMaxSubsequence, 0, maxSubsequence, 0) > 0) {
            maxSubsequence.splice(0, k, ...curMaxSubsequence);
        }
    }
    return maxSubsequence;
};

var MaxSubsequence = function(nums, k) {
    const length = nums.length;
    const stack = new Array(k).fill(0);
    let top = -1;
    let remain = length - k;
    for (let i = 0; i < length; i++) {
        const num = nums[i];
        while (top >= 0 && stack[top] < num && remain > 0) {
            top--;
            remain--;
        }
        if (top < k - 1) {
            stack[++top] = num;
        } else {
            remain--;
        }
    }
    return stack;
}

const merge = (subsequence1, subsequence2) => {
    const x = subsequence1.length, y = subsequence2.length;
    if (x === 0) {
        return subsequence2;
    }
    if (y === 0) {
        return subsequence1;
    }
    const mergeLength = x + y;
    const merged = new Array(mergeLength).fill(0);
    let index1 = 0, index2 = 0;
    for (let i = 0; i < mergeLength; i++) {
        if (compare(subsequence1, index1, subsequence2, index2) > 0) {
            merged[i] = subsequence1[index1++];
        } else {
            merged[i] = subsequence2[index2++];
        }
    }
    return merged;
}

const compare = (subsequence1, index1, subsequence2, index2) => {
    const x = subsequence1.length, y = subsequence2.length;
    while (index1 < x && index2 < y) {
        const difference = subsequence1[index1] - subsequence2[index2];
        if (difference !== 0) {
            return difference;
        }
        index1++;
        index2++;
    }
    return (x - index1) - (y - index2);
}

队列

857.雇佣k名工人的最低成本

题目
有 n 名工人。 给定两个数组 quality 和 wage ，其中，quality[i] 表示第 i 名工人的工作质量，其最低期望工资为 wage[i] 。

现在我们想雇佣 k 名工人组成一个工资组。在雇佣 一组 k 名工人时，我们必须按照下述规则向他们支付工资：

对工资组中的每名工人，应当按其工作质量与同组其他工人的工作质量的比例来支付工资。
工资组中的每名工人至少应当得到他们的最低期望工资。
给定整数 k ，返回 组成满足上述条件的付费群体所需的最小金额 。在实际答案的 10-5 以内的答案将被接受。

解析

假设我们已经选择了某一个工资组，组成成员为 [h1,h2,⋯ ,hk]，其中 hi表示第 hi个工人，整个工作组的总工作质量为：totalq，总的支付金额为 totalc。那么按照题目的要求对于任意工人 hi要满足： 即： 所以当某一个工资组的总工作质量固定时，最少的付费金额只与工资组中 有关

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[]} quality
 * @param {number[]} wage
 * @param {number} k
 * @return {number}
 */
var mincostToHireWorkers = function(quality, wage, k) {
    const n=quality.length;
    const arr=new Array(n).fill(0).map((_,i)=>i);
    //也可以const arr=[...Array(n).keys()];
    //arr里存储的是工资质量比从小到大的下标
    //这样保证了后面相乘的时候当前的比一定是最大的
    arr.sort((a,b)=>{
        return wage[a]*quality[b]-wage[b]*quality[a];
    });
    let res=1e9;
    let totalq=0.0;
    //最大堆是按照quality大小来的，尽量留下总quality最小的k个
    const pq=new MaxPriorityQueue();
    for(let i=0;i<k-1;i++){
        totalq+=quality[arr[i]];
        pq.enqueue(quality[arr[i]]);
    }
    for(let i=k-1;i<n;i++){
        totalq+=quality[arr[i]];
        pq.enqueue(quality[arr[i]]);
        const totalc=wage[arr[i]]/quality[arr[i]]*totalq;
        res=Math.min(res,totalc);
        totalq-=pq.dequeue().element;
    }
    return res;
};

2071.你可以安排的最多任务数目

题目

给你 n 个任务和 m 个工人。每个任务需要一定的力量值才能完成，需要的力量值保存在下标从 0 开始的整数数组 tasks 中，第 i 个任务需要 tasks[i] 的力量才能完成。每个工人的力量值保存在下标从 0 开始的整数数组 workers 中，第 j 个工人的力量值为 workers[j] 。每个工人只能完成 一个 任务，且力量值需要 大于等于 该任务的力量要求值（即 workers[j] >= tasks[i] ）。

除此以外，你还有 pills 个神奇药丸，可以给 一个工人的力量值 增加 strength 。你可以决定给哪些工人使用药丸，但每个工人 最多 只能使用 一片 药丸。

给你下标从 0 开始的整数数组tasks 和 workers 以及两个整数 pills 和 strength ，请你返回 最多 有多少个任务可以被完成。

解析

堆

264.丑数Ⅱ

题目
给你一个整数 n ，请你找出并返回第 n 个 丑数 。
丑数 就是质因子只包含 2、3 和 5 的正整数。

解析

我的代码也很丑陋

  1. 最小堆
    初始时堆为空，现将最小丑数1加入堆，然后每次取出堆顶元素x，把2x,3x,5x入堆，然后不断循环，第n次从最小堆取出的元素就是第n个丑数
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
78
79
80
81
82
83
84
85
86
87
88
var nthUglyNumber = function(n) {
    const factors = [2, 3, 5];
    //防止重复元素
    const seen = new Set();
    const heap = new MinHeap();
    seen.add(1);
    heap.insert(1);
    let ugly = 0;
    for (let i = 0; i < n; i++) {
        ugly = heap.pop();
        for (const factor of factors) {
            const next = ugly * factor;
            if (!seen.has(next)) {
                seen.add(next);
                heap.insert(next);
            }
        }
        
    }
    return ugly;
};

// 最小堆
class MinHeap {
    constructor() {
        this.heap = [];
    }

    getParentIndex(i) {
        return (i - 1) >> 1;
    }

    getLeftIndex(i) {
        return i * 2 + 1;
    }

    getRightIndex(i) {
        return i * 2 + 2;
    }

    shiftUp(index) {
        if(index === 0) { return; }
        const parentIndex = this.getParentIndex(index);
        if(this.heap[parentIndex] > this.heap[index]){
            this.swap(parentIndex, index);
            this.shiftUp(parentIndex);
        }  
    }

    swap(i1, i2) {
        const temp = this.heap[i1];
        this.heap[i1]= this.heap[i2];
        this.heap[i2] = temp;
    }

    insert(value) {
        this.heap.push(value);
        this.shiftUp(this.heap.length - 1);
    }

    pop() {
        this.heap[0] = this.heap.pop();
        this.shiftDown(0);
        return this.heap[0];
    }

    shiftDown(index) {
        const leftIndex = this.getLeftIndex(index);
        const rightIndex = this.getRightIndex(index);
        if (this.heap[leftIndex] < this.heap[index]) {
            this.swap(leftIndex, index);
            this.shiftDown(leftIndex);
        }
        if (this.heap[rightIndex] < this.heap[index]){
            this.swap(rightIndex, index);
            this.shiftDown(rightIndex);
        }
    }

    peek() {
        return this.heap[0];
    }

    size() {
        return this.heap.length;
    }
}

  1. 动态规划

dp[i]是指第i个丑数，使用三个指针表示下一个丑数是当前指针指向的丑数乘以 2 , 3 , 5，每次都比较这三个指针乘以2,3,5之后的最小值，被选中的指针向右移动一位，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var nthUglyNumber = function(n) {
    const dp = new Array(n + 1).fill(0);
    dp[1] = 1;
    let p2 = 1, p3 = 1, p5 = 1;
    for (let i = 2; i <= n; i++) {
        const num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
        dp[i] = Math.min(Math.min(num2, num3), num5);
        if (dp[i] === num2) {
            p2++;
        }
        if (dp[i] === num3) {
            p3++;
        }
        if (dp[i] === num5) {
            p5++;
        }
    }
    return dp[n];
};

373.查找和最小的K对数字

题目
给定两个以 非递减顺序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。

定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。

请找到和最小的 k 个数对 (u1,v1), (u2,v2) … (uk,vk) 。

解析
多路并归

其实就是最小堆，但是js实现堆操作太恶心了，改用java，用现成的数据结构

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
class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>(k, (o1, o2)->{
            return nums1[o1[0]] + nums2[o1[1]] - nums1[o2[0]] - nums2[o2[1]];
        });
        List<List<Integer>> ans = new ArrayList<>();
        int m = nums1.length;
        int n = nums2.length;
        for (int i = 0; i < Math.min(m, k); i++) {
            pq.offer(new int[]{i,0});
        }
        while (k-- > 0 && !pq.isEmpty()) {
            int[] idxPair = pq.poll();
            List<Integer> list = new ArrayList<>();
            list.add(nums1[idxPair[0]]);
            list.add(nums2[idxPair[1]]);
            ans.add(list);
            if (idxPair[1] + 1 < n) {
                pq.offer(new int[]{idxPair[0], idxPair[1] + 1});
            }
        }
        
        return ans;
    }
}

诶，突然发现力扣的js环境支持最小优先队列 MinPriorityQueue 和 最大优先队列 MaxPriorityQueue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number} k
 * @return {number[][]}
 */
var kSmallestPairs = function (nums1, nums2, k) {
    const res = [];
    const pq = new MinPriorityQueue({ compare: (a, b) => nums1[a[0]] + nums2[a[1]] - (nums1[b[0]] + nums2[b[1]]) });

    for (let i = 0; i < Math.min(k, nums1.length);  i++) pq.enqueue([i, 0]);

    while (res.length < k && pq.size()) {
        const [i, j] = pq.dequeue();
        if (j + 1 < nums2.length) pq.enqueue([i, j + 1]);
        res.push([nums1[i], nums2[j]]);
    }

    return res;
};


双指针

88.合并两个有序数组(不用额外空间)

题目
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

解析
创建一个额外空间数组很简单，但是不使用额外空间的思路挺有意思，是逆向双指针，从后往前比较，放到nums1的尾部，这样就不会出现从前往后的覆盖问题

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[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    let p1=m-1,p2=n-1;
    let cur=m+n-1;
    while(p1>=0||p2>=0){
        if(p1==-1){
            cur=nums2[p2--];
        }else if(p2==-1){
            cur=nums1[p1--];
        }else if(nums1[p1]>nums2[p2]){
            cur=nums1[p1--];
        }else {
            cur=nums2[p2--];
        }
        nums1[p1+p2+2]=cur;
    }
};

31.下一个排列

题目
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

解析

从后往前遍历，让遇到的第一个nums[i] < nums[i + 1]与遇到的第一个nums[j] > nums[i]互换位置(这里j一定在[i+1,len-1)里面)，然后[i+1,len-1)倒序排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function (nums) {
    const len = nums.length;
    let i = len - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    let j = len - 1;
    if (i >= 0) {
        while (j >= 0 && nums[j] <= nums[i]) {
            j--;
        }
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    let l = i + 1, r = len - 1;
    while (l < r) {
        [nums[l++], nums[r--]] = [nums[r], nums[l]];
    }
};

滑动窗口

1052.爱生气的书店老板

题目
有一个书店老板，他的书店开了 n 分钟。每分钟都有一些顾客进入这家商店。给定一个长度为 n 的整数数组 customers ，其中 customers[i] 是在第 i 分钟开始时进入商店的顾客数量，所有这些顾客在第 i 分钟结束后离开。

在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。

当书店老板生气时，那一分钟的顾客就会不满意，若老板不生气则顾客是满意的。

书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 minutes 分钟不生气，但却只能使用一次。

请你返回 这一天营业下来，最多有多少客户能够感到满意 。

解析
经典滑动窗口，维护一个长度为 minutes 的滑动窗口。当滑动窗口从下标范围 [i−minutes,i−1] 移动到下标范围 [i−minutes+1,i] 时，下标 i−minutesi 从窗口中移出，下标 i 进入到窗口内

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[]} customers
 * @param {number[]} grumpy
 * @param {number} minutes
 * @return {number}
 */
var maxSatisfied = function(customers, grumpy, minutes) {
    let total=0;
    const len=customers.length;
    for(let i=0;i<len;i++){
        if(grumpy[i]==0){
            total+=customers[i];
        }
    }
    let increase=0;
    for(let i=0;i<minutes;i++){
        //注意这里求的是生气后不满意的顾客数
        increase+=customers[i]*grumpy[i];
    }
    let max=increase;
    for(let i=minutes;i<len;i++){
        increase=increase-customers[i-minutes]*grumpy[i-minutes]+customers[i]*grumpy[i];
        max=Math.max(increase,max);
    }
    return total+max;
};S

187.重复的DNA序列

题目
DNA序列 由一系列核苷酸组成，缩写为 ‘A’, ‘C’, ‘G’ 和 ‘T’.。

例如，”ACGAATTCCG” 是一个 DNA序列 。
在研究 DNA 时，识别 DNA 中的重复序列非常有用。

给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。

解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {string} s
 * @return {string[]}
 */
var findRepeatedDnaSequences = function(s) {
    let res=[];
    let cnt=new Map();
    for(let i=0;i<=s.length-10;i++){
        const sub=s.slice(i,i+10);
        cnt.set(sub,(cnt.get(sub)||0)+1);
        if(cnt.get(sub)===2){
            res.push(sub);
        }
    }
    return res;
};

480.滑动窗口中位数

题目
中位数是有序序列最中间的那个数。如果序列的长度是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。

例如：

[2,3,4]，中位数是 3
[2,3]，中位数是 (2 + 3) / 2 = 2.5
给你一个数组 nums，有一个长度为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。

解析
这个题用javascript简直是灾难，因为js内置的MaxPriorityQueue和MinPriorityQueue处理不了大数，自己建堆不仅麻烦还会超时，我真是服了

尽管如此，我还是觉得这个解题思路值得学一下，尽管js永远无法解决

双堆和延迟删除。使用最大堆存放窗口中较小的部分，使用最大堆存放窗口中较小的部分，那么两个堆的堆顶配合窗口的奇偶性可以推出中位数。

窗口每次移动，就比较左右边界和两个堆顶元素的情况，由于要保证两个堆里元素个数平衡，用balance记录大小堆更新元素后的平衡情况。有三种可能，增和删在同一个堆里，balance为0；small增big减，balance为2；big增small减，balance为-2。不平衡的话就从多的堆顶弹出，推入少的堆里。

这里注意在堆里不好实现删除，所以用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
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
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var medianSlidingWindow = function (nums, k) {
    const small = new MaxPriorityQueue(); // 使用最大堆存放窗口中较小的部分
    const big = new MinPriorityQueue(); // 使用使用最大堆存放窗口中较小的部分最小堆存放窗口中较大的部分
    const mp = new Map(); // 使用 Map 存放元素及其出现次数

    function getMedian() {
        if (small.size() > big.size()) {
            return small.front().element;
        } else {
            return (small.front().element+ big.front().element)/ 2.0;
        }
    }

    // 初始化小顶堆
    for (let i = 0; i < k; i++) {
        small.enqueue(nums[i]);
    }
    // 调整使得 small 和 big 保持平衡
    for (let i = 0; i < Math.floor(k / 2); i++) {
        big.enqueue(small.dequeue().element);
    }

    const ans = [getMedian()]; // 存放结果

    for (let i = k; i < nums.length; i++) {
        let balance = 0;
        const l = nums[i - k];
        mp.set(l, (mp.get(l) || 0) + 1);
        if (!small.isEmpty() && l <= small.front().element) {
            balance--;
        } else {
            balance++;
        }
        if (!small.isEmpty() && nums[i] <= small.front().element) {
            small.enqueue(nums[i]);
            balance++;
        } else {
            big.enqueue(nums[i]);
            balance--;
        }
        if (balance > 0) {
            big.enqueue(small.dequeue().element);
        }
        if (balance < 0) {
            small.enqueue(big.dequeue().element);
        }
        while (!small.isEmpty() && mp.get(small.front().element) > 0) {
            mp.set(small.front().element, mp.get(small.front().element) - 1);
            small.dequeue();
        }
        while (!big.isEmpty() && mp.get(big.front().element) > 0) {
            mp.set(big.front().element, mp.get(big.front().element) - 1);
            big.dequeue();
        }
        ans.push(getMedian());
    }
    return ans;

};

1652. 拆炸弹

题目
你有一个炸弹需要拆除，时间紧迫！你的情报员会给你一个长度为 n 的 循环 数组 code 以及一个密钥 k 。

为了获得正确的密码，你需要替换掉每一个数字。所有数字会 同时 被替换。

如果 k > 0 ，将第 i 个数字用 接下来 k 个数字之和替换。
如果 k < 0 ，将第 i 个数字用 之前 k 个数字之和替换。
如果 k == 0 ，将第 i 个数字用 0 替换。
由于 code 是循环的， code[n-1] 下一个元素是 code[0] ，且 code[0] 前一个元素是 code[n-1] 。

给你 循环 数组 code 和整数密钥 k ，请你返回解密后的结果来拆除炸弹！

解析
题目不难，值得注意的点在于可以创建一个两倍长度的数组来表示循环数组上

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 {number[]} code
 * @param {number} k
 * @return {number[]}
 */
var decrypt = function(code, k) {
    const n = code.length;
    if (k === 0) {
        return new Array(n).fill(0);
    }
    const res = new Array(n).fill(0);
    const newCode = new Array(n * 2).fill(0).map((_, idx) => {
        return code[idx % code.length];
    });
    code = newCode;
    let l = k > 0 ? 1 : n + k;
    let r = k > 0 ? k : n - 1;
    let w = 0;
    for (let i = l; i <= r; i++) {
        w += code[i];
    }
    for (let i = 0; i < n; i++) {
        res[i] = w;
        w -= code[l];
        w += code[r + 1];
        l++;
        r++;
    }
    return res;
};

链表

2.两数相加

题目
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

解析

这个题使用链表存储数字的每一位，数字的低位到高位是链表从右到左的顺序，所以是逆序，要注意进位的问题

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
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2) {
    let head = null, tail = null;
    let carry = 0;
    while (l1 || l2) {
        const n1 = l1 ? l1.val : 0;
        const n2 = l2 ? l2.val : 0;
        const sum = n1 + n2 + carry;
        carry = Math.floor(sum / 10);
        if (!head) {
            head = tail = new ListNode(sum % 10);
        } else {
            tail.next = new ListNode(sum % 10);
            tail = tail.next;
        }
        if (l1) l1 = l1.next;
        if (l2) l2 = l2.next;
    }
    if(carry>0){
        tail.next=new ListNode(carry);
    }
    return head;
};

树

230.二叉搜索树中第k小的元素

题目
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

解析

  1. 中序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var kthSmallest = function (root, k) {
    const stack = [];
    while (root != null || stack.length) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        root=stack.pop();
        k--;
        if(k==0){
            break;
        }
        root=root.right;
    }
    return root.val;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
var kthSmallest = function (root, k) {
    const list = [];
    const dfs=(node)=>{
        if(node==null){
            return;
        }
        dfs(node.left);
        list.push(node.val);
        dfs(node.right);
    }
    dfs(root);
    return list[k-1];
};
  1. AVL
    官方题解写了个平衡二叉搜索树 我愿称之为屎山代码
    本题属实是大材小用了

102.二叉树的层序遍历

题目
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

解析
层序遍历往往用bfs来做，注意要把每一层单独提取出来

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
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if(!root)return[];
    let q=[];
    let res=[];
    q.push(root);
    while(q.length){
        let len=q.length;
        let level=[];
        //跟普通bfs的差异在于把每一层单独提出来了
        while(len--){
            const node=q.shift();
            level.push(node.val);
            if(node.left!=null){
                q.push(node.left);
            }
            if(node.right!=null){
                q.push(node.right);
            }
        }
        res.push(level);
    }
    return res;
};

103.二叉树的锯齿形层序遍历

题目
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

解析
不是双端写不起而是reverse更有性价比

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
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function(root) {
if(!root)return[];
    let q=[];
    let res=[];
    let reverse=false;
    q.push(root);
    while(q.length){
        let len=q.length;
        let level=[];
        //跟普通bfs的差异在于把每一层单独提出来了
        while(len--){
            const node=q.shift();
            level.push(node.val);
            if(node.left!=null){
                q.push(node.left);
            }
            if(node.right!=null){
                q.push(node.right);
            }
        }
        res.push(reverse==true?level.reverse():level);
        reverse=!reverse;
    }
    return res;
};

高级数据结构

200.岛屿数量

题目
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围

解析

这不就是广州大学城

dfs或者bfs都可以

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 {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
    let vis = new Array(grid.length).fill().map(() => new Array(grid[0].length).fill(0));
    const dfs = (curx, cury) => {
        if (curx < 0 || curx >= grid.length || cury < 0 || cury >= grid[0].length || grid[curx][cury] == 0) return;
        grid[curx][cury] = 0;
        dfs(curx + 1, cury);
        dfs(curx, cury + 1);
        dfs(curx - 1, cury);
        dfs(curx, cury - 1);


    }
    let res = 0;
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            if (grid[i][j] == 1) {
                res++;
                dfs(i, j);
            }
        }
    }
    return res;
};

图

并查集

prim算法

最小生成树算法，即所有节点权值和最小的连通子图

  1. 初始化minDist数组(最大值)，用于记录每一个节点到最小生成树的最短路径，随便选一个节点作为最小生成树，更新最小生成树相邻节点对应的minDist数组值
  2. 选择离最小生成树最近的节点加入最小生成树，更新最小生成树相邻节点对应的minDist数组值
  3. 重复循环2，直至遍历完

kruskal算法

Dijkstra

很伤心，华为机考的时候只懂大概原理，还不会手撕代码，卡条件了直接寄

在有权图（权值非负数）中求从起点到其他节点的最短路径算法

朴素版本步骤

  1. 初始化minDist数组(最大值)，用于记录起始点到其他节点的最短路径，与起始点相邻的节点先更新对应的minDist数组值
  2. 选择离起始点最近且未被访问过的节点，该结点被标记访问过
  3. 从新节点出发，更新与新节点相邻的节点minDist数组值
  4. 重复循环23，直至遍历完

优化堆版本步骤

743.网络延迟时间

题目
有 n 个网络节点，标记为 1 到 n。

给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。

现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

解析

3123.最短路径中的边

题目
给你一个 n 个节点的无向带权图，节点编号为 0 到 n - 1 。图中总共有 m 条边，用二维数组 edges 表示，其中 edges[i] = [ai, bi, wi] 表示节点 ai 和 bi 之间有一条边权为 wi 的边。

对于节点 0 为出发点，节点 n - 1 为结束点的所有最短路，你需要返回一个长度为 m 的 boolean 数组 answer ，如果 edges[i] 至少 在其中一条最短路上，那么 answer[i] 为 true ，否则 answer[i] 为 false 。

请你返回数组 answer 。

注意，图可能不连通。

解析

207.课程表

题目
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

解析

递归

搜索

dfs

通常都是递归，在遍历树和图的所有节点时往往比bfs更简洁、空间复杂度更低

代码框架

1
2
3
4
5
6
7
8
9
10
11
12
13
function dfs(参数) {
    if (终止条件，往往是搜到底了，判断当前是否为null) {
        存放结果;
        return;
    }

    for (选择：本节点所连接的其他节点) {
        处理节点;
        dfs(图，选择的节点); // 递归
        回溯，撤销处理结果
    }
}

bfs

通常是使用额外队列来遍历，遍历顺序和dfs是不同的

在层序遍历和最短路径(无权，带权值dijkstra)的场景下，往往只能用bfs

代码框架（以网格结构为例，可以上下左右延伸）

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
// 表示四个方向
const direction = [[0, -1], [-1, 0], [0, 1], [1, 0]]; 
// grid 是地图，也就是一个二维数组
// visited标记访问过的节点，不要重复访问
// x,y 表示开始搜索节点的下标
//表示层数
let level=0;
function bfs(grid, visited,  x,  y) {
    let que=[]; // 定义队列
    que.push([x, y]); // 起始节点加入队列
    visited[x][y] = true; // 只要加入队列，立刻标记为访问过的节点
    while(que.length) { // 开始遍历队列里的元素
        let len = queue.length;
        //如果考虑层数，一定要注意把queue当前的长度抽取出来
        while (len--) {
            let cur = queue.shift();// 从队列取元素
            let curx = cur[0];
            let cury = cur[y]; // 当前节点坐标
            for (dir of direction) { // 当前节点的四个方向左右上下去遍历
                let nextx = curx + dir[0];
                let nexty = cury + dir[1]; // 获取周边四个方向的坐标
                if (nextx < 0 || nextx >= grid.length() || nexty < 0 || nexty >= grid[0].length()) continue;  // 坐标越界了，直接跳过
                if (!visited[nextx][nexty]) { // 如果节点没被访问过
                    que.push([nextx, nexty]);  // 队列添加该节点为下一轮要遍历的节点
                    visited[nextx][nexty] = true; // 只要加入队列立刻标记，避免重复访问
                }
            }
        }
        level++;
    }
    
}

回溯(类似dfs)

1
2
3
4
5
6
7
8
9
10
11
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

39.组合总和

题目
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个

解析

第一反应误以为是背包了，但其实是不同的，用回溯更简单。回溯一般终止条件是对树的层数做限制，这里不限制重复，所以终止条件是和大于等于target

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[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    let res=[],path=[],len=candidates.length;
    //因为会重复，先排序再剪枝
    candidates.sort((a,b)=>a-b);
    const backtracking=(target,idx)=>{
        if(target==0){
            res.push([...path]);
            return;
        }
        for(let i=idx;i<len;i++){
            const num=candidates[i];
            if(target-num<0)break;
            path.push(num);
            target-=num;
            //关键在这里，因为不限制重复，所以传当前索引
            backtracking(target,i);
            path.pop();
            target+=num;
        }
    }
    backtracking(target,0);
    return res;
};

924.尽量减少恶意软件的传播

题目
给出了一个由 n 个节点组成的网络，用 n × n 个邻接矩阵图 graph 表示。在节点网络中，当 graph[i][j] = 1 时，表示节点 i 能够直接连接到另一个节点 j。

一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。

假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。

如果从 initial 中移除某一节点能够最小化 M(initial)， 返回该节点。如果有多个节点满足条件，就返回索引最小的节点。

请注意，如果某个节点已从受感染节点的列表 initial 中删除，它以后仍有可能因恶意软件传播而受到感染。

解析

并查集+bfs/dfs，本质上是找到一个最大连通块且只包含一个感染节点

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 minMalwareSpread = function(graph, initial) {
    const st = new Set(initial);
    const vis = Array(graph.length).fill(false);
    //这里用nodeID来记录连通块的状态nodeId为-1是初始状态，x表示当前连通块里的感染节点下标，-2代表有多个感染节点
    let nodeId, size;
    function dfs(x) {
        vis[x] = true;
        size++;
        // 按照状态机更新 nodeId
        if (nodeId !== -2 && st.has(x)) {
            nodeId = nodeId === -1 ? x : -2;
        }
        for (let y = 0; y < graph[x].length; y++) {
            if (graph[x][y] === 1 && !vis[y]) {
                dfs(y);
            }
        }
    }

    let ans = -1;
    let max_size = 0;
    for (const x of initial) {
        if (vis[x]) {
            continue;
        }
        nodeId = -1;
        size = 0;
        dfs(x);
        if (nodeId >= 0 && (size > max_size || size === max_size && nodeId < ans)) {
            ans = nodeId;
            max_size = size;
        }
    }
    return ans < 0 ? Math.min(...initial) : ans;
};


928.尽量减少恶意软件的传播II

题目
给出了一个由 n 个节点组成的网络，用 n × n 个邻接矩阵图 graph 表示。在节点网络中，当 graph[i][j] = 1 时，表示节点 i 能够直接连接到另一个节点 j。

一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。

假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。

我们可以从 initial 中删除一个节点，并完全移除该节点以及从该节点到任何其他节点的任何连接。

请返回移除后能够使 M(initial) 最小化的节点。如果有多个节点满足条件，返回索引 最小的节点 。

解析
本题跟前面一题最大的区别在于924 是从 initial 中删除，928 是从 graph 中删除。

前一个题可以直接dfs解决，因为graph里面结点没有变化，但是本题不行，因为从graph里删除了节点，原本可以联通删除后不能联通了，所以每删除一个要重新dfs，导致复杂度很大，所以逆向思维。从不在 initial中的点 v 出发 DFS，在不经过 initial 中的节点的前提下，看看 v 是只能被一个点感染到，还是能被多个点感染到。如果 v 只能被点 x=initial[i] 感染到，那么在本次 DFS 过程中访问到的其它节点，也只能被点 x 感染到。

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
var minMalwareSpread = function(graph, initial) {
    const st = new Set(initial);
    const vis = Array(graph.length).fill(false);

    let nodeID, size;
    function dfs(x) {
        vis[x] = true;
        size++;
        for (let y = 0; y < graph[x].length; y++) {
            if (graph[x][y] === 0) {
                continue;
            }
            if (st.has(y)) {
                // 按照 924 题的状态机更新 nodeID
                // 注意避免重复统计，例如上图中的 0 有两条不同路径可以遇到 1
                if (nodeID !== -2 && nodeID !== y) {
                    nodeID = nodeID === -1 ? y : -2;
                }
            } else if (!vis[y]) {
                //对不在initial里的节点继续dfs
                dfs(y);
            }
        }
    }

    const cnt = new Map();
    for (let i = 0; i < graph.length; i++) {
        if (vis[i] || st.has(i)) {
            continue;
        }
        nodeID = -1;
        size = 0;
        dfs(i);
        if (nodeID >= 0) { // 只找到一个在 initial 中的节点
            // 删除节点 nodeId 可以让 size 个点不被感染
            //注意因为是从graph里删除了节点和所有连接，原来能连接到该节点的不一定都能在一个连通块里，所以要累积nodeID相同的连通块
            cnt.set(nodeID, (cnt.get(nodeID) ?? 0) + size);
        }
    }

    let maxCnt = 0;
    let minNodeID = 0;
    for (const [nodeID, c] of cnt) {
        if (c > maxCnt || c === maxCnt && nodeID < minNodeID) {
            maxCnt = c;
            minNodeID = nodeID;
        }
    }
    return cnt.size ? minNodeID : Math.min(...initial);
};

2385.感染二叉树需要的总时间

题目
给你一棵二叉树的根节点 root ，二叉树中节点的值 互不相同 。另给你一个整数 start 。在第 0 分钟，感染 将会从值为 start 的节点开始爆发。

每分钟，如果节点满足以下全部条件，就会被感染：

节点此前还没有感染。
节点与一个已感染节点相邻。
返回感染整棵树需要的分钟数。

解析

  1. bfs
    先把题目中的树dfs转化成图，再bfs搜索
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 {TreeNode} root
 * @param {number} start
 * @return {number}
 */
var amountOfTime = function (root, start) {
    let graph = new Map();
    const dfs = (node) => {
        if (node.left != null) {
            const child = node.left;
            //这里小细节set的时候第二项value一定要[]一下，因为插入的是数组
            graph.has(node.val) ? graph.get(node.val).push(child.val) : graph.set(node.val, [child.val]);
            graph.has(child.val) ? graph.get(child.val).push(node.val) : graph.set(child.val, [node.val]);
            dfs(child);
        }
        if (node.right != null) {
            const child = node.right;
            graph.has(node.val) ? graph.get(node.val).push(child.val) : graph.set(node.val, [child.val]);
            graph.has(child.val) ? graph.get(child.val).push(node.val) : graph.set(child.val, [node.val]);
            dfs(child);
        }
    }
    dfs(root);
    let vis = new Set();
    vis.add(start);
    let time = 0;
    let q = [];
    //注意这里不适用len = queue.length再while (len--)再time++，因为本题可能只有一个节点同时也是感染节点，会出现答案是0但结果time为1
    q.push([start, 0]);
    while (q.length) {
        const [n, t] = q.shift();
        time = t;
        if (graph.has(n)) {
            graph.get(n).forEach(item => {
                if (!vis.has(item)) {
                    q.push([item, t + 1]);
                    vis.add(item);
                }
            })
        }
    }
    return time;
};
  1. dfs
    还可以把题目转化为求树中距离目标节点最远的节点，即拆分为两个问题，一个是从目标节点往下求二叉树的最大深度；二个是去掉目标节点的所有子树，求二叉树的最大直径
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 {TreeNode} root
 * @param {number} start
 * @return {number}
 */
var amountOfTime = function (root, start) {
    let res = 0;
    const dfs = (node) => {
        if (node == null) {
            return [0, false];
        }
        let [l, lFound] = dfs(node.left);
        let [r, rFound] = dfs(node.right);
        if (node.val == start) {
            //计算start最大深度
            res = Math.max(l, r);
            return [1, true];
        }
        // 只有在左子树或右子树包含 start 时，才能更新答案
        if (lFound || rFound) {
            res = Math.max(res, l + r);
            //向上返回当前节点最大深度，但是要保证返回的是包含start的那边一边子树深度
            return [lFound ? l + 1 : r + 1, true];
        }
        return [Math.max(l, r) + 1, false];
    }
    dfs(root);
    return res;
};

529.扫雷游戏

题目

给你一个大小为 m x n 二维字符矩阵 board ，表示扫雷游戏的盘面，其中：

‘M’ 代表一个 未挖出的 地雷，
‘E’ 代表一个 未挖出的 空方块，
‘B’ 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的 已挖出的 空白方块，
数字（’1’ 到 ‘8’）表示有多少地雷与这块 已挖出的 方块相邻，
‘X’ 则表示一个 已挖出的 地雷。
给你一个整数数组 click ，其中 click = [clickr, clickc] 表示在所有 未挖出的 方块（’M’ 或者 ‘E’）中的下一个点击位置（clickr 是行下标，clickc 是列下标）。

根据以下规则，返回相应位置被点击后对应的盘面：

如果一个地雷（’M’）被挖出，游戏就结束了- 把它改为 ‘X’ 。
如果一个 没有相邻地雷 的空方块（’E’）被挖出，修改它为（’B’），并且所有和其相邻的 未挖出 方块都应该被递归地揭露。
如果一个 至少与一个地雷相邻 的空方块（’E’）被挖出，修改它为数字（’1’ 到 ‘8’ ），表示相邻地雷的数量。
如果在此次点击中，若无更多方块可被揭露，则返回盘面

解析
为了做题，第一次看懂扫雷的规则
思路蛮简单的,有三种变化情况

  1. 一来就遇到 M，直接踩雷，更新为X，游戏结束。
  2. 遍历中遇到E，再细分两种情况：
    1. 相邻 8 个节点有雷，即用于计数的count不为0，更新为count，结束当前节点的遍历。
    2. 相邻 8 个节点没有雷，即用于计数的count为0，更新为 B，并继续对当前节点的相邻节点进行遍历。

dfs就是在b情况下继续递归当前节点的相邻节点

bfs就是在b情况下把当前节点的相邻节点加入循环队列

  1. dfs
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
/**
 * @param {character[][]} board
 * @param {number[]} click
 * @return {character[][]}
 */
var updateBoard = function (board, click) {
    const directions = [[0, 1], [0, -1], [1, 0], [1, 1], [1, -1], [-1, 0], [-1, 1], [-1, -1]];
    const dfs = (x, y) => {
        let count = 0;
        for (dir of directions) {
            let curx = x + dir[0];
            let cury = y + dir[1];
            if (curx < 0 || curx >= board.length || cury < 0 || cury >= board[0].length) {
                continue;
            }
            if (board[curx][cury] == 'M') {
                count++;
            }
        }
        if (count > 0) {
            board[x][y] = count.toString();
        } else {
            board[x][y] = 'B';
            for (dir of directions) {
                let curx = x + dir[0];
                let cury = y + dir[1];
                if (curx < 0 || curx >= board.length || cury < 0 || cury >= board[0].length||board[curx][cury]!='E') {
                continue;
            }
                dfs(curx,cury);
            }
        }
    }
    if(board[click[0]][click[1]]=='M'){
        board[click[0]][click[1]]='X';
    }else{
        dfs(click[0],click[1]);
    }
    return board;
};
  1. bfs
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
/**
 * @param {character[][]} board
 * @param {number[]} click
 * @return {character[][]}
 */
var updateBoard = function (board, click) {
    const directions = [[0, 1], [0, -1], [1, 0], [1, 1], [1, -1], [-1, 0], [-1, 1], [-1, -1]];
    const bfs = (sx, sy) => {
        let queue=[];
        const vis=new Array(board.length).fill(0).map(()=>new Array(board[0].length).fill(0));
        queue.push([sx,sy]);
        vis[sx][sy]=1;
        while(queue.length){
            const [x,y]=queue.shift();
            let count = 0;
        for (dir of directions) {
            let curx = x + dir[0];
            let cury = y + dir[1];
            if (curx < 0 || curx >= board.length || cury < 0 || cury >= board[0].length) {
                continue;
            }
            if (board[curx][cury] == 'M') {
                count++;
            }
        }
        if (count > 0) {
            board[x][y] = count.toString();
        } else {
            board[x][y] = 'B';
            for (dir of directions) {
                let curx = x + dir[0];
                let cury = y + dir[1];
                if (curx < 0 || curx >= board.length || cury < 0 || cury >= board[0].length||board[curx][cury]!='E'||vis[curx][cury]==1) {
                continue;
            }
                queue.push([curx,cury]);
                vis[curx][cury]=1;
            }
        }
        }
        
    }
    if(board[click[0]][click[1]]=='M'){
        board[click[0]][click[1]]='X';
    }else{
        bfs(click[0],click[1]);
    }
    return board;
};

贪心

二分查找

开闭区间整理

直接画图先推得了，每次都卡条件，套公式不管用

注意一下二分的开闭区间问题

这里整理一下二分区间常见写法
注意具体题目中if上取等要看题意能否等于目标值

  1. [left, right]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
        while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
            int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
            if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，所以[middle + 1, right]
            } else { // nums[middle] >= target
                right=middle-1; // target 在右区间，所以[left, middle - 1]
            }
        }
        //不存在的话返回的是nums.size()和-1
        return left;
    }
  1. [left, right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int search(vector<int>& nums, int target) {
        int left = 0;
        //不存在的话返回的是nums.size()
        int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)
        while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
            //这里位运算一定一定一定要括号括起来，我这个错误被卡bug了一天
            int middle = left + ((right - left) >> 1);
            if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，在[middle + 1, right)中
            } else { // nums[middle] >= target
                right=middle; // target 在左区间，在[left, middle)中
            }
        }
        //不存在的话返回的是nums.size()和0
        return left;
    }
  1. (left, right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int search(vector<int>& nums, int target) {
        int left = -1;
        int right = nums.size(); // 定义target在左开右开的区间里，即：(left, right)
        while (lef+1 < right) { // 因为left+1 == right的时候，在(left, right)是无效的空间，所以使用 <
            //这里位运算一定一定一定要括号括起来，我这个错误被卡bug了一天
            int middle = left + ((right - left) >> 1);
            //这里一定要注意，返回的是从后往前第一个满足的，如果出现了重复元素，返回的是最后一个的位置
            if (nums[middle] < target) {
                left = middle ;// target 在右区间，在(middle, right)中
            } else {
                right = middle; // target 在左区间，在(left, middle)中
            }
        }
        //不存在的话返回的是nums.size()和-1
        return right;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int search(vector<int>& nums, int target) {
        int left = -1;
        int right = nums.size(); // 定义target在左开右开的区间里，即：(left, right)
        while (lef+1 < right) { // 因为left+1 == right的时候，在(left, right)是无效的空间，所以使用 <
            //这里位运算一定一定一定要括号括起来，我这个错误被卡bug了一天
            int middle = left + ((right - left) >> 1);
            //这里一定要注意，返回的是从前往后第一个满足的，如果出现了重复元素，返回的是第一个的位置
            if (nums[middle] <= target) {
                left = middle ;// target 在右区间，在(middle, right)中
            } else {
                right = middle; // target 在左区间，在(left, middle)中
            }
        }
        //不存在的话返回的是nums.size()和-1
        return left;
    }

436.寻找右区间

题目
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

解析

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
/**
 * @param {number[][]} intervals
 * @return {number[]}
 */
var findRightInterval = function(intervals) {
    const len=intervals.length;
    const startIntervals=new Array(len).fill(0).map(()=>new Array(2).fill(0));
    for(let i=0;i<len;i++){
        startIntervals[i][0]=intervals[i][0];
        startIntervals[i][1]=i;
    }
    startIntervals.sort((a,b)=>a[0]-b[0]);
    const res=new Array(len).fill(0);
    for(let i=0;i<len;i++){
        let left=0;
        let right=len-1;
        let target = -1;
        while(left<=right){
            const mid=left+((right-left)>>1);
            if(startIntervals[mid][0]>=intervals[i][1]){
                target = startIntervals[mid][1];
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        res[i]=target;
    }
    return res;
};

1146.快照数组

题目
实现支持下列接口的「快照数组」- SnapshotArray：

SnapshotArray(int length) - 初始化一个与指定长度相等的 类数组 的数据结构。初始时，每个元素都等于 0。
void set(index, val) - 会将指定索引 index 处的元素设置为 val。
int snap() - 获取该数组的快照，并返回快照的编号 snap_id（快照号是调用 snap() 的总次数减去 1）。
int get(index, snap_id) - 根据指定的 snap_id 选择快照，并返回该快照指定索引 index 的值。

解析

注意这里题目说的是每调用一次snap才会增加时间，所以会出现同一时间多次调用set的情况，即重复元素，因此要考虑取的是第一次snap的

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
/**
 * @param {number} length
 */
var SnapshotArray = function (length) {
    this.arr = Array.from({length},() => []);
    this.time = 0;
};

/** 
 * @param {number} index 
 * @param {number} val
 * @return {void}
 */
SnapshotArray.prototype.set = function (index, val) {
    this.arr[index].push([val, this.time]);
};

/**
 * @return {number}
 */
SnapshotArray.prototype.snap = function () {
    return this.time++;
};

/** 
 * @param {number} index 
 * @param {number} snap_id
 * @return {number}
 */
SnapshotArray.prototype.get = function (index, snap_id) {
    let l = -1, r = this.arr[index].length;
    while (l+1 < r) {
        let mid = l + ((r - l) >> 1);
        //这里小心别被重复元素坑了，要返回的是第一个
        if (this.arr[index][mid][1] <=snap_id) {
            l = mid;
        } else {
            r = mid;
        }
    }
    const id = l;
    if(id==-1||id==this.arr[index].length){
        return 0;
    }
    return this.arr[index][id][0];

};

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * var obj = new SnapshotArray(length)
 * obj.set(index,val)
 * var param_2 = obj.snap()
 * var param_3 = obj.get(index,snap_id)
 */

动态规划

背包问题归纳

现实中谁会这么算，都是乱装
让一个出门不带包的人天天算怎么装满包

  1. 类型

  • 能否装满/最多装背包(01)

    • 一维dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    • 二维dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

  • 装满背包的方法(完全/01)
    dp[j] += dp[j - nums[i]]

  • 背包能装的最大价值
    dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

  • 装满背包的物品最小个数
    dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

  1. 遍历顺序

  • 01背包

    • 二维 物品和容量内外都可以，第二层for循环是从小到大遍历
    • 一维 先物品再容量内，第二层for循环是从大到小遍历

  • 完全背包

    • 如果求组合数就是外层for循环遍历物品，内层for遍历背包。第二层for循环是从小到大遍历
    • 如果求排列数就是外层for遍历背包，内层for循环遍历物品。第二层for循环是从小到大遍历

403.青蛙过河

题目
一只青蛙想要过河。 假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。 青蛙可以跳上石子，但是不可以跳入水中。

给你石子的位置列表 stones（用单元格序号 升序 表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。开始时， 青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃 1 个单位（即只能从单元格 1 跳至单元格 2 ）。

如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1 个单位。 另请注意，青蛙只能向前方（终点的方向）跳跃。

解析

青蛙为什么不会自己游过去！

dp[i][k]表示青蛙能否达到「现在所处的石子编号」为 i 且「上一次跳跃距离」为 k 的状态

dp[i][k]=dp[j][k−1]⋁dp[j][k]⋁dp[j][k+1]
stones[i]−stones[j]=k

现在所处的石子索引为 i (不是stones[i])时，上一次跳跃距离k 必定满足 k≤i。可以这么理解，假设青蛙每次都比上一次多跳一格，石子索引为i代表跳了i次，那么k最多加到i。那么当第i个石子和第i-1个石子的距离即stones[i]−stones[i-1]>i的时候，青蛙绝对无法到达终点

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[]} stones
 * @return {boolean}
 */
var canCross = function (stones) {
    const len = stones.length;
    const dp = new Array(len).fill(0).map(() => new Array(len).fill(0));
    dp[0][0] = true;
    for (let i = 1; i < len; i++) {
        if (stones[i] - stones[i - 1] > i) {
            return false;
        }
        for (let i = 1; i < len; i++) {
            for (let j = i; j > 0; j--) {
                const k = stones[i] - stones[j - 1];
                if (k > j) {
                    break;
                }
                dp[i][k] = dp[j - 1][k - 1] || dp[j - 1][k] || dp[j - 1][k + 1];
                if (i == len - 1 && dp[i][k]) {
                    return true;
                }
            }
        }
        return false;
    }
};

494.目标和

题目
给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-‘ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

解析

  1. 回溯算法
    暴力搜索

  2. 动态规划

本题要如何使表达式结果为target，既然为target，那么就一定有 left组合 - right组合 = target，left + right = sum，而sum是固定的。right = sum - left，因此left - (sum - left) = target 推导出 left = (target + sum)/2

从而问题转变成01背包问题，装满容量为left的背包的方法

  • 一维dp(滚动数组)
    dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法，递推公式为dp[j] += dp[j - nums[i]]，注意dp[0]=1和倒序，因为dp数组被全部初始化为0，从右向左不会出现dp[j - nums[i]]覆盖了已经赋值过的数组，保证每个元素只放入一次

  • 二维dp
    dp[i][j] 表示在数组 nums 的前 i 个数中选取元素，使得这些元素之和等于 j 的方案数

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
const findTargetSumWays = (nums, target) => {
    //一维dp
    const sum = nums.reduce((a, b) => a+b);
    
    if(Math.abs(target) > sum) {
        return 0;
    }

    if((target + sum) % 2) {
        return 0;
    }

    const halfSum = (target + sum) / 2;

    let dp = new Array(halfSum+1).fill(0);
    dp[0] = 1;

    for(let i = 0; i < nums.length; i++) {
        for(let j = halfSum; j >= nums[i]; j--) {
            dp[j] += dp[j - nums[i]];
        }
    }

    return dp[halfSum];
};
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
//二维dp
var findTargetSumWays = function(nums, target) {
    let sum = 0;
    for (const num of nums) {
        sum += num;
    }
    const diff = sum - target;
    if (diff < 0 || diff % 2 !== 0) {
        return 0;
    }
    const n = nums.length, neg = diff / 2;
    const dp = new Array(n + 1).fill(0).map(() => new Array(neg + 1).fill(0));
    dp[0][0] = 1;
    for (let i = 1; i <= n; i++) {
        const num = nums[i - 1];
        for (let j = 0; j <= neg; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= num) {
                dp[i][j] += dp[i - 1][j - num];
            }
        }
    }
    return dp[n][neg];
};

70.爬楼梯(进阶)

题目
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。一步一个台阶，两个台阶，三个台阶，…….，直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢？

解析

我直接坐电梯！

原题是每次爬1个或者2个，就是斐波那契数列

现在每次可以爬m种台阶，且不限制数量，就是完全背包问题

dp[i]：爬到有i个台阶的楼顶，有dp[i]种方法

递推公式：dp[i] += dp[i - j]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function climbStairs(n) {
    /**
        一次可以爬m阶
        dp[i]: i阶楼梯的方法种数
        dp[1]: 1;
        dp[2]: 2;
        dp[3]: dp[2] + dp[1];
        ...
        dp[i]: dp[i - 1] + dp[i - 2] + ... + dp[max(i - m, 1)]; 从i-1加到max(i-m, 1)
     */
    const m = 2;    // 本题m为2
    const dp = new Array(n + 1).fill(0);
    dp[0]=1;
    dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        for (let j = 1; j <=m; j++) {
            dp[i] += dp[i-j];
        }
    }
    return dp[n];
};

377.组合总和Ⅳ

题目
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

解析
完全背包排列问题

如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。

记不住就现场举例子，计算dp[4]的时候，遍历nums（物品）放在外循环，遍历target的作为内循环的话，结果集只有 {1,3} 这样的集合，不会有{3,1}这样的集合，因为nums遍历放在外层，3只能出现在1后面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @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 = 0; i <= target; i++) {
        for(let j = 0; j < nums.length; j++) {
            if (i >= nums[j]) {
                dp[i] += dp[i - nums[j]];
            }
        }
    }

    return dp[target];
};

1235.规划兼职工作

题目
你打算利用空闲时间来做兼职工作赚些零花钱。

这里有 n 份兼职工作，每份工作预计从 startTime[i] 开始到 endTime[i] 结束，报酬为 profit[i]。

给你一份兼职工作表，包含开始时间 startTime，结束时间 endTime 和预计报酬 profit 三个数组，请你计算并返回可以获得的最大报酬。

注意，时间上出现重叠的 2 份工作不能同时进行。

如果你选择的工作在时间 X 结束，那么你可以立刻进行在时间 X 开始的下一份工作。

解析
有点类似以前做过的气球问题(无重叠区间)
用结束时间从小到大排序，使用 dp[i] 表示前 i 份兼职工作可以获得的最大报酬，区间范围[0,i−1]， k 表示满足结束时间小于等于第 i−1 份工作开始时间的兼职工作数量
dp[i]=max(dp[i−1],dp[k]+profit[i−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
var jobScheduling = function (startTime, endTime, profit) {
    const n = startTime.length;
    const arr = new Array(n).fill(0).map((_, i) => [startTime[i], endTime[i], profit[i]]);
    arr.sort((a, b) => a[1] - b[1]);
    const dp = new Array(n + 1).fill(0);

    for (let i = 1; i <= n; i++) {
        const k = binarySearch(arr, i - 1, arr[i - 1][0]);
        dp[i] = Math.max(dp[i - 1], dp[k] + arr[i - 1][2]);
    }
    return dp[n];
};
const binarySearch = (arr, r, t) => {
    let l = 0;
    //[l,r)
    while (l < r) {
        const mid = l + Math.floor((r - l) / 2);
        //同一个时间点上可以重叠，切记取等
        if (arr[mid][1] <= t) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    return l;
};

741.摘樱桃

题目
给你一个 n x n 的网格 grid ，代表一块樱桃地，每个格子由以下三种数字的一种来表示：

0 表示这个格子是空的，所以你可以穿过它。
1 表示这个格子里装着一个樱桃，你可以摘到樱桃然后穿过它。
-1 表示这个格子里有荆棘，挡着你的路。
请你统计并返回：在遵守下列规则的情况下，能摘到的最多樱桃数：

从位置 (0, 0) 出发，最后到达 (n - 1, n - 1) ，只能向下或向右走，并且只能穿越有效的格子（即只可以穿过值为 0 或者 1 的格子）；
当到达 (n - 1, n - 1) 后，你要继续走，直到返回到 (0, 0) ，只能向上或向左走，并且只能穿越有效的格子；
当你经过一个格子且这个格子包含一个樱桃时，你将摘到樱桃并且这个格子会变成空的（值变为 0 ）；
如果在 (0, 0) 和 (n - 1, n - 1) 之间不存在一条可经过的路径，则无法摘到任何一个樱桃。

解析
我第一反应是两次dp，但是错了，才意识到局部最优不等于全局最优，导致这个的原因在于规定了移动方法只能向两个方向，导致如果单次取最优，会导致下一次有些点根本无法到达

1
2
3
4
5
6
7
0:[1, 1, 1, 1, 0, 0, 0]
1:[0, 0, 0, 1, 0, 0, 0]
2:[0, 0, 0, 1, 0, 0, 1]
3:[1, 0, 0, 1, 0, 0, 0]
4:[0, 0, 0, 1, 0, 0, 0]
5:[0, 0, 0, 1, 0, 0, 0]
6:[0, 0, 0, 1, 1, 1, 1]

所以唯一的解决方案就是两次dp同时进行，求两者和的最优解

为了统计两次dp是否经过了同一个格子，将第二次dp(向上走的)等效成向下走，这样当两次dp坐标相同就代表经过同一个格子

因为如果考虑横纵坐标，状态维度太大了，进行简化。由于每一次移动都只能移动一格，同时进行的两次dp的坐标x,y之和是相等的，都是移动步数，只要两次dp横坐标相同，坐标就相同，所以把四维简化成二维。即dp[steps][x1][x2]表示两人各自都走了steps步，分别走到[x1][steps-x1]和[x2][steps-x2]，此时得到的樱桃个数的最大值

一共四种情况，取最大值
都往右：从 dp[steps−1][x1][x2]转移过来；
往下，往右：从 dp[steps−1][x1-1][x2]转移过来；
往右，往下：从 dp[steps−1][x1][x2-1]转移过来；
都往下：从 dp[steps−1][x1-1][x2-1]转移过来；

为了简化代码，可以假设第一次dp的不会走到第二次dp的下方，即x1<=x2，可以减少一半的循环次数

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
/**
 * @param {number[][]} grid
 * @return {number}
 */
var cherryPickup = function(grid) {
    const n = grid.length;
    const f = new Array(n * 2 - 1).fill(0).map(() => new Array(n).fill(0).map(() => new Array(n).fill(-Number.MAX_VALUE)));
    f[0][0][0] = grid[0][0];
    for (let k = 1; k < n * 2 - 1; ++k) {
        for (let x1 = Math.max(k - n + 1, 0); x1 <= Math.min(k, n - 1); ++x1) {
            const y1 = k - x1;
            if (grid[x1][y1] === -1) {
                continue;
            }
            for (let x2 = x1; x2 <= Math.min(k, n - 1); ++x2) {
                let y2 = k - x2;
                if (grid[x2][y2] === -1) {
                    continue;
                }
                let res = f[k - 1][x1][x2]; // 都往右
                if (x1 > 0) {
                    res = Math.max(res, f[k - 1][x1 - 1][x2]); // 往下，往右
                }
                if (x2 > 0) {
                    res = Math.max(res, f[k - 1][x1][x2 - 1]); // 往右，往下
                }
                if (x1 > 0 && x2 > 0) {
                    res = Math.max(res, f[k - 1][x1 - 1][x2 - 1]); // 都往下
                }
                res += grid[x1][y1];
                if (x2 !== x1) { // 避免重复摘同一个樱桃
                    res += grid[x2][y2];
                }
                f[k][x1][x2] = res;
            }
        }
    }
    return Math.max(f[n * 2 - 2][n - 1][n - 1], 0);
};

进一步优化维度，把dp三维优化成二维，删除steps。可以类比背包问题二维转一维，使用倒序避免覆盖问题

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 cherryPickup = function(grid) {
    const n = grid.length;
    const f = new Array(n).fill(0).map(() => new Array(n).fill(-Number.MAX_VALUE));
    f[0][0] = grid[0][0];
    for (let k = 1; k < n * 2 - 1; ++k) {
        for (let x1 = Math.min(k, n - 1); x1 >= Math.max(k - n + 1, 0); --x1) {
            for (let x2 = Math.min(k, n - 1); x2 >= x1; --x2) {
                const y1 = k - x1, y2 = k - x2;
                if (grid[x1][y1] === -1 || grid[x2][y2] === -1) {
                    f[x1][x2] = -Number.MAX_VALUE;
                    continue;
                }
                let res = f[x1][x2]; // 都往右
                if (x1 > 0) {
                    res = Math.max(res, f[x1 - 1][x2]); // 往下，往右
                }
                if (x2 > 0) {
                    res = Math.max(res, f[x1][x2 - 1]); // 往右，往下
                }
                if (x1 > 0 && x2 > 0) {
                    res = Math.max(res, f[x1 - 1][x2 - 1]); //都往下
                }
                res += grid[x1][y1];
                if (x2 !== x1) { // 避免重复摘同一个樱桃
                    res += grid[x2][y2];
                }
                f[x1][x2] = res;
            }
        }
    }
    return Math.max(f[n - 1][n - 1], 0);
};

1463.摘樱桃Ⅱ

题目

给你一个 rows x cols 的矩阵 grid 来表示一块樱桃地。 grid 中每个格子的数字表示你能获得的樱桃数目。

你有两个机器人帮你收集樱桃，机器人 1 从左上角格子 (0,0) 出发，机器人 2 从右上角格子 (0, cols-1) 出发。

请你按照如下规则，返回两个机器人能收集的最多樱桃数目：

从格子 (i,j) 出发，机器人可以移动到格子 (i+1, j-1)，(i+1, j) 或者 (i+1, j+1) 。
当一个机器人经过某个格子时，它会把该格子内所有的樱桃都摘走，然后这个位置会变成空格子，即没有樱桃的格子。
当两个机器人同时到达同一个格子时，它们中只有一个可以摘到樱桃。
两个机器人在任意时刻都不能移动到 grid 外面。
两个机器人最后都要到达 grid 最底下一行。

解析
这个题机器人走的路径就是向下的三个相邻格子，两个机器人每次移动都在同一行
状态方程可以写为dp[y][x1][x2]=max(dp[y-1][dx1][dx2]+grid[y][x1]+grid[y][x2])，dx1取值范围[x1-1,x1,x1+1]，dx2取值范围[x2-1,x2,x2+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
31
32
33
34
35
/**
 * @param {number[][]} grid
 * @return {number}
 */
var cherryPickup = function(grid) {
    const m = grid.length;
    const n = grid[0].length;

    let f = Array.from({ length: n }, () => Array(n).fill(-1));
    let g = Array.from({ length: n }, () => Array(n).fill(-1));

    f[0][n - 1] = grid[0][0] + grid[0][n - 1];
    for (let i = 1; i < m; ++i) {
        for (let j1 = 0; j1 < n; ++j1) {
            for (let j2 = 0; j2 < n; ++j2) {
                let best = -1;
                for (let dj1 = j1 - 1; dj1 <= j1 + 1; ++dj1) {
                    for (let dj2 = j2 - 1; dj2 <= j2 + 1; ++dj2) {
                        if (dj1 >= 0 && dj1 < n && dj2 >= 0 && dj2 < n && f[dj1][dj2] != -1) {
                            best = Math.max(best, f[dj1][dj2] + (j1 == j2 ? grid[i][j1] : grid[i][j1] + grid[i][j2]));
                        }
                    }
                }
                g[j1][j2] = best;
            }
        }
        [f, g] = [g, f];
    }
    let ans = 0;
    for (let j1 = 0; j1 < n; ++j1) {
        ans = Math.max(ans, Math.max(...f[j1]));
    }
    return ans;
};

位运算

这类的题目不多，但是一些小技巧不会能卡很久

异或

任何数和 0 做异或运算，结果仍然是原来的数，即 。
任何数和其自身做异或运算，结果是 0，即 。
异或运算满足交换律和结合律，即 。

Brian Kernighan 算法

经典题目338计算二进制里1的个数

对于任意整数x，令 ，该运算将x的二进制表示的最后一个1变成 0，以及后面的0都变成1，而1前面的数不会变。进行&操作之后原本最后一个1以及后面所有的0都会变成0，这样成功实现了减少一个1的目的，可以用这个方法来计数所有的1的个数

总的时间复杂度为O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {number} n
 * @return {number[]}
 */
var countBits = function (n) {
    const bits = new Array(n + 1).fill(0);
    const countOnes = (x) => {
        let ones = 0;
        while (x > 0) {
            x &= (x - 1);
            ones++;
        }
        return ones;
    }
    for (let i = 0; i < n + 1; i++) {
        bits[i] = countOnes(i);
    }
    return bits;
};

1017.负二进制转换

题目
给你一个整数 n ，以二进制字符串的形式返回该整数的 负二进制（base -2）表示。

注意，除非字符串就是 “0”，否则返回的字符串中不能含有前导零。

解析
当基数 x>1时，将整数 n 转换成 x 进制的原理是：令 ，计算过程如下:

当计算第 0 位上的数字时，此时 ，，其中 0≤r<x

当计算第 i 位上的数字时，此时 ，，其中 0≤r<x

按照上述计算方式进行计算，直到满足 结束。

如果基数 x 为负数，只要能确定余数的可能取值，上述做法同样适用。由于「负二进制」余数的可能取值是 0,1,-1，举例子5%(-2)=-3…(-1)和5%(-2)=-2…1，但是表示上没有负数，只有0和1。所有的负数表示都是补码形式，最低位奇偶性不变，做最低位&操作就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var baseNeg2 = function(n) {
    if (n === 0 || n === 1) {
        return '' + n;
    }
    let res = '';
    while (n !== 0) {
        const remainder = n & 1;
        res += remainder;
        //减去余数，其实就是把最低位抹掉，防止不能整除
        n -= remainder;
        n /= -2;
    }
    return res.split('').reverse().join('');
};

数论

gcd

最大公约数，理解辗转相除的关键在于被除数和除数有相同的因数，那么被除数和除数的余数跟它们也有一样的因数，反之亦然

1
2
3
4
5
6
7
8
function gcd(a, b) {
    while (b !== 0) {
        [a, b] = [b, a % b];
    }
    return a;
}
或者简写
const gcd = (a, b) => (b===0 ? a : gcd(b, a % b))

质数

在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数为质数，统计 [2,n] 中质数的数量

  1. 枚举
    假设x=a*b，只需要找到到a和b中较小的那一个，就可以排除x，查找范围在 之间
1
2
3
4
5
6
7
8
const prime=(x)=>{
        for(let i=2;i*i<=x;i++){
            if(x%i==0){
                return false;
            }
        }
        return true;
    }
  1. 埃氏筛

如果x是质数，那么2x,3x…一定不是质数，然后判断应该从x*x开始，因为2x,3x…x*x会被小于x的数标记，会重复

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number} n
 * @return {number}
 */
var countPrimes = function (n) {
    const isPrime = new Array(n).fill(1);
    let ans = 0;
    for (let i = 2; i < n; ++i) {
        if (isPrime[i]) {
            ans += 1;
            for (let j = i * i; j < n; j += i) {
                isPrime[j] = 0;
            }
        }
    }
    return ans;
};

2024春招冲刺算法百题
2024/04/15/春招冲刺百题/
作者
文景色 | Ella
发布于
2024-04-15 00:00
许可
 评论
评论插件加载失败
正在加载评论插件
  1. 前言
    1. 模拟
      1. 54.螺旋矩阵
      2. 59.螺旋矩阵Ⅱ
      3. 289.生命游戏
      4. 48.旋转图像
      5. 1515.换水问题
    2. 栈
      1. 94.二叉树中序遍历(非递归)
      2. 2007.从双倍数组中还原原数组
      3. 402.移掉k位数字
      4. 316.去除重复字母
      5. 321.拼接最大数
    3. 队列
      1. 857.雇佣k名工人的最低成本
      2. 2071.你可以安排的最多任务数目
    4. 堆
      1. 264.丑数Ⅱ
      2. 373.查找和最小的K对数字
    5. 双指针
      1. 88.合并两个有序数组(不用额外空间)
      2. 31.下一个排列
    6. 滑动窗口
      1. 1052.爱生气的书店老板
      2. 187.重复的DNA序列
      3. 480.滑动窗口中位数
      4. 1652. 拆炸弹
    7. 链表
      1. 2.两数相加
    8. 树
      1. 230.二叉搜索树中第k小的元素
      2. 102.二叉树的层序遍历
      3. 103.二叉树的锯齿形层序遍历
    9. 高级数据结构
      1. 200.岛屿数量
    10. 图
      1. 并查集
      2. prim算法
      3. kruskal算法
      4. Dijkstra
      5. 743.网络延迟时间
      6. 3123.最短路径中的边
      7. 207.课程表
    11. 递归
    12. 搜索
      1. dfs
      2. bfs
      3. 回溯(类似dfs)
      4. 39.组合总和
      5. 924.尽量减少恶意软件的传播
      6. 928.尽量减少恶意软件的传播II
      7. 2385.感染二叉树需要的总时间
      8. 529.扫雷游戏
    13. 贪心
    14. 二分查找
      1. 开闭区间整理
      2. 436.寻找右区间
      3. 1146.快照数组
    15. 动态规划
      1. 背包问题归纳
      2. 403.青蛙过河
      3. 494.目标和
      4. 70.爬楼梯(进阶)
      5. 377.组合总和Ⅳ
      6. 1235.规划兼职工作
      7. 741.摘樱桃
      8. 1463.摘樱桃Ⅱ
    16. 位运算
      1. 异或
      2. Brian Kernighan 算法
      3. 1017.负二进制转换
    17. 数论
      1. gcd
      2. 质数
  1. 前言
    1. 模拟
      1. 54.螺旋矩阵
      2. 59.螺旋矩阵Ⅱ
      3. 289.生命游戏
      4. 48.旋转图像
      5. 1515.换水问题
    2. 栈
      1. 94.二叉树中序遍历(非递归)
      2. 2007.从双倍数组中还原原数组
      3. 402.移掉k位数字
      4. 316.去除重复字母
      5. 321.拼接最大数
    3. 队列
      1. 857.雇佣k名工人的最低成本
      2. 2071.你可以安排的最多任务数目
    4. 堆
      1. 264.丑数Ⅱ
      2. 373.查找和最小的K对数字
    5. 双指针
      1. 88.合并两个有序数组(不用额外空间)
      2. 31.下一个排列
    6. 滑动窗口
      1. 1052.爱生气的书店老板
      2. 187.重复的DNA序列
      3. 480.滑动窗口中位数
      4. 1652. 拆炸弹
    7. 链表
      1. 2.两数相加
    8. 树
      1. 230.二叉搜索树中第k小的元素
      2. 102.二叉树的层序遍历
      3. 103.二叉树的锯齿形层序遍历
    9. 高级数据结构
      1. 200.岛屿数量
    10. 图
      1. 并查集
      2. prim算法
      3. kruskal算法
      4. Dijkstra
      5. 743.网络延迟时间
      6. 3123.最短路径中的边
      7. 207.课程表
    11. 递归
    12. 搜索
      1. dfs
      2. bfs
      3. 回溯(类似dfs)
      4. 39.组合总和
      5. 924.尽量减少恶意软件的传播
      6. 928.尽量减少恶意软件的传播II
      7. 2385.感染二叉树需要的总时间
      8. 529.扫雷游戏
    13. 贪心
    14. 二分查找
      1. 开闭区间整理
      2. 436.寻找右区间
      3. 1146.快照数组
    15. 动态规划
      1. 背包问题归纳
      2. 403.青蛙过河
      3. 494.目标和
      4. 70.爬楼梯(进阶)
      5. 377.组合总和Ⅳ
      6. 1235.规划兼职工作
      7. 741.摘樱桃
      8. 1463.摘樱桃Ⅱ
    16. 位运算
      1. 异或
      2. Brian Kernighan 算法
      3. 1017.负二进制转换
    17. 数论
      1. gcd
      2. 质数