攻略

基本思路

同一类型的题集中刷，边刷边总结

对于一些简单题, 直接看题解, 看看有没有值得学习的方案, 有再记录下来, 不要直接上手做了, 省点时间

hard 没有思路就直接看答案, 一般都不会考这么难的

没有顺利解答的, 要标记一下, 使用 solved 标记

国内面试 200 题足以, 常考的是链表、字符串、动态规划, 但是要面试外企的话需要 500 题, 工作年限越长, 算法考的越少

GitHub - labuladong/fucking-algorithm: 刷算法全靠套路，认准 labuladong 就够了！English version supported! Crack LeetCode, not only how, but also why.

分类列表

有没有人一起从零开始刷力扣 - 力扣（LeetCode）

• 字符串
  • 数字与字符串间转换, 做完了第一行就行, 第一行倒数第一个也没做, 留着以后做吧
  • 字符串匹配只做了前 2 题, 第 2 题还是 unsolved
• 中心扩展法的两题也先不做了, 感觉是动态规划的衍生题目
  • 数与位
  • 数字的位操作, 做到 231
  • 简单数学题, 只做了第一题, 感觉考的不会太多, 太离谱了
• 栈
  • 388 没做, 看着就烦
  • 括号匹配: 32 没做
  • 递归的也先不做, 因为这里的重点是如何用栈去解决递归问题, 得想学好递归再回来简化
• 链表最后一题没做
• 哈希表
  • 哈希表最后一题没做
• 贪心算法都没有做, 等之后和动态规划一起处理吧
• 双指针
  • 头尾指针, 最后一题接雨水没做, 属于动态规划 + 栈的复合题目, 最后再总结吧
  • 滑动窗口, 最后两道困难题没有做, 留着总结完之后再尝试吧
  • 快慢指针最后一题, 多方法没做的
• 四叉树没做
• 回溯法, 有一些没做, 按照随想录走的, 剩余的做查漏补, go to next!
  • 几个回溯法的都先跳过, 直接从 BFS 开始, bfs 也到此为止吧, 直接从动态规划开始了, 后面再查漏补缺

题解大全

我的建议是先 acwing 再代码随想录 + labuladong 的算法小抄。做为非科班转码选手，可能会有人想知道我是怎么刷 Leetcode 的，在此献上:大家都是如何刷 LeetCode 的？

官方的题解基本就够用了，多拓宽思路

• https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/get-kth-magic-number-lcci
• ac_oier - 力扣（LeetCode）

搞定大厂算法面试之leetcode精讲

总结

深度遍历与栈，深度遍历可以通过栈形式的迭代代替

广度遍历与队列，广度遍历只能通过队列形式，无法通过递归

注意入参

提交有 case 不通过是有惩罚的

最常见的问题: 示例给出的都是大于 0 的正数, 我会下意识的以为所有的输入都是正数, 但是其实是会有负数的

这时候初始化值就不能为 0, 而应该是 Number.MIN_SAFE_INTERGER

优先队列

一个数组, 排序的同时, 要获取每个数的 order , 要对应上原来的位置

135. 分发糖果

减少特判

dummyHead

网格问题, 填充额外的行, col 不用填充, 读取到 undefined 自动结束递归

递归改迭代

用一个额外的变量维护结果.

• 链表的 prev cur
• 树的层次遍历队列

linked-list

../data-structure/tree-traversal

两种数据结构都很常使用递归和迭代, 可以稍微总结一下递归的套路、迭代的套路

递归的一般思路:

1. 确定终止条件
2. 确定单层递归的逻辑
3. 需要用到什么参数就补充什么参数, 再确定返回值即可

递归与回溯

backtracking

Index 问题

有 n 个 item, 每个 item 的 index 从 0 开始, 每个 item 的前后都可以插入新的 item

这个可插入的 slot 就像是尺子上面 5cm 那个长条, 除了线段是一段一段的, 每一段前后都会有一根长条, 这个长条归属于谁?

