# LeetCode 题解速览
对于写过的题，将其最精华的思想浓缩为一句 key，组成 key list，以最后复习时过一遍这些思想。
⚠ 整理中
最近日期：05/08
之前做过的题目补充题解的进度：95%
md 表格生成代码：
如果已经写了一些题目了，第一次想要整理成下面这样的表格用，手动整理太慢
简单写了一份代码用于获得所有已通过的题目信息并生成 markdown 表格
有需要可以自取，根据你的需求改一改就好了
// 打开 https://leetcode-cn.com/problemset/all/ // 登录后，拉到页面最低端，将“每页数量”设置为全部 // 在控制台运行以下代码，即可自动生成完成过的题目markdown表格 let resultArray = [ '| 序号 | 难度 | 题目 | 标签 | 思路 |', '| ---- | ---- | ---- | ---- | ---- |', ]; let table = document.querySelector('.reactable-data'); for (let row of table.children) { if (row.querySelector('.text-success')) { let cols = row.querySelectorAll('td'); let order = cols[1].innerHTML; let title = row.querySelector('.question-title a'); let titleName = title.innerHTML; let titleLink = title.getAttribute('href'); let level = cols[5].querySelector('span').innerHTML; resultArray.push( `| ${order} | ${level} | [${titleName}](https://leetcode-cn.com${titleLink}) | | |` ); } } let resultString = resultArray.join('\n'); console.log('复制内容：'); console.log(resultString); alert('请手动复制监控台输出的内容');
# 0~255 题
| 序号 | 难度 | 题目 | 标签 | 思路 |
|---|---|---|---|---|
| 1 | 简单 | 两数之和 (opens new window) | 数组 | 利用哈希表的 key，使 key+value=target |
| 2 | 中等 | 两数相加 (opens new window) | 链表 | 进位状态、3while 循环 |
| 3 | 中等 | 无重复字符的最长子串 (opens new window) | 串 | 连续字串需满足某性质问题，可考虑滑动窗口，再用 Set 保持无重复 |
| 8 | 中等 | 字符串转换整数 (atoi) (opens new window) | 字符串 正则 | 正则匹配 /^(-|\+)?\d+/ |
| 11 | 中等 | 盛最多水的容器 (opens new window) | 数组 贪心 | 短板决定高度：两板中较短一版向中心找更长的板 |
| 21 | 简单 | 合并两个有序链表 (opens new window) | 链表 | - |
| 22 | 中等 | 括号生成 (opens new window) | 回溯 | 还有'('时就插入'('，回溯，剩余')'多于'('就插入')' |
| 23 | 困难 | 合并 K 个排序链表 (opens new window) | 链表 分治 | 已经具有了多个子问题，可以子问题两两合并成一个较大的子问题 |
| 23 | - | - | 优先队列 | 使用优先队列，用最小堆维护每个链表的首元素，便可每次取得最小 |
| 24 | 中等 | 两两交换链表中的节点 (opens new window) | 链表 | 两两一组，每次记录前一组的最后一个 |
| 28 | 简单 | 实现 strStr() (opens new window) | 字符串 | 暴力 / Sunday / KMP |
| 33 | 中等 | 搜索旋转排序数组 (opens new window) | 查找 | 二分法拓展，判断 mid 与哪边围起来是有序的且目标是否在这个范围 |
| 36 | 中等 | 有效的数独 (opens new window) | 数组 | 用三个对象数组，空间换时间，可仅一次遍历 |
| 42 | 困难 | 接雨水 (opens new window) | 数组 记忆化 | 遍历两次，记下每个元素的左最高元素和右最高元素，然后取交集 |
| 42 | - | - | 数组 栈 | 高度向下时压栈，向上时元素出栈并与当前元素计算水槽宽高 |
| 42 | - | - | 数组 双指针 | 从两边各自记录找到的最大值，矮的一边向中遍历，小于最大可倒水 |
| 45 | 困难 | 跳跃游戏 II (opens new window) | 贪心 | 维护当前步数可达最远距离，在该范围内探索加一步可达的最远距离 |
| 46 | 中等 | 全排列 (opens new window) | 回溯 | 典型利用递归的特性实现回溯 |
| 50 | 中等 | Pow(x, n) (opens new window) | 分治 | 每次将偶数幂次对半分而非一个一个累乘，奇数幂次提一个变成偶数 |
| 53 | 简单 | 最大子序和 (opens new window) | 动态规划 | 记录某位置前面的最大子序和，判断该位置是否要加上前子序和变大 |
| 55 | 中等 | 跳跃游戏 (opens new window) | 数组 贪心 | 一步一步走，不断延拓我们能够达到的最大边界 |
| 56 | 中等 | 合并区间 (opens new window) | 数组 | 先以起始位置排序，再按顺序比较，接壤则合并 |
| 69 | 简单 | x 的平方根 (opens new window) | 查找 | 二分法求平方根，注意琐碎细节 |
| 69 | - | - | 数学 | 数值分析牛顿法求解 x^2-a=0 的根，转化为 x'=(x+a/x)/2 迭代方程 |
| 72 | 困难 | 编辑距离 (opens new window) | 动态规划 | 二维动归，抽象出三种修改方式的状态转移关系 |
| 74 | 中等 | 搜索二维矩阵 (opens new window) | 数组 分治 | 二维的二分法，[row, col] = [floor(mid/n), mid%n] |
| 88 | 简单 | 合并两个有序数组 (opens new window) | 数组 | 逆向思维，从后往前两两比较可以让出位置 |
| 94 | 中等 | 二叉树的中序遍历 (opens new window) | 树 | 左遍历压栈到底，弹出节点值，取其右节点继续左遍历 |
| 98 | 中等 | 验证二叉搜索树 (opens new window) | 二叉搜索树 | 利用定义，设计递归函数fn(root,lower,upper)限制子树保持性质 |
| 98 | - | - | - | 利用性质，判断中序遍历结果是否为升序即可 |
| 100 | 简单 | 相同的树 (opens new window) | 树 | 选一种遍历方式同时遍历两棵树即可 |
| 121 | 简单 | 买卖股票的最佳时机 (opens new window) | 数组 | 线性遍历，记录当前已知最小值，相减以计算最大利润 |
| 122 | 简单 | 买卖股票的最佳时机 II (opens new window) | 数组 | 相邻相减，如果是正的就加起来 |
| 144 | 中等 | 二叉树的前序遍历 (opens new window) | 树 | 取节点值，右树压栈，往左树探 |
| 151 | 中等 | 翻转字符串里的单词 (opens new window) | 字符串 | split -> reverse -> join |
| 155 | 简单 | 最小栈 (opens new window) | 栈 设计 | 辅助栈，每次压栈都压 min(x, minStack.top()) |
| 169 | 简单 | 多数元素 (opens new window) | 数组 | 哈希表统计出现次数，某一值出现次数过半数则结束 |
| 175 | 简单 | 组合两个表 (opens new window) | SQL JOIN | A left join B on A.key = B.key |
| 199 | 中等 | 二叉树的右视图 (opens new window) | 树 | BFS（层次遍历）/ DFS（右子树优先+维护当前遍历的节点深度） |
| 200 | 中等 | 岛屿数量 (opens new window) | 矩阵 遍历 | 典型 DFS / BFS / 并查集 |
| 202 | 简单 | 快乐数 (opens new window) | 哈希表 | Set 存储出现过的结果以避免循环 |
| 202 | 简单 | 快乐数 (opens new window) | 双指针 | 对于判断是否有无限循环的问题，可以考虑快慢指针 |
| 206 | 简单 | 反转链表 (opens new window) | 链表 | prev、current、current.next 三角恋 |
| 221 | 中等 | 最大正方形 (opens new window) | 矩阵 遍历 | 对每个为 1 的元素，将其作为正方形左上角，看是否能补两边长变大 |
| 221 | - | - | 动态规划 | 重复计算考虑动归，dp(i,j)等于 i-1、j-1、i-1 且 j-1 三者最小值+1 |
| 225 | 简单 | 用队列实现栈 (opens new window) | 队列 设计 | 前 n-1 个数从队头出来返入队尾，原本的队尾即可从队头取出 |
| 227 | 中等 | 基本计算器 II (opens new window) | 设计 | 加减直接运算，乘除则先把之前加减的给吐出来运算完了再加回去 |
| 235 | 简单 | 二叉搜索树的最近公共祖先 (opens new window) | 二叉搜索树 | 利用搜索树性质，找到值在两数之间的数即可 |
| 236 | 中等 | 二叉树的最近公共祖先 (opens new window) | 树 遍历 | 递归 DFS，左右子树都找到目标（或者当前节点是其中一个）时保存该答案 |
# 256~511 题
| 序号 | 难度 | 题目 | 标签 | 思路 |
|---|---|---|---|---|
| 289 | 中等 | 生命游戏 (opens new window) | 矩阵 卷积 | 状态值少，可以使用位运算，在不同的位保存不同阶段的状态 |
| 300 | 中等 | 最长上升子序列 (opens new window) | 动态规划 子序列 | 后面的 dp 从前面符合条件的 dp 取最大 |
| 300 | - | - | 贪心 分治 | 维护一个序列：大的接在后面，小的找个位置挤掉一个相对大的 |
| 322 | 中等 | 零钱兑换 (opens new window) | 动态规划 | 01 背包问题，dp[i] = Math.min(dp[i], dp[i - coin] + 1) |
| 322 | - | - | 贪心 回溯 | 每次贪心地选择尽量大的硬币（需回溯所有情况以保证最优） |
| 355 | 中等 | 设计推特 (opens new window) | 设计 | 使用哈希表、链表、优先队列以尽量低的复杂度解决多路归并问题 |
| 357 | 中等 | 计算各个位数不同的数字个数 (opens new window) | 数学 | 数的排列组合 |
| 365 | 中等 | 水壶问题 (opens new window) | 遍历 | 遍历所有操作，消除重复情况以避免死循环 |
| 365 | - | - | 数学 | 存在 a、b 使得ax + by = z，即满足z % gcd(x, y) = 0 |
| 404 | 简单 | 左叶子之和 (opens new window) | 树 | 给函数增加一个“当前节点是否为左节点”的标记 |
| 409 | 简单 | 最长回文串 (opens new window) | 哈希表 | 偶数个数字符直接对称，奇数个可丢掉一个变成偶数个加以利用 |
| 445 | 中等 | 两数相加 II (opens new window) | 链表 | 遇到逆序，可以考虑栈 |
| 460 | 困难 | LFU 缓存 (opens new window) | 设计 哈希表 | 双哈希表以不同的 key 记录同一个结果，以维护 O(1)的增与查 |
| 466 | 困难 | 统计重复个数 (opens new window) | 字符串 子序列 | 对于周期性的问题，找出“循环节”，即可省略所有重复周期的遍历 |
| 501 | 简单 | 二叉搜索树中的众数 (opens new window) | 二叉搜索树 | 利用“中序遍历 BST 可得到递增数组”的性质 |
| 509 | 简单 | 斐波那契数 (opens new window) | 动态规划 | 非常经典的动规消除重复子问题 dp[i] = dp[i - 1] + dp[i - 2] |
# 512~767 题
| 序号 | 难度 | 题目 | 标签 | 思路 |
|---|---|---|---|---|
| 513 | 中等 | 找树左下角的值 (opens new window) | 树 | 记录当前遍历的深度，最深的最左叶子总是会第一个遍历到 |
| 542 | 中等 | 01 矩阵 (opens new window) | 矩阵 遍历 | 逆向思维，将“每个 1 都去找最近的 0”变成“所有 0 组成超级源点去 BFS” |
| 543 | 简单 | 二叉树的直径 (opens new window) | 树 遍历 | 记录左树和右树高，记录最大的左右树高之和，返回 1+最高子树高 |
| 572 | 简单 | 另一个树的子树 (opens new window) | 树 遍历 | 难度大于表面，细节很多，最好联想串匹配问题去注意细节，DFS 遍历 |
| 572 | - | - | 树 串 | 既然和串匹配很像，KMP 算法也能用在 DFS 上（难度可以算困难了） |
| 599 | 简单 | 两个列表的最小索引总和 (opens new window) | 哈希表 | 将其中一表用<list[i], i>存为哈希表，另一表线性遍历即可 |
| 643 | 简单 | 子数组最大平均数 I (opens new window) | 数组 | 定宽滑动窗口 |
| 695 | 中等 | 岛屿的最大面积 (opens new window) | 矩阵 遍历 | 典型矩阵 DFS，每个位置做好 visited 标记后探索四个方向 |
| 744 | 简单 | 寻找比目标字母大的最小字母 (opens new window) | 数组 查找 | 尤其注意数组具有一个“有序”的条件，采取线性遍历或二分法 |
| 747 | 简单 | 至少是其他数字两倍的最大数 (opens new window) | 数组 | 线性遍历找到第一大和第二大的数进行比较即可 |
# 768~1024 题
| 序号 | 难度 | 题目 | 标签 | 思路 |
|---|---|---|---|---|
| 836 | 简单 | 矩形重叠 (opens new window) | 几何 | max(x1,x3) < min(x2,x4) && max(y1,y3) < min(y2,y4) |
| 838 | 中等 | 推多米诺 (opens new window) | 数组 双指针 | 双指针根据不同的情况进行区域划分，对区域做对应的操作 |
| 841 | 中等 | 钥匙和房间 (opens new window) | 遍历 | DFS/BFS，把当前进入的房间内未去过的房间的钥匙拿到 |
| 876 | 简单 | 链表的中间结点 (opens new window) | 链表 双指针 | 经典快慢指针 |
| 887 | 困难 | 鸡蛋掉落 (opens new window) | 动态规划 分治 | dp(K,N)=1+min(max(dp(K-1,X-1),dp(K,N-X))) K 蛋数 N 层数 X 当前层 |
| 892 | 简单 | 三维形体的表面积 (opens new window) | 几何 | 注意不能用三视图算 可先算所有立方体的表面积再减去被遮挡的面 |
| 905 | 简单 | 按奇偶排序数组 (opens new window) | 排序 | O(NlogN)：使用排序算法，以模 2 的结果作为排序依据 |
| 905 | - | - | 遍历 | O(N)：两次遍历，一次输出偶数一次输出奇数 |
| 905 | - | - | 双指针 | O(N)：快排思想，双指针指向左右边缘，向中心找一对不守序的数 |
| 912 | 中等 | 排序数组 (opens new window) | 排序 | 任意实现一种排序 |
| 914 | 简单 | 卡牌分组 (opens new window) | 哈希表 | 哈希表统计各元素个数，求个数的最大公约数是否大于 2 |
| 938 | 简单 | 二叉搜索树的范围和 (opens new window) | 二叉搜索树 | 依据性质，根据是否在区间内决定是否深入 DFS 即可 |
| 945 | 中等 | 使数组唯一的最小增量 (opens new window) | 数组 排序 | 先排序，然后线性遍历查找重复 |
| 958 | 中等 | 二叉树的完全性检验 (opens new window) | 树 | 层次遍历，每个入队元素都记录好自己的序号，观察遍历结果是否连续 |
| 994 | 简单 | 腐烂的橘子 (opens new window) | ||
| 999 | 简单 | 可以被一步捕获的棋子数 (opens new window) | ||
| 1013 | 简单 | 将数组分成和相等的三个部分 (opens new window) |
# 1024+ 题
| 序号 | 难度 | 题目 | 标签 | 思路 |
|---|---|---|---|---|
| 1071 | 简单 | 字符串的最大公因子 (opens new window) | ||
| 1095 | 困难 | 山脉数组中查找目标值 (opens new window) | 二分查找 | 二分找山顶时 mid 与 mid+1 比大小识别坡度，左右坡分别找 target |
| 1103 | 简单 | 分糖果 II (opens new window) | ||
| 1111 | 中等 | 有效括号的嵌套深度 (opens new window) | 子序列 分组 | 利用奇偶性进行分组 |
| 1160 | 简单 | 拼写单词 (opens new window) | ||
| 1162 | 中等 | 地图分析 (opens new window) | 图 遍历 | 多源 DFS，visited 数组 |
| 1248 | 中等 | 统计「优美子数组」 (opens new window) | 子序列 前缀和 | 找到所有奇数，然后(odd[i]−odd[i−1])∗(odd[i+k]−odd[i+k−1]) |
| 1248 | - | - | - | 改为差分形式，遍历的数通过左最近奇数 i 找到 odd[i-k]来累加 |
# 程序员面试金典系列
| 序号 | 难度 | 题目 | 标签 | 思路 |
|---|---|---|---|---|
| 面试题 01.06 | 简单 | 字符串压缩 (opens new window) | 字符串 | 取一字符，while 自增循环计其连续个数，加入结果字符串 |
| 面试题 01.07 | 中等 | 旋转矩阵 (opens new window) | 矩阵 交换 | 分成 4 区，顺时针交换；或者先转置，再水平翻转 |
| 面试题 04.03 | 中等 | 特定深度节点链表 (opens new window) | 树 遍历 | 层次遍历（BFS）一层一次循环或者 DFS 将深度当参数传入 |
| 面试题 08.11 | 中等 | 硬币 (opens new window) | 动态规划 | 完全背包问题，关键点在于面额枚举在外层，背包遍历在内层 |
| 面试题 10.01 | 简单 | 合并排序的数组 (opens new window) | 数组 | 类似归并，要点是从后往前遍历，从尾巴开始填充 |
| 面试题 16.03 | 困难 | 交点 (opens new window) | 数学 | 参数方程表示线段，求交点，考虑斜率相等重叠等情况 |
| 面试题 16.16 | 中等 | 部分排序 (opens new window) | 双指针 | 从左到右遍历不是为了找第一个不守序的元素，而是找最后一个 |
| 面试题 17.16 | 简单 | 按摩师 (opens new window) | 动态规划 | dp[i]=max(dp[i-1], dp[i-2]+val[i])（三个变量迭代即可） |
# 剑指 Offer 系列
| 序号 | 难度 | 题目 | 标签 | 思路 |
|---|---|---|---|---|
| 面试题 10-I | 简单 | 斐波那契数列 (opens new window) | 数学 | 基础题，直接用两个变量递推就可以 |
| 面试题 11 | 简单 | 旋转数组的最小数字 (opens new window) | 数组 查找 | 二分查找的变种，注意两指针相等时需要做保守策略 |
| 面试题 13 | 中等 | 机器人的运动范围 (opens new window) | 矩阵 遍历 | DFS/BFS 仔细分析限制条件，只需向右/下走即可遍历所有 |
| 面试题 14-I | 中等 | 剪绳子 (opens new window) | 数学 贪心 | 需要能观察出规律，或者数学推导，否则需动归 |
| 面试题 26 | 中等 | 树的子结构 (opens new window) | 树 | 二叉树版的字符串比对，时间复杂度 O(M*N)可以了 |
| 面试题 27 | 简单 | 二叉树的镜像 (opens new window) | 树 | 递归 left, right = mirror(right), mirror[left] |
| 面试题 33 | 中等 | 二叉搜索树的后序遍历序列 (opens new window) | 树 | 翻转后序遍历结果就是镜像先序遍历+搜索树先序遍历递增性质 |
| 面试题 40 | 简单 | 最小的 k 个数 (opens new window) | 排序 TopK | 堆排序（O(nlogk)） / 快速排序变种（O(n)） |
| 面试题 46 | 中等 | 把数字翻译成字符串 (opens new window) | ||
| 面试题 51 | 困难 | 数组中的逆序对 (opens new window) | 数组 排序 | 和顺序有关需优化可考虑排序算法。本题一边归并一边统计 |
| 面试题 56-I | 中等 | 数组中数字出现的次数 (opens new window) | 位运算 | 要求低时空复杂度，考虑位运算，又有重复的条件，考虑异或 |
| 面试题 57-II | 简单 | 和为 s 的连续正数序列 (opens new window) | ||
| 面试题 59-II | 中等 | 队列的最大值 (opens new window) | ||
| 面试题 62 | 简单 | 圆圈中最后剩下的数字 (opens new window) | 数学 | 约瑟夫环循环链表可解 但数学推导从结果反推起始位置更好 |
# LeetCode 周赛
| 周 | 序号 | 难度 | 题目 | 标签 | 思路 |
|---|---|---|---|---|---|
| 178 | 1365 | 简单 | 有多少小于当前数字的数字 (opens new window) | 数组 | 暴力 / 桶排序 / O(NlogN)排序 |
| 178 | 1366 | 中等 | 通过投票对团队排名 (opens new window) | 排序 | 自定义排序的比较规则，哈希表存储信息 |
| 180 | 1380 | 简单 | 矩阵中的幸运数 (opens new window) | 数组 | 统计每行最小与每列最大，取交集 |
| 180 | 1381 | 中等 | 设计一个支持增量操作的栈 (opens new window) | 数组 栈 设计 | 优化：可以设置一个增量数组用于弹出时再加上 |
| 182 | 5368 | 简单 | 找出数组中的幸运数 (opens new window) | 数组 | 哈希表 |
| 182 | 5369 | 中等 | 统计作战单位数 (opens new window) | 数组 | 滑动窗口，先选最高和最低，再在中间选中间 |
| 182 | 5370 | 中等 | 设计地铁系统 (opens new window) | 设计 | 使用哈希表设计好信息存储即可 |