一个解决方案就是在 list 的最后再添加一个空的 item, 这个 item 的唯一作用就是把所有的 slot 都定义成了在 item 前面. 解决了 slot 的归属问题. 如果你没有这个空的 slot , 就不清楚最后一个 slot 是谁的了.

这个问题从小到遇到过无数遍了, 比如 星期一到星期五之间有多少天? 包不包含头? 包不包含尾?

48. Rotate Image 这一题为了处理好第 n 列和索引 i j 的关系, 浪费了不少时间.

我们在日常中描述矩阵的时候, 都是 one index 的, 但是在代码里却要切换成 0 index

先用正常逻辑去处理 index, 如果出现边界情况, 比如 index 为负 1, 这时候再把所有的 index + 1

从特殊到一般, 先想想最简单的情况 index 的关系是怎么样的, 然后再拓展到一般情况

前缀和

植树问题

方案一: 把 Index 代表的含义写下来, 避免反复确认

preSum[i] 就代表着 nums[0..i-1] 所有元素的累加和，如果我们想求区间 nums[i..j] 的累加和，只要计算 preSum[j+1] - preSum[i] 即可，而不需要遍历整个区间求和。

dp[i] 代表着从 0 到 i-1 个字符的最长上升子序列

Arithmetic-sequence

Time-sequence 时间类题目

主要特点

1. 注重时间开始和结束，比如 1s 初，1s 末
2. 注重时间的间隔，1s 初和 1s 末，间隔了 1s

Solution Tips

想不明白的时候多画时序图

存在性判断问题

用哈希表, 快速判断

节省空间复杂度的方法

原地标记

负数标记, 或者随便弄一个能识别出来的标记, -0, xxx 都行的

又叫做原地哈希

滚动数组都是类似的原理

其实本质上就是利用数组自身的空间

循环数组也是一样的, 旋转数组

矩阵操作

遍历矩阵的正确姿势: 两个 for 循环的标记变量直接使用 row 和 col, 不需要再声明 i j 来获取临时的 row col

如何遍历矩阵最外面的那一圈? 用一个路径数组, [0,1],[1,0], 这样就可以遍历一圈了

    const firstRow = Array.from({ length: board[0].length }, (val, index) => [0, index]);
    const lastRow = Array.from({ length: board[0].length }, (val, index) => [board.length - 1, index]);
    const firstCol = Array.from({ length: board.length - 2 }, (val, index) => [index + 1, 0]);
    const lastCol = Array.from({ length: board.length - 2 }, (val, index) => [index + 1, board[0].length - 1]);
    const step = [...firstRow, ...lastCol, ...lastRow, ...firstCol];

位运算

异或

异或的特性就是自己异或自己为 0, 利用这个特性, 可以用于处理奇偶数次的题目

逐位 操作

用作数的对齐, 之后做运算

var hammingDistance = function(x, y) {
    // 将两个数转换为二进制, 然后进行逐位对比
    const a = x.toString(2);
    const b = y.toString(2);

    let i = a.length - 1;
    let j = b.length - 1;

    while (i >= 0 || j >= 0) {
        const bitA = a[i] || '0';
        const bitB = b[j] || '0';
    }
};
console.log(hammingDistance(1, 4))

以前的我居然命名为 归并式对比, 你别说, 还有点内味

自然数组

数组长度为 n, 且包含 0 到 n - 1 的自然数

特点就是每个数会对应 index, 少了哪个 index 代表那个数缺失了, 被访问过

跟随 index 跳动会成环, 记得还有一道题是超出了 n 的, 但是超出之后会取模, 所以本质上还是自然数组

287 与 442 相比就是不能修改原数组

又要求 O(n) , 所以只能用判圈算法, 然后就是无法找出全部的重复数了

只能知道哪个重复了

跳过重复

递归与分治

和二叉树的分治很像

旋转 = 翻转

Sub 总结

计数问题转换为求和问题

525. 连续数组

ACM 考点

https://oi-wiki.org/string/minimal-string/

https://www.bilibili.com/video/BV1rT411u7b9?spm_id_from=333.1007.tianma.1-2-2.click&vd_source=db8a4b4129af2e1d7a3e3f6357bb4d45

方案总数

Leetcode Overview