力扣hot100
1.两数之和（哈希 简单）
注意点：
- 你不能使用两次相同的元素
- 每次输出只会存在一个有效答案
思路：
- 为什么会想到用哈希法：每当我们遇到要判断这个元素是否在这个集合里出现过的时候，可以联想到哈希法
- 为什么要用map：map可以在最快时间内查到元素是否出现过，把元素作为key，元素对应的下标作为value，这里用map存放我们遍历过的元素
初始代码
1 | class Solution { |
完整代码实现
1 | class Solution { |
补充：暴力枚举法
1 | //第二种写法:暴力枚举法 |
2.移动零（双指针 - 简单）
思路：1.分两个数组，一个数组保存非零的数字，一个数组保存零的数字，分别遍历完后，再将这两个数组一合并 但这违反了题目中复杂度为O（1）
2.定义两个指针，让它们同时指向数组的第一个元素，当右指针指向的元素为0，我们就往右移动右指针，一直到右指针指向的元素不为0，这个时候我们就交换左右指针指向的元素，交换完左右指针指向的元素，左指针需要向右移一位，然后我们继续向右移动右指针，一直到指向的元素不为0，这个时候我们就交换左右指针指向的元素，继续之前的过程，直到右指针遍历完了整个数组
基于思路二实现：
1 | public void moveZeroes(int[] nums) { |
或者这样优化：
1 | public class Solution { |
✅ 使用双指针；
✅ 不用额外数组；
✅ 时间复杂度 O(n)，空间复杂度 O(1)；
✅ 但没有“交换元素”，而是“覆盖非零 → 后补零”；
✅ 操作次数更少，效率更高（尤其当非零元素很多时）。
nums = [0, 1, 0, 3, 12]
一开始：nums = [0, 1, 0, 3, 12]
left = 0
遍历右指针过程：
| right | nums[right] | 是否非零？ | 操作 | nums（当前状态） | left |
|---|---|---|---|---|---|
| 0 | 0 | 否 | 跳过 | [0, 1, 0, 3, 12] | 0 |
| 1 | 1 | 是 | nums[0] = 1，left++ | [1, 1, 0, 3, 12] | 1 |
| 2 | 0 | 否 | 跳过 | [1, 1, 0, 3, 12] | 1 |
| 3 | 3 | 是 | nums[1] = 3，left++ | [1, 3, 0, 3, 12] | 2 |
| 4 | 12 | 是 | nums[2] = 12，left++ | [1, 3, 12, 3, 12] | 3 |
第二步：从 left 开始到末尾，全填 0
此时：
left = 3
nums = [1, 3, 12, 3, 12]
填 0：
| left | 操作 | nums（当前状态） |
|---|---|---|
| 3 | nums[3] = 0 | [1, 3, 12, 0, 12] |
| 4 | nums[4] = 0 | [1, 3, 12, 0, 0] |
3.两数相加（链表-中等）
思路：
- 这里有两个链表L1和L2，还需要一个进位值carry来保存进位的符号
- 例如上图的4+6，此时carry等于1（4+6+0），此时的carry就赋给下一次运算
- 得到新链表的每一个值都是(L1.val+L2.val+carry)%10+ 例如例二7+9 =( 7+9+0)%10=6，因为初始的carry为0
- 递归条件：只要 l1、l2、carry 还有一个没用完，就一直循环，递归结束条件：l1，l2，carry都为null的时候
代码实现：
1 | public class Solution1 { |
思考：
1.为什么要创建 dummyHead？为什么是 -1？
- 这个
dummyHead是一个哑节点（虚拟头节点），它的作用是： 简化链表操作，避免处理头节点为空或首个节点需要特殊处理的问题。 - 它的
val填什么其实无所谓，因为： 你最后只会返回dummyHead.next，真正的结果链表从它“后面”开始。
2.cur.next = new ListNode(num);cur = cur.next;怎么理解
如果dummyHead → 7 → 0
cur 指向 0
你执行这一句：cur.next = new ListNode(8);
就会变成：dummyHead → 7 → 0 → 8
cur.next → 新的 8 节点
之后：cur = cur.next; // 把 cur 往后移到 8，准备连接下一个节点
为什么返回 dummyHead.next？
- 回顾一下：
dummyHead是我们人为加的“虚拟头节点”，不属于最终结果； - 真正的加法结果是从
dummyHead.next开始的。
dummyHead: -1 → 7 → 0 → 8
你真正的返回应该是：7 → 0 → 8 也就是从 dummyHead.next 开始的部分。
另一种递归写法：
1 | public class Solution { |
-
carry不是单纯表示“上一次的进位”，它同时承担当前的“累加和”； -
每次把当前
l1和l2的值加进去； -
然后将
l1、l2指向下一个节点，为下一层递归准备。 -
返回的是
ListNode(当前位, 下一位递归结果)，构建整条链表。 -
carry % 10：当前位的值（个位数）； -
carry / 10：进位值，传递给下一层递归； -
addTwo(...)：下一位的节点，递归返回值； -
new ListNode(值, 下一节点)：创建当前节点并链接下一个。
4.二叉树的中序遍历（二叉树-简单）
中序遍历：左子树->根节点->右子树
从题中的例图可以看出来，1没有左子树，先返回根节点1，再返回右子树2和3,2为右子树的根节点2和3中，先返回左子树3，再返回根节点2，没有右子树，综上即[1,3,2]
思路：知道了中序遍历的规律，我们可以用递归的方法去做，方式一
方式二，还可以用栈来做，递归的调用过程是不断往左边走，当左边走不下去了，就打印节点，并转向右边，然后右边继续这个过程。我们在迭代实现时，就可以用栈来模拟上面的调用过程。
1 | 方式一，递归做法 |
5.搜索插入位置（二分查找-简单）
标准的二分查找题目
1 | public int searchInsert(int[] nums, int target) { |
6.有效的括号（栈-简单）
用栈的方式来写
1 | public boolean isValid(String s) { |
优化一下：
1 | public boolean isValid(String s) { |
2.用 Map<Character, Character> 的方式重写，使代码更优雅、结构更清晰。
使用 Map 来存储「括号的对应关系」可以让我们：
- 不用写一大堆
if或switch - 在遇到右括号时，快速查到它对应的左括号
- 逻辑更清晰、便于扩展（比如未来加
< >等新括号）
1 | public boolean isValid(String s) { |
7.杨辉三角（动态规划-简单）
思路：
首先得先知道什么是杨辉三角，即第一行只有一个元素1，后续每行的首尾元素都为1，中间元素等于上一行相邻元素两个元素之和。此外，第i行有i个元素，元素个数和当前行数相同。下面来用动态规划五部曲进行分析。
- 确定dp数组以及下标的含义：
dp[i] 表示杨辉三角中第i+1行的元素列表（从0开始计数），每个元素dp[i][j]表示该行的第j个位置上的数值
- 确定递推公式：
dp[i][j] = dp[i-1][j-1] + dp[i-1][j] 这个公式表示当前行的元素等于上一行相邻两个元素之和，如下图中的2的等于它的左上角和头顶之和
- dp数组如何初始化：
初始化第一行只有一个元素1，后续每行的首尾元素都初始化为1
- 确定遍历顺序：
需要按照行优先的顺序从上到下逐行构建，每行的中间元素需要从前一行计算得
1 | public List<List<Integer>> generate(int numRows) { |
直接利用上一行（单数组滚动法）
思路：只保留上一行，用一个新列表构建当前行，完成后再赋值给上一行。节省空间到 O(n)。
1 | public List<List<Integer>> generate(int numRows) { |
二维数组：
1 | public List<List<Integer>> generate(int numRows) { |
8.只出现一次的数字（位运算-简单）
位运算中的异或运算 XOR，主要因为异或运算有以下几个特点：
- x ^ x = 0 （任何数与自己异或结果为0）
- x ^ 0 = x （任何数与0异或结果为该数本身）
- XOR是交换的和结合的。
- 故而在以上的基础条件上，将所有数字按照顺序做异或运算，最后剩下的结果即为唯一的数字
异或位运算：
1 | public int singleNumber(int[] nums) { |
9.相交链表（链表-简单）
要求：两个单链表，如果有交点，返回这个交点；否则返回 null。
思路：
两个指针 P 和 Q 的奇妙走法
我们设置两个指针：
p从headA出发q从headB出发
如果 p 到达了链表末尾，就从 headB 开始走；
如果 q 到达了链表末尾，就从 headA 开始走。
直到它们相遇为止（或者都为 null）。
假设如下：
- A 链表为：
a + c，a 是独有部分，c 是公共部分 - B 链表为：
b + c，b 是独有部分，c 是公共部分 - 公共部分长度为 c
- 则：
- p 总共走：a + c + b
- q 总共走：b + c + a
也就是说，两个指针最终都走了 a + b + c 的长度！
如果两个链表有交点，它们一定在 c 的起点相遇。
如果没有交点，p 和 q 会最终都走到 null，然后一起退出循环。
（leetcode网友热评）
走到尽头见不到你，于是走过你来时的路，等到相遇时才发现，你也走过我来时的路。
走过彼此的路，我们终会相遇❤️❤️❤️
代码如下：
1 | public ListNode getIntersectionNode(ListNode headA, ListNode headB) { |
暴力法
简单的一个想法，对链表 A 中的每一个结点，我们都遍历一次链表 B 查找是否存在重复结点，第一个查找到的即第一个公共结点
1 | public ListNode getIntersectionNode(ListNode headA, ListNode headB) { |
哈希表法
基本思路：用 HashSet 存一个链表的所有节点
- 先遍历链表 A，把它所有的节点放进一个
HashSet中（注意是节点本身，不是值）。 - 然后遍历链表 B，每走一个节点，就判断是否存在于这个 HashSet 中。
- 如果存在，说明从该节点开始就是交点。
- 如果 B 走完都没有命中，返回
null。
1 | public ListNode getIntersectionNode(ListNode headA, ListNode headB) { |
栈的做法
两个链表如果在某个节点相交，那么从相交点开始到链表末尾的所有节点是完全一样的（引用相同）。
因此，我们可以：
- 把两个链表的节点分别存入两个栈/双端队列中；
- 从链表尾部开始倒着对比两个链表的节点；
- 最后一个“相同”的节点，就是我们要找的相交起点。
1 | public ListNode getIntersectionNode(ListNode headA, ListNode headB) { |
10.二叉树的最大深度（二叉树-简单）
1.后序遍历（DFS）
树的后序遍历 / 深度优先搜索往往利用 递归 或 栈 实现，这里使用递归实现。
关键点： 此树的深度和其左（右）子树的深度之间的关系。显然，此树的深度 等于 左子树的深度 与 右子树的深度中的 最大值 +1 。
- 终止条件： 当 root 为空，说明已越过叶节点，因此返回 深度 0 。
- 递推工作： 本质上是对树做后序遍历。
- 计算节点 root 的 左子树的深度 ，即调用 maxDepth(root.left)。
- 计算节点 root 的 右子树的深度 ，即调用 maxDepth(root.right)。
- 返回值： 返回 此树的深度 ，即 max(maxDepth(root.left), maxDepth(root.right)) + 1
1 | public int maxDepth(TreeNode root) { |
2.层序遍历（BFS）
树的层序遍历 / 广度优先搜索往往利用 队列 实现。
关键点： 每遍历一层，则计数器 +1 ，直到遍历完成，则可得到树的深度。
- 特例处理： 当 root 为空，直接返回 深度 0 。
- 初始化： 队列 queue （加入根节点 root ），计数器 res = 0。
- 循环遍历： 当 queue 为空时跳出。
- 初始化一个空列表 tmp ，用于临时存储下一层节点。
- 遍历队列： 遍历 queue 中的各节点 node ，并将其左子节点和右子节点加入 tmp。
- 更新队列： 执行 queue = tmp ，将下一层节点赋值给 queue。
- 统计层数： 执行 res += 1 ，代表层数加 1。
- 返回值： 返回 res 即可。
1 | public int maxDepth(TreeNode root) { |
11.翻转二叉树（简单-二叉树）
递归法
思路：交换每个节点的左子树和右子树
根据二叉树镜像的定义，考虑递归遍历（dfs）二叉树，交换每个节点的左 / 右子节点，即可生成二叉树的镜像。
递归解析：
终止条件： 当节点 root 为空时（即越过叶节点），则返回 null 。
递推工作：
初始化节点 tmp ，用于暂存 root 的左子节点。
开启递归 右子节点 invertTree(root.right) ，并将返回值作为 root 的 左子节点 。
开启递归 左子节点 invertTree(tmp) ，并将返回值作为 root 的 右子节点 。
返回值： 返回当前节点 root 。
1 | public TreeNode invertTree(TreeNode root) { |
方法2：辅助栈（或队列）
利用栈（或队列）遍历树的所有节点 node ，并交换每个 node 的左 / 右子节点。
算法流程：
特例处理： 当 root 为空时，直接返回 null 。
初始化： 栈（或队列），本文用栈，并加入根节点 root 。
循环交换： 当栈 stack 为空时跳出。
出栈： 记为 node 。
添加子节点： 将 node 左和右子节点入栈。
交换： 交换 node 的左 / 右子节点。
返回值： 返回根节点 root 。
1 | public TreeNode invertTree(TreeNode root) { |
12.岛屿数量（BFS/DFS 中等）
岛屿由水平方向或竖直方向上相邻的陆地连接形成
思路：
1.广度优先搜索（BFS）
只需搜索该元素水平和垂直方向的元素，之后再遍历每行没被搜索的元素，值为1时继续开始广度优先搜索
- 初始化岛屿计数器
res为 0。 - 遍历网格：
- 每次遇到值为
'1'的格子时，启动 BFS 并将其与其他相连的'1'都标记为'0'，每次启动 BFS 都将岛屿计数器res加 1。 - BFS 搜索：
- 使用队列来进行 BFS，遍历该岛屿的每个格子，并将相邻的格子（上下左右）也加入队列，继续标记已访问的格子。
- 返回结果：
- 最终返回
res，即岛屿的总数。
1 | class Solution { |
2.深度优先搜索（DFS）
DFS就是沿着一条路径一直走下去，每个位置只要是1，先要把它置为0，然后沿着他的上下左右4个方向继续遍历，执行同样的操作，要注意边界条件的判断。
初始化：岛屿数量 res 设为 0，开始遍历 grid 中的每一个元素。
发现岛屿：当遇到岛屿（1）时，启动 DFS，标记该岛屿及其相邻部分。
递归过程：每次调用 dfs 会将当前岛屿的一个部分标记为已访问（2），并递归地访问该岛屿的上下左右四个相邻格子，直到该岛屿的所有部分都被访问。
岛屿计数：每次从未访问的岛屿（1）开始 DFS，岛屿数量 res 增加 1。
返回结果：遍历完网格后，返回岛屿总数 res。
1 | class Solution { |
13.反转链表（链表-简单）
方法1递归
思路：使用递归法遍历链表，当越过尾节点后终止递归，在回溯时修改各节点的 next 引用指向。
recur(cur, pre) 递归函数：
- 终止条件：当 cur 为空，则返回尾节点 pre （即反转链表的头节点）；
- 递归后继节点，记录返回值（即反转链表的头节点）为 res ；
- 修改当前节点 cur 引用指向前驱节点 pre ；
- 返回反转链表的头节点 res ；
reverseList(head) 函数：
调用并返回 recur(head, null) 。传入 null 是因为反转链表后， head 节点指向 null ；
1 | class Solution { |
方法2迭代（双指针）
考虑遍历链表，并在访问各节点时修改 next 引用指向
1 | class Solution { |
14.对称二叉树（二叉树-简单）
思路：
对称二叉树定义： 对于树中 任意两个对称节点 L 和 R ，一定有：
L.val = R.val ：即此两对称节点值相等。
L.left.val = R.right.val ：即 L 的 左子节点 和 R 的 右子节点 对称。
L.right.val = R.left.val ：即 L 的 右子节点 和 R 的 左子节点 对称。
1 | public boolean isSymmetric(TreeNode root) { |
15.二叉树的直径（二叉树-简单）
1 | int diameter = 0; |
16.二叉树的层序遍历（二叉树-中等）
思路：
1.BFS(广度优先遍历)
广度优先遍历是按层层推进的方式，遍历每一层的节点。题目要求的是返回每一层的节点值，所以这题用广度优先来做非常合适。广度优先需要用队列作为辅助结构，我们先将根节点放到队列中，然后不断遍历队列。
首先拿出根节点，如果左子树/右子树不为空，就将他们放入队列中。第一遍处理完后，根节点已经从队列中拿走了，而根节点的两个孩子已放入队列中了，现在队列中就有两个节点 2 和 5。
第二次处理，会将 2 和 5 这两个节点从队列中拿走，然后再将 2 和 5 的子节点放入队列中，现在队列中就有三个节点 3，4，6。
我们把每层遍历到的节点都放入到一个结果集中，最后返回这个结果集就可以了。
1 | public List<List<Integer>> levelOrder(TreeNode root) { |
2.DFS(深度优先搜索)
按照深度优先的处理顺序，会先访问节点 1，再访问节点 2，接着是节点 3。
之后是第二列的 4 和 5，最后是第三列的 6。
每次递归的时候都需要带一个 index(表示当前的层数)，也就对应那个田字格子中的第几行，如果当前行对应的 list 不存在，就加入一个空 list 进去。
1 | public List<List<Integer>> levelOrder(TreeNode root) { |
17.盛最多水的容器（双指针-中等）
给定一个长度为 n 的整数数组 height，其中每个元素代表柱子的高度。在坐标轴上画出这些柱子，选择其中两根柱子与 x 轴共同构成一个容器，求这个容器可以容纳的最多水量。
思路：
缩减搜索空间
要解决的核心问题是：
为什么移动较短边是对的？会不会错过最大面积的可能性？
举例
假设当前两根柱子 i 和 j，height[i] < height[j]：
- 由于面积受限于较短的柱子（即 height[i]），
- 并且我们要缩短宽度了（因为下一步是往中间靠），
- 那么为了可能增加面积，唯一的机会是找到更高的柱子来提升高度（否则面积一定变小）
所以：
移动较短的柱子才有可能找到更优解；移动较长边肯定是浪费计算。
这个逻辑保证了不会遗漏最大面积。
从搜索空间来看，一开始我们有完整的二维搜索空间（i < j 的所有组合），双指针的过程就像在这个空间中不断缩小边界：
由于 i、j 的约束条件的限制，搜索空间是白色的倒三角部分。可以看到，搜索空间的大小是 O(n2) 数量级的。如果用暴力解法求解，一次只检查一个单元格，那么时间复杂度一定是 O(n2)。要想得到 O(n) 的解法，我们就需要能够一次排除多个单元格。那么我们来看看，本题的双指针解法是如何削减搜索空间的：
一开始，我们检查右上方单元格 (0,7)，即考虑最左边的 0 号柱子和最右边的 7 号柱子，计算它们之间容纳水的面积。然后我们比较一下两根柱子的高度，关注其中较短的一根。
假设左边的 0 号柱子较短。根据刚才的推理，0 号柱子目前的水面高度已经到了上限。由于 7 号柱子已经是离 0 号柱子最远的了，水的宽度也最大，如果换其他的柱子和 0 号柱子配对，水的宽度只会更小，高度也不会增加，容纳水的面积只会更小。也就是说，0 号柱子和 6,5,…,1 号柱子的配对都可以排除掉了。记录了 (0,7) 这组柱子的结果之后，就可以排除 0 号柱子了。这相当于 i=0 的情况全部被排除。对应于双指针解法的代码，就是 i++；对应于搜索空间，就是削减了一行的搜索空间，如下图所示。
排除掉了搜索空间中的一行之后，我们再看剩余的搜索空间，仍然是倒三角形状。我们检查右上方的单元格 (1,7)，即考虑 1 号柱子和 7 号柱子，计算它们之间容纳水的面积。然后，比较两根柱子的高度。
假设此时 7 号柱子较短。同理， 7 号柱子已经是离 1 号柱子最远的了，如果换其他的柱子和 1 号柱子配对，水的宽度变小，高度也不会增加，容纳水的面积只会更小。也就是说，7 号柱子和 2,3,…,6 号柱子的配对都可以排除掉了。记录了 (1,7) 这组柱子的结果之后，就可以排除 7 号柱子了。这相当于 j=7 的情况全部被排除。对应于双指针解法的代码，就是 j–；对应于搜索空间，就是削减了一列的搜索空间，如下图所示。
可以看到，无论柱子 i 和 j 哪根更长，我们都可以排除掉一行或者一列的搜索空间。经过 n 步以后，就能排除所有的搜索空间，检查完所有的可能性。搜索空间的减小过程如下面动图所示：
双指针解法的本质是：在每一步都通过移动较短的柱子，来尝试在缩小宽度的同时，提升高度，从而寻找可能的更大面积 —— 同时还能有效剪枝搜索空间，避免 O(n²) 的暴力搜索。
1 | public int maxArea(int[] height) { |
双指针指向数组两端：
i：左指针，从头开始j：右指针，从尾开始
每一步：
- 计算当前两根柱子组成的面积
(j - i) * min(height[i], height[j]) - 尝试移动较短的那根柱子，期待找到更高的柱子，从而有可能增大面积
- 一旦
i == j，遍历完成
用时最短的答案，思路是一样的：
18.字母异位词分组（哈希 中等）
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
方法一：排序
字母相同，但排列不同的字符串，排序后都一定是相同的。因为每种字母的个数都是相同的，那么排序后的字符串就一定是相同的。
把“排序后的串”当作 键 key，把原始单词丢进以该 key 为索引的列表里。最后把这些列表作为结果返回。
- 遍历每个字符串，将它转成字符数组并排序。
- 排序后的字符串作为键（key），把它存到一个
HashMap<String, List<String>>中。 - 相同 key 的单词放到同一个 list 里，最后把 map 中的所有 list 输出即可。
1 | import java.util.*; |
方法二，计数法
计数法”版本的核心思想是：
- 不再对字符串进行排序（
O(L log L)），而是统计 26 个字母的出现次数（O(L)）。 - 用字母计数结果作为 签名 key。相同字母频次的单词一定是字母异位词。
1 | import java.util.*; |
19.和为K的子数组（子串 中等）
- 子数组必须是连续的；
- 要找出所有子数组之和 = k 的个数；
- 暴力做法是用两层循环计算所有可能的子数组和，时间复杂度是 O(n²)，会超时；
- 优化做法用 前缀和 + 哈希表 实现 O(n) 的时间复杂度。
什么是前缀和？
前缀和 preSum[i] 表示从第 0 个数到第 i-1 个数的总和。
比如数组 nums = [1,2,3]，前缀和数组是：
1 | preSum = [0, 1, 3, 6] |
因为：
- preSum[0] = 0
- preSum[1] = 1
- preSum[2] = 1+2 = 3
- preSum[3] = 1+2+3 = 6
核心思想：
子数组之和 = k，等价于：
对于两个下标 i 和 j（j > i）来说：
1 | preSum[j] - preSum[i] == k |
如上例子的preSum = [0, 1, 3, 6]，nums = [1,2,3]中1=preSum[1] -preSum[0]
2=preSum[2] -preSum[1] ，3=preSum[3] -preSum[2]
也就是说，从 i 到 j-1 的子数组和是 k！
那么就可以反过来思考：
1 | preSum[j] - k == preSum[i] |
具体做法：
-
初始化：
- 创建一个哈希表
preCnt来记录每个前缀和出现的次数； - 放入初始值：
preCnt[0] = 1，表示和为 0 的前缀和出现了一次。
- 创建一个哈希表
-
遍历数组
1
nums
：
-
每一步累加当前值，得到新的
preSum； -
检查：有没有之前的某个前缀和
1
preSum - k
？
- 有的话，就说明存在一个子数组的和是 k，累计结果；
-
把当前的
preSum存入哈希表中，出现次数 +1。
-
1 | public int subarraySum(int[] nums, int k) { |
20.最大子数组和（动态规划 中等）
思路：看描述就知道应该是一个经典的动态规划题目
定义两个变量：一个是截至目前的累加量，current_sum,一个是截止目前见过的最大的量，如果current_sum没有当前元素大，我们不妨放弃current_sum，从当前数组元素重新开始，遍历完整个数组后，max_sum就记录了最大子数组和
例如从第一个数-2开始，current_sum和max_sum都为-2，当遍历到了1，让current_sum+1和1对比，发现-1<1所以我们选择重新开始
current_sum和max_sum更新为1
接下来是-3，我们选择继续累加，更新current_sum
接下来是4选择继续累加为2小于当前元素4，因为我们选择重新开始，并更新最大数组和
同理一直累加直到数组完全遍历完，拿出最后的max_sum，这就是最终的最大子数组和
1 | public int maxSubArray(int[] nums) { |
以下是Kadane 算法 的另一种写法，来自leetcode画手大鹏
题目：最大子数组和
我们要找一个连续子数组，它的和最大。
关键观察：
- 如果之前累积的和
sum是 正的，它对后面的子数组有帮助（加上它会更大），所以可以继续加。 - 如果之前累积的和
sum是 负的 或 0，它对后面的子数组是负担（加上它会更小），所以应该丢掉，从当前这个数重新开始。
遍历数组时，如果当前累积和是正数，就延续下去；如果是负数，就丢掉重新开始，同时更新全局最大值。
1 | public int maxSubArray(int[] nums) { |
21.回文链表（链表 简单）
解题思路：
- 快慢指针：使用快慢指针找到链表的中间节点。快指针每次移动两步，慢指针每次移动一步，当快指针到达链表末尾时，慢指针刚好到达链表的中间。
- 反转后半部分链表：从慢指针开始，将链表的后半部分反转。
- 比较前半部分与后半部分：将链表的前半部分和反转后的后半部分逐个节点进行比较，如果每个节点都相等，说明是回文链表。
输入：head = [1, 2, 2, 1]
- 快慢指针找到中点：
2 - 反转后半部分：
1 <- 2 - 比较前半部分和反转后的后半部分：
[1, 2]和[1, 2]相同，返回true。
输入：head = [1, 2]
- 快慢指针找到中点：
2 - 反转后半部分：
2 - 比较前半部分和反转后的后半部分：
[1]和[2]不相同，返回false。
1 | public boolean isPalindrome(ListNode head) { |
法2：将链表的值存入一个数组，然后通过双指针的方式（从头和尾同时比较）判断数组是否是回文的。
- 将链表元素存入数组：遍历链表，将链表中的每个节点的值存入一个数组中。这样，链表的元素就转化成了一个一维数组，方便后续处理。
- 双指针比较：通过两个指针，一个从数组的开始位置，一个从数组的结束位置，逐个比较它们的值。如果有任何一对不相等，说明链表不是回文链表，直接返回
false。 - 链表是回文：如果遍历完数组，所有对应的元素都相等，那么链表就是回文链表。
1 | class Solution { |
22.多数元素（简单）
1.排序法：
排序数组：
Arrays.sort(nums); 会对数组进行排序。排序后，数组中的元素会按从小到大的顺序排列。由于“多数元素”（出现次数大于 n/2）的数量比较大，它一定会出现在排序后数组的中间位置。
找出多数元素：
排序完成后，数组中间的元素（即索引为 n/2 的元素）就是多数元素。因为多数元素出现次数超过数组长度的一半，所以排序后的数组中，它必定会位于数组的中间位置。
例如：
- 假设
nums = [3, 3, 3, 2, 2]，排序后为[2, 2, 3, 3, 3]，可以看到3就是多数元素，因为它的出现次数大于n/2。
使用位运算来获取数组的中间元素。位运算中的 >> 1 相当于对数组长度进行除以 2 的操作，并且结果会向下取整
高效访问：
nums[nums.length >> 1] 用位移操作代替了除法，计算出数组中间位置的元素，效率较高。这个操作等同于 nums.length / 2。
1 | class Solution { |
2.摩尔投票法思路
摩尔投票法（Boyer-Moore Voting Algorithm）是一种用于在数组中寻找多数元素的高效算法。多数元素是指在数组中出现次数超过 ⌊n/2⌋ 次的元素。摩尔投票法的思路非常巧妙，下面我会详细讲解为什么这个算法能够正确地找出多数元素。
思路解释：
- 初始化候选人和票数：
cand_num：当前的候选人，初始化为数组的第一个元素nums[0]。count：票数，初始化为 1，表示当前候选人cand_num得到了 1 票。
- 遍历数组：
- 对于数组中的每个元素
nums[i]，如果它和当前候选人cand_num相同，则为候选人增加一票，即count++。 - 如果它和候选人不同，则减去一票，即
count--。
- 对于数组中的每个元素
- 调整候选人：
- 如果
count变为 0，表示当前候选人失去了对多数的支持，此时更换候选人，将新的候选人设置为nums[i]，并且将count重置为 1。
- 如果
- 最终答案：
- 遍历结束后，
cand_num就是最终的多数元素。
- 遍历结束后，
1 | class Solution { |
摩尔投票法通过票数的增减和候选人更换机制，确保在最后得到的候选人就是数组中的多数元素。这种方法非常高效，适用于找到一个在数组中出现次数超过 ⌊n/2⌋ 的元素，且其时间复杂度为 O(n)，空间复杂度为 O(1)。
23.环形链表（双向链表-简单）
快慢指针
想象兔子和乌龟在同一跑道上，一个速度快、另一个速度慢。如果跑道有环，兔子必然在一段时间后追上乌龟。对于链表来说，如果在链表中引入两个以不同速度（一个比另一个快一倍）前进的指针，在链表存在环的情况下，这两个指针必定会相遇。
注意：代码比较两个节点的时候，比较的是内存地址是否一致，并没有比较节点的 val。
问：兔子会不会「跳过」乌龟，从来不会和乌龟相遇呢？
答：这是不可能的。如果有环的话，那么兔子和乌龟都会进入环中。这时用「相对速度」思考，乌龟不动，兔子相对乌龟每次只走一步，这样就可以看出兔子一定会和乌龟相遇了。
问：为什么代码的 while 循环没有判断 slow 是否为空？
答：slow 在 fast 后面，如果 fast 不是空，那么 slow 也肯定不是空。好比快人先去探路，慢人走的都是快人走过的路。
1 | class Solution { |
24.将有序数组转换为二叉搜索树（二叉树-简单）
排序法
分析：BST 的中序遍历是升序的，因此本题等同于根据中序遍历的序列恢复二叉搜索树。因此我们可以以升序序列中的任一个元素作为根节点，以该元素左边的升序序列构建左子树，以该元素右边的升序序列构建右子树，这样得到的树就是一棵二叉搜索树啦～ 又因为本题要求高度平衡，因此我们需要选择升序序列的中间元素作为根节点
1 | class Solution { |
逐行说明
sortedArrayToBST：从整段[0, n-1]开始递归。dfs(nums, lo, hi)：把nums[lo..hi]这段区间转成一棵 BST 并返回根节点。- 结束条件：
lo > hi代表子区间为空，返回null。 - 选根：
mid为中点，nums[mid]做根。 - 递归：左子树来自左半区间
[lo, mid-1]，右子树来自右半区间[mid+1, hi]。
25.合并两个有序链表（简单-链表）
思路：每次在两个链表的头结点里选更小的那个作为新链表的头，然后把它的next指向“剩下部分的合并结果”。
1 | public ListNode mergeTwoLists(ListNode list1, ListNode list2) { |
复杂度与特性
- 时间复杂度：
O(m+n)（每个节点访问一次）。 - 空间复杂度：
O(m+n)（递归调用栈的最大深度，最坏相当于两个表总长度）。 - 代码不创建新节点，直接重用原链表节点，指针重排完成合并。
总结：取两条链表当前更小的头结点当“新头”，然后把它的尾巴和另一条链表继续递归（或迭代）合并。
迭代版
1 | public ListNode mergeTwoListsIter(ListNode l1, ListNode l2) { |
循环结束时，肯定有一条链表先到头，另一条还有剩余（因为它们是升序，所以剩余部分直接接到新链表尾就行）。
用三元运算符简化了：
- 如果
l1不为空，接上l1； - 否则接上
l2。
26.买卖股票的最佳时机（贪心-简单）
1 | public int maxProfit(int[] prices) { |
27.跳跃游戏（贪心-中等）
1 | class Solution { |
1 | class Solution { |
这段代码是通过从后往前遍历的方式来判断是否能跳到数组的最后一个位置。它的核心思想是贪心算法，具体来说是通过追踪能跳到当前元素的最远位置，判断是否能够从初始位置跳到最后一个位置。
代码解读：
-
初始化
：
index用来表示从最后一个位置开始，当前位置能跳到的最远位置。初始时，index = nums.length - 1，即从最后一个位置开始。
-
倒序遍历
：
- 从倒数第二个位置（
nums.length - 2）开始，依次向前遍历整个数组。 - 对于每个位置
i，判断能否通过i + nums[i]（当前位置i能跳到的最大位置）到达index。 - 如果可以到达，说明可以从这个位置跳到当前位置
index，因此更新index为当前位置i。
- 从倒数第二个位置（
-
判断是否能从起始位置跳到最后
：
- 如果遍历结束后，
index变回了起始位置（index == 0），说明从头到尾能跳到最后一个位置，返回true。 - 否则，返回
false。
- 如果遍历结束后，
28.爬楼梯（动态规划-简单）
1 | public int climbStairs(int n) { |
29.合并区间（数组-中等）
给定若干个区间 [start, end]，要求合并所有有交集的区间，返回一个不重叠的新区间数组。
例子：
输入：[[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
因为 [1,3] 和 [2,6] 有交集，合并成 [1,6]。
代码核心思路
1 | class Solution { |
示例运行过程
输入：[[1,3],[2,6],[8,10],[15,18]]
-
排序后：
[[1,3],[2,6],[8,10],[15,18]] -
初始：
ans = [[1,3]] -
遍历
1
[2,6]
：
2 <= 3→ 可以合并，更新右端点：ans = [[1,6]]
-
遍历
1
[8,10]
：
8 > 6→ 无法合并，新建区间：ans = [[1,6],[8,10]]
-
遍历
1
[15,18]
：
15 > 10→ 无法合并，新建区间：ans = [[1,6],[8,10],[15,18]]
最终结果：[[1,6],[8,10],[15,18]]
总结：
这段代码的思路就是 “先排序，再贪心合并”。
- 排序确保区间的合并只可能发生在相邻区间；
- 遍历时用条件判断是否重叠，能合并就更新右端点，否则就新建一个区间。
30.三数之和（双指针 中等）
思路:数组遍历核心想法：
先固定一个数 nums[i]，把问题变成在它右侧找一对数，使得两数和等于 -nums[i]。因为排过序，用左右指针就能在线性时间里完成这一对数的查找；再配合去重，就能得到不重复的三元组。
如果 nums[i]大于 0，则三数之和必然无法等于 0，结束循环
如果 nums[i] == nums[i−1]，则说明该数字重复，会导致结果重复，所以应该跳过
当 sum == 0 时，nums[L] == nums[L+1] 则会导致结果重复，应该跳过，L++
当 sum == 0 时，nums[R] == nums[R−1] 则会导致结果重复，应该跳过，R−−
时间复杂度：O(n2)，n 为数组长度
1 | public static List<List<Integer>> threeSum(int[] nums) { |
为什么这些去重是充分且必要的？
- 外层去重：同一个基准
nums[i]会引出完全相同的一批三元组（因为右侧的候选区间和数值都一样），必须跳过。 - 内层去重（L、R）：在固定
i的情况下，如果nums[L]与下一个相等，或者nums[R]与前一个相等，继续用它们会得到完全相同的三元组，所以要把这些重复值一次性跨过去。
小例子走一遍
1 | nums = [-1, 0, 1, 2, -1, -4]` |
-
i=0(-4): 目标两数和+4，双指针找不到，结束。 -
i=1(-1)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
:
- `L=2(-1), R=5(2)` → sum=0，收录 `[-1,-1,2]`，跳过重复，`L→3, R→4`
- `L=3(0), R=4(1)` → sum=0，收录 `[-1,0,1]`，`L→4, R→3` 结束本轮
- `i=2(-1)`：等于前一个，外层去重跳过。
- 后续最小值 ≥ 0，外层终止。
结果：`[[-1,-1,2], [-1,0,1]]`
## 31.最长连续序列（哈希 中等）
public int longestConsecutive(int[] nums) {
// 使用HashSet存储数组中的所有元素
HashSet
for (int num : nums) {
nums_set.add(num);
}
// 初始化最长连续序列的长度为0
int longestStreak = 0;
for (int num : nums_set) {
// 如果当前数字的前一个数字不在HashSet中，则开始计算以当前数字为首的最长连续序列长度
if (!nums_set.contains(num - 1)) {
int currentNum = num;
int currentStreak = 1;
while (nums_set.contains(currentNum + 1)) {
// 当前数字的后一个数字在HashSet中
currentNum += 1;
// 最长连续序列长度加一
currentStreak += 1;
}
// 更新最长连续序列的长度
longestStreak = Math.max(longestStreak, currentStreak);
}
}
return longestStreak;
}
1 |
|
public int longestConsecutive(int[] nums) {
//如果数组为空，则返回0
if (nums.length == 0) {
return 0;
}
//对数组进行排序
Arrays.sort(nums);
//初始化条件，max为最终求的最长连续序列的长度，curr_len为当前连续序列的长度,last_num为上一个数
int max = 1;
int curr_len = 1;
int last_num = nums[0];
//遍历数组
for (int i = 1; i < nums.length; i++) {
//如果当前数与上一个数相等，则不做处理
if (nums[i] == last_num) {
continue;
}
//如果当前数与上一个数相差1，则说明是连续的
if (nums[i] - last_num == 1) {
curr_len++;
}
//如果当前数与上一个数相差大于1，则说明不是连续的
else {
//更新最长连续序列的长度
max = Math.max(curr_len, max);
//重置当前连续序列的长度
curr_len = 1;
}
//更新上一个数
last_num = nums[i];
}
return Math.max(curr_len, max);
}
1 |
|
public boolean isValidBST(TreeNode root) {
//这是入口方法，直接调用递归函数 isValidBST。在调用时，我们传递了整个树的根节点 root，并将它的有效值范围设为 Long.MIN_VALUE 到 Long.MAX_VALUE，表示初始时没有任何限制。
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean isValidBST(TreeNode node, long minVal, long maxVal) {
if (node == null) {
//递归基础条件：如果当前节点是 null，就返回 true，因为空节点没有违反 BST 的性质。
return true;
}
//当节点小于最小值或者大于最大值时，不是二叉搜索树
//左子树节点必须小于当前节点的值。右子树节点必须大于当前节点的值。
if (node.val <= minVal || node.val >= maxVal) {
return false;
}
return isValidBST(node.left, minVal, node.val) && isValidBST(node.right, node.val, maxVal);
}
return isValidBST(node.left, minVal, node.val) && isValidBST(node.right, node.val, maxVal);
1 |
|
class Solution {
private long pre = Long.MIN_VALUE; // ① 预存当前节点值，用于比较
public boolean isValidBST(TreeNode root) {
if (root == null) { // ② 递归结束条件：空节点
return true;
}
// 递归遍历左子树
if (!isValidBST(root.left)) {
return false; // 左子树验证失败，返回 false
}
// 检查当前节点值是否大于上一个访问节点的值
if (root.val <= pre) { // ③ 中序遍历顺序保证当前节点值应该大于上一个节点
return false; // 当前节点不符合 BST 的要求
}
pre = root.val; // 更新上一个访问的节点值为当前节点
// 递归遍历右子树
return isValidBST(root.right);
}
}
1 |
|
rev(B) + rev(A)
1 |
|
B + rev(A)
1 |
|
B + A
1 |
|
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
k %= n; // 避免 k >= n 的情况
// 1. 反转整个数组
reverse(nums, 0, n - 1);
// 2. 反转前 k 个元素
reverse(nums, 0, k - 1);
// 3. 反转后 n-k 个元素
reverse(nums, k, n - 1);
}
// 工具函数：反转数组的一部分
private void reverse(int[] nums, int start, int end) {
while (i < j) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
i++;
j--;
}
}
}
1 |
|
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[]answer = new int[n];
//answer[i] = (i 左边所有数的乘积) * (i 右边所有数的乘积)
//左侧乘积
int left = 1;
for(int i = 0;i<n;i++){
answer[i]=left;//先把当前左乘积存到结果数组中
left=nums[i]*left;
}
//右侧乘积
int right = 1;
for(int i =n-1;i>=0;i–){
answer[i]=answer[i]right;//在已有的L[i]R[i]
right=rightnums[i];//把nums[i]累进right，供左边那个位置用
}
return answer;
}
1 |
|
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
// 1) 哑结点：统一边界（尤其删除头结点时）
ListNode dummy = new ListNode(0, head);
// 2) 两个指针都从 dummy 出发
ListNode fast = dummy, slow = dummy;
// // 3) fast 先走 n+1 步，保证 fast 与 slow 相隔 n+1 个“结点距离”
// 这样当 fast 走到 null 时，slow 正好停在“待删结点的前一个”
for (int i = 0; i < n + 1; i++) {
fast = fast.next;
}
// 4) fast、slow 同步前进，直到 fast 走到链表末尾(null)
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
// 5) 删除 slow 后面的那个结点（即倒数第 n 个）
slow.next = slow.next.next;
// 6) 返回新头结点（可能头结点被删了，所以不能直接返回 head）
return dummy.next;
}
}
1 |
|
2s = s + nb
=> s = nb
1 |
|
public ListNode detectCycle(ListNode head) {
ListNode fast = head, slow = head;
// 第一次相遇：判断是否有环
while (true) {
if (fast == null || fast.next == null) return null; // 无环
fast = fast.next.next;
slow = slow.next;
if (fast == slow) break; // 有环 -> 第一次相遇
}
// 第二次相遇：找到入口
fast = head; // fast回到头
while (slow != fast) {
slow = slow.next; // 两者一起走
fast = fast.next;
}
return fast; // 相遇点就是入口
}
1 |
|
//两个栈，一个普通栈存储所有元素，另一个辅助栈存储最小值
private Stack
private Stack
public MinStack() {
//初始化
minStack = new Stack<>();
stack = new Stack<>();
}
//入栈操作，同时更新辅助栈的最小值
public void push(int val) {
stack.push(val);
if (minStack.isEmpty() || val <= minStack.peek()) {
minStack.push(val);
}
}
//出栈操作，同时更新辅助栈的最小值
public void pop() {
//如果栈顶元素是最小值，则辅助栈也出栈
if (stack.pop().equals(minStack.peek())) {
minStack.pop();
}
}
//获取栈顶元素
public int top() {
return stack.peek();
}
//获取栈中的最小值
public int getMin() {
return minStack.peek();
}
1 |
|
public int kthSmallest(TreeNode root, int k) {
// 中序遍历二叉搜索树，得到有序数组->中序遍历后可以得到有序数组，直接返回第 k 个元素即可
List
inorder(root, list);
// 返回第 k 个元素
return list.get(k - 1);
}
// 中序遍历二叉搜索树
private void inorder(TreeNode root, List
// 递归终止条件
if (root == null) return;
// 中序遍历二叉搜索树左子树
inorder(root.left, list);
// 将根节点的值加入到列表中
list.add(root.val);
// 中序遍历二叉搜索树右子树
inorder(root.right, list);
}
1 |
|
class Solution {
int res, k;
void dfs(TreeNode root) {
if (root == null) return;
// 1) 递归左子树
dfs(root.left);
// 2) 访问当前节点
if (k == 0) return; // 已找到结果，后面不用再遍历
if (--k == 0) res = root.val; // 第 k 次访问到结点时，记录答案
// 3) 递归右子树
dfs(root.right);
}
public int kthSmallest(TreeNode root, int k) {
this.k = k; // 把目标 k 存为类变量
dfs(root);
return res;
}
}
1 |
|
class Solution {
public String decodeString(String s) {
StringBuilder res = new StringBuilder(); // 当前的临时结果
int multi = 0; // 当前的倍数
LinkedList
LinkedList
for (char c : s.toCharArray()) {
if (c == '[') {
// 保存现场
stack_multi.addLast(multi);
stack_res.addLast(res.toString());
// 重置
multi = 0;
res = new StringBuilder();
}
else if (c == ']') {
// 取出倍数和上一个结果
int cur_multi = stack_multi.removeLast();
StringBuilder tmp = new StringBuilder();
for (int i = 0; i < cur_multi; i++) tmp.append(res);
// 拼接结果
res = new StringBuilder(stack_res.removeLast() + tmp);
}
else if (Character.isDigit(c)) {
// 累计 multi，考虑多位数
multi = multi * 10 + (c - '0');
}
else {
// 普通字母，加入结果
res.append(c);
}
}
return res.toString();
}
}
1 |
|
class Solution {
public ListNode sortList(ListNode head) {
// 1) 递归终止：空或单节点天然有序
if (head == null || head.next == null) return head;
// 2) 快慢指针找中点（fast 从 head.next 起步）
ListNode fast = head.next, slow = head, prev = null;
while (fast != null && fast.next != null) {
slow = slow.next; // 慢走一步
fast = fast.next.next; // 快走两步
}
// 3) 断开成两段 [head..slow] 和 [slow.next..]
ListNode mid = slow.next;
slow.next = null;
// 4) 分治：分别对左右两段排序
ListNode left = sortList(head);
ListNode right = sortList(mid);
// 5) 归并：合并两个有序链表
ListNode dummy = new ListNode(0), cur = dummy;
while (left != null && right != null) {
if (left.val < right.val) { // 注意：这里“严格小于”
cur.next = left; left = left.next;
} else {
cur.next = right; right = right.next;
}
cur = cur.next;
}
cur.next = (left != null) ? left : right; // 拼上剩余
return dummy.next;
}
}
1 |
|
fast
1 |
|
head.next
1 |
|
1
/
2 5
/ \
3 4 6
//将 1 的左子树插入到右子树的地方
1
2 5
/ \
3 4 6
//将原来的右子树接到左子树的最右边节点
1
2
/ \
3 4
5
6
//将 2 的左子树插入到右子树的地方
1
2
\
3 4
5
6
//将原来的右子树接到左子树的最右边节点
1
2
\
3
4
5
6
class Solution {
public void flatten(TreeNode root) {
while (root != null) {
if (root.left != null) {
// 找到左子树的最右节点
TreeNode pre = root.left;
while (pre.right != null) {
pre = pre.right;
}
// 原右子树接到左子树最右节点
pre.right = root.right;
// 左子树移到右边
root.right = root.left;
root.left = null;
}
// 处理下一个节点
root = root.right;
}
}
}
1 |
|
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) return head; // 递归终止
ListNode next = head.next; // 下一个节点
head.next = swapPairs(next.next); // 递归交换后续链表
next.next = head; // 完成这两个节点的交换
return next; // 返回新头节点
}
1 |
|
swapPairs(1)
1 |
|
2 -> 1 -> 4 -> 3
1 |
|
//全排列：给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
class Solution {
public List<List
List<List
List
backtrack(nums, res, path); // 递归搜索
return res;
}
// 回溯算法
private void backtrack(int[] nums, List<List<Integer>> res, List<Integer> path) {
if (path.size() == nums.length) { // ✨ 终止：选满 n 个
res.add(new ArrayList<>(path)); // 必须拷贝一份
return;
}
for (int i = 0; i < nums.length; i++) { // 枚举下一位的选择
if (path.contains(nums[i])) continue; // 这个数用过了，跳过
path.add(nums[i]); // 做选择
backtrack(nums, res, path); // 递归
path.remove(path.size() - 1); // 撤销选择（回溯）
}
}
}
1 |
|
class Solution {
List<List
boolean[] used;
public List<List
List
//初始化used数组
used = new boolean[nums.length];
backtrack(nums, path);// 递归搜索
return res;
}
//回溯算法
private void backtrack(int[] nums, List<Integer> path) {
if (path.size() == nums.length) { // ✨ 终止：选满 n 个
res.add(new ArrayList<>(path)); // 必须拷贝一份
return;
}
//递归数组
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;//这个数用过了，跳过
used[i] = true;//标记为已使用
path.add(nums[i]); // 做选择
backtrack(nums, path); // 递归
path.remove(path.size() - 1); // 撤销选择（回溯）
used[i] = false;
}
}
}
1 |
|
List<List<Integer>> res = new ArrayList<>(); // 收集所有排列
List<Integer> path = new ArrayList<>();// 当前构造中的“路径/前缀”
public List<List<Integer>> subsets(int[] nums) {
backtrack(nums, 0);// 递归搜索
return res;
}
//回溯算法
private void backtrack(int[] nums, int startIndex) {
//每个节点都是一个子集
res.add(new ArrayList<>(path)); // 必须拷贝一份
//递归数组
for (int i = startIndex; i < nums.length; i++) {
path.add(nums[i]); // 做选择
backtrack(nums, i+1); // 递归
path.remove(path.size() - 1); // 撤销选择（回溯）
}
}
1 |
|
depth == res.size()
1 |
|
public List
if(root == null) return new ArrayList<>();
List
dfs(root, 0, res);
return res;
}
private void dfs(TreeNode node, int depth, List
if (node == null) return;
// 只有第一次到达某一层时，才记录该层的节点值
if (depth == res.size()) {
res.add(node.val);
}
dfs(node.right, depth + 1, res);
dfs(node.left, depth + 1, res);
}
1 |
|
public Node copyRandomList(Node head) {
if (head == null) return null;
// ① 在每个原节点后插入克隆节点
Node cur = head;
while (cur != null) {
Node clone = new Node(cur.val);
clone.next = cur.next;
cur.next = clone;
cur = clone.next;
}
// ② 利用“克隆紧挨原节点”的结构复制 random
cur = head;
while (cur != null) {
if (cur.random != null) {
cur.next.random = cur.random.next;
}
cur = cur.next.next;
}
// ③ 拆分：还原原链表 + 抽出克隆链表
cur = head;
Node cloneHead = cur.next;
while (cur != null) {
Node next = cur.next; // next 是克隆节点
cur.next = next.next; // 原节点跳过克隆，连回原链
if (next.next != null) {
next.next = next.next.next; // 克隆节点指向下一个克隆
}
cur = cur.next; // 前进到下一个原节点
}
return cloneHead;
}
1 |
|
class LRUCache {
//定义节点信息，每一个节点都包含key,value,prev,next四个属性
private static class Node {
int key;
int value;
Node prev;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
//定义容量，双向链表头尾哨兵节点，哈希表
private final int capacity;
// 哑结点：初始 self-loop，方便统一增删
private final Node dummy = new Node(0,0);
// 哈希表：key -> 节点，方便快速定位到节点
private final HashMap<Integer, Node> map = new HashMap<>();
/**
* 以 正整数 作为容量 capacity 初始化 LRU 缓存
* @param capacity
*/
public LRUCache(int capacity) {
this.capacity = capacity;
dummy.next = dummy;
dummy.prev = dummy;
}
/**
* 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
* @param key
* @return
*/
public int get(int key) {
Node node = map.get(key);
if (node == null) return -1;
// 访问后变为最近使用：移到表头
moveToHead(node);
return node.value;
}
/**
* 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。
* 如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
* @param key
* @param value
*/
public void put(int key, int value) {
Node node = map.get(key);
if (node != null) {
// 已存在：更新值 + 移到表头
node.value = value;
moveToHead(node);
} else {
// 不存在：新建节点，挂到表头
Node newNode = new Node(key, value);
map.put(key, newNode);
addToHead(newNode);
// 若超容量：删除尾部最久未使用节点
if (map.size() > capacity) {
Node tail = removeTail();
map.remove(tail.key);
}
}
}
//删除节点
/* ---------- 双向链表工具方法 ---------- */
// 从链表中摘除 node
private void unlink(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
// 可选：帮助 GC
// node.prev = node.next = null;
}
// 把 node 插到 dummy 之后（表头）
private void addToHead(Node node) {
node.next = dummy.next;
node.prev = dummy;
dummy.next.prev = node;
dummy.next = node;
}
// 将 node 移到表头
private void moveToHead(Node node) {
unlink(node);
addToHead(node);
}
// 移除尾部真实节点（dummy.prev），并返回它
private Node removeTail() {
Node tail = dummy.prev;
unlink(tail);
return tail;
}
}
1 |
|
class LRUCache {
private final int capacity;
private final Map<Integer, Integer> cache = new LinkedHashMap<>(); // 内置 LRU
public LRUCache(int capacity) {
this.capacity = capacity;
}
public int get(int key) {
// 删除 key，并利用返回值判断 key 是否在 cache 中
Integer value = cache.remove(key);
if (value != null) { // key 在 cache 中
cache.put(key, value);
return value;
}
// key 不在 cache 中
return -1;
}
public void put(int key, int value) {
// 删除 key，并利用返回值判断 key 是否在 cache 中
if (cache.remove(key) != null) { // key 在 cache 中
cache.put(key, value);
return;
}
// key 不在 cache 中，那么就把 key 插入 cache，插入前判断 cache 是否满了
if (cache.size() == capacity) { // cache 满了
Integer eldestKey = cache.keySet().iterator().next();
cache.remove(eldestKey); // 移除最久未使用 key
}
cache.put(key, value);
}
}
1 |
|
class Solution {
//数字到字母的映射
private static final String[] LETTERS = {
“”, // 0
“”, // 1
“abc”, // 2
“def”, // 3
“ghi”, // 4
“jkl”, // 5
“mno”, // 6
“pqrs”,// 7
“tuv”, // 8
“wxyz” // 9
};
public List<String> letterCombinations(String digits) {
List<String> ans = new ArrayList<>();// 存放结果
if (digits == null || digits.length() == 0) return ans;
StringBuilder path = new StringBuilder();
backtrack(ans, path, digits, 0);
return ans;
}
private void backtrack(List<String> ans, StringBuilder path, String digits, int index) {
//如果遍历到字符串末尾，则将path加入结果集
if (index == digits.length()) {
ans.add(path.toString());
return;
}
//获取当前数字对应的字母
//digits.charAt(index) - '0'表示的是字符对应的数字，例如'2'-'0'=2
int digit = digits.charAt(index) - '0';
//遍历当前数字对应的字母
String letters = LETTERS[digit];
for (char letter : letters.toCharArray()) {
path.append(letter);
//递归遍历下一个数字
backtrack(ans, path, digits, index + 1);
//回溯，撤销选择
path.deleteCharAt(path.length() - 1);
}
}
}
1 |
|
class Solution {
// 把中序数组的“值 -> 下标”存起来，O(1) 定位根在中序中的位置
private Map<Integer, Integer> idx;
// 先序数组
private int[] preorder;
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
// 把中序数组的“值 -> 下标”存起来，O(1) 定位根在中序中的位置
idx = new HashMap<>(inorder.length * 2);
for (int i = 0; i < inorder.length; i++) idx.put(inorder[i], i);
// 递归构建：先序区间 [0..n-1]，中序区间 [0..n-1]
return build(0, preorder.length - 1, 0, inorder.length - 1);
}
// 递归函数：用“先序[preL..preR] + 中序[inL..inR]”这两个区间，构造出对应的子树，并返回其根节点
private TreeNode build(int preL, int preR, int inL, int inR) {
if (preL > preR) return null; // 空区间：没有节点
int rootVal = preorder[preL]; // 先序的第一个就是当前子树的“根”
int inRoot = idx.get(rootVal); // 根在中序中的位置
int leftSize = inRoot - inL; // 左子树节点数 = 中序左半部分的长度
TreeNode root = new TreeNode(rootVal);
// 左子树：
// 先序：根之后的 leftSize 个，即 [preL+1 .. preL+leftSize]
// 中序：根左侧区间 即 [inL .. inRoot-1]
root.left = build(preL + 1, preL + leftSize, inL, inRoot - 1);
// 右子树：
// 先序：左子树那段之后 即 [preL+leftSize+1 .. preR]
// 中序：根右侧区间 即 [inRoot+1 .. inR]
root.right = build(preL + leftSize + 1, preR, inRoot + 1, inR);
return root;
}
}
1 |
|
preorder = [3, 9, 20, 15, 7] inorder = [9, 3, 15, 20, 7]
1 |
|
3
/ \
9 20
/ \
15 7
1 |
|
class Solution {
private int pre = 0; // 前序数组的游标
private int in = 0; // 中序数组的游标
public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder, inorder, Long.MAX_VALUE); // 初始 stop 设置为无穷大
}
private TreeNode build(int[] preorder, int[] inorder, long stop) {
if (pre == preorder.length) return null; // 前序走完了
// 中序遇到 stop，说明当前子树结束
if (inorder[in] == stop) {
in++;
return null;
}
// 取当前前序的节点值，作为根
int rootVal = preorder[pre++];
TreeNode root = new TreeNode(rootVal);
// 递归构造左子树，直到遇到 rootVal 为止
root.left = build(preorder, inorder, rootVal);
// 递归构造右子树，直到遇到 stop 为止
root.right = build(preorder, inorder, stop);
return root;
}
}
1 |
|
：相当于一个“哨兵值”，表示递归到某个子树的边界。
-
构造左子树时，边界是 当前根节点值。
-
构造右子树时，边界是 父递归传下来的 stop 值。
-
pre：每次从前序里取一个新值（就是新的根）。 -
in：在中序中不断前进，直到遇到stop，说明当前子树已经结束。
执行过程示例
以 preorder = [3,9,20,15,7]，inorder = [9,3,15,20,7] 为例：
-
pre=031
2
3
，取TreeNode(3)1
2
3
当根，创建31
2
3
4
5
6
7
8
9
10
11
12
13
14
15
。
- 左子树的 `stop = 3`
- 右子树的 `stop = MAX_VALUE`
2. 进入左子树：
- `pre=1`，取 `9` 当根。
- 左子树的 `stop = 9` → 遇到 `inorder[in] == 9` → 返回 `null`
- 右子树的 `stop = 3` → 遇到 `inorder[in] == 3` → 返回 `null`
- 返回节点 `9`
3. 回到根3 / \ 9 20 / \ 15 71
2
3
4
5
6
7
8
9
10
，进入右子树：
- `pre=2`，取 `20` 当根。
- 左子树的 `stop = 20` → `pre=3`，取 `15`，左右都返回 `null`。
- 右子树的 `stop = MAX_VALUE` → `pre=4`，取 `7`，左右返回 `null`。
- 返回节点 `20`，包含子树 `15` 和 `7`
最终得到树：
1 |
|
//括号生成
// 给定一个整数 n，生成所有由左右括号组成的合法的（格式正确的）长度为 2n 的字符串
// 例如：输入: n = 3, 输出: [“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]
class Solution {
public List
//创建结果集
List
if (n == 0) {
return res;
}
//定义一个StringBuilder
StringBuilder sb = new StringBuilder();
//递归生成括号组合
backtrack(res, sb, 0, 0, n);
return res;
}
private void backtrack(List<String> res, StringBuilder sb, int open, int close, int max) {
//1.处理非法结果
//如果左括号数量大于n或者右括号数量大于左括号，则不合法
if (open > max || close > open) {
return;
}
//如果左括号和右括号的数量都等于n，则找到了一个合法的组合
if (open == max && close == max) {
res.add(sb.toString());
return;
}
//2.递归生成左右括号组合
//递归生成左括号
sb.append('(');
backtrack(res, sb, open + 1, close, max);
sb.deleteCharAt(sb.length() - 1);
//递归生成右括号
sb.append(')');
backtrack(res, sb, open, close + 1, max);
sb.deleteCharAt(sb.length() - 1);
}
}
1 |
|
/**
- @author geqian
- @version 1.0
- @description 组合总和
- 回溯法
- 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，
- 并以列表形式返回。你可以按 任意顺序 返回这些组合。
- candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
- @date 2025/9/9 10:27
*/
class Solution {
public List<List
if(candidates == null || candidates.length == 0) return new ArrayList<>();
List<List
List
backtrack(candidates, target, 0, res, path);// 从下标 0 开始做选择
return res;
}
// 回溯法
private void backtrack(int[] candidates, int target, int startIndex, List<List
if(target < 0) return; // 剪枝：和已经超了，不可能再凑成0
if(target == 0){ // 命中：把当前 path 拷贝进答案
res.add(new ArrayList<>(path));
return;
}
for(int i = startIndex; i < candidates.length; i++){
if(candidates[i] > target) continue;// 剪枝（不排序时用 continue，不能 return）
path.add(candidates[i]);// 做选择
backtrack(candidates, target - candidates[i], i, res, path);// 传 i：允许重复选这个数
// 回溯，撤销选择
path.remove(path.size() - 1);
}
}
}
1 |
|
import java.util.*;
class Solution {
public List<List
Arrays.sort(candidates); // 先排好序
List<List
backtrack(candidates, target, 0, new ArrayList<>(), res);
return res;
}
private void backtrack(int[] a, int target, int start, List<Integer> path, List<List<Integer>> res) {
if (target == 0) {
res.add(new ArrayList<>(path));
return;
}
for (int i = start; i < a.length; i++) {
if (a[i] > target) break; // 排序后可直接 break
path.add(a[i]);
backtrack(a, target - a[i], i, path, res); // i：可重复用
path.remove(path.size() - 1);
}
}
}
1 |
|
class Solution {
public boolean exist(char[][] board, String word) {
int m = board.length;// 行数
int n = board[0].length;// 列数
boolean[][] visited = new boolean[m][n];// 标记访问过的点
// 遍历二维数组，从每个点开始尝试搜索
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 从每个点开始尝试搜索，如果找到匹配的单词，返回 true
if (backtrack(board, word, visited, i, j, 0)) return true;
}
}
// 所有点都遍历完了，都没有找到匹配的单词
return false;
}
// 回溯法
private boolean backtrack(char[][] board, String word, boolean[][] visited, int i, int j, int index) {
// 终止条件：遍历到最后一个字符，返回 true
if (index == word.length()) return true;
// 边界条件：超出范围，或者已经访问过，或者当前字符不匹配
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || visited[i][j] || board[i][j] != word.charAt(index)) return false;
visited[i][j] = true;// 做选择，标记访问过
// 递归遍历上、下、左、右四个方向
boolean res = backtrack(board, word, visited, i - 1, j, index + 1);//上
if (!res) res = backtrack(board, word, visited, i + 1, j, index + 1);//下
if (!res) res = backtrack(board, word, visited, i, j - 1, index + 1);//左
if (!res) res = backtrack(board, word, visited, i, j + 1, index + 1);//右
visited[i][j] = false;// 撤销选择，恢复现场
return res;
}
}
1 |
|
public boolean exist(char[][] board, String word) {
int m = board.length;// 行数
int n = board[0].length;// 列数
boolean[][] visited = new boolean[m][n];// 标记访问过的点
// 遍历二维数组，从每个点开始尝试搜索
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 从每个点开始尝试搜索，如果找到匹配的单词，返回 true
if (backtrack(board, word, visited, i, j, 0)) return true;
}
}
// 所有点都遍历完了，都没有找到匹配的单词
return false;
}
1 |
|
private boolean backtrack(char[][] board, String word, boolean[][] visited, int i, int j, int index) {
// 终止条件：遍历到最后一个字符，返回 true
if (index == word.length()) return true;
// 边界条件：超出范围，或者已经访问过，或者当前字符不匹配
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || visited[i][j] || board[i][j] != word.charAt(index))
return false;
visited[i][j] = true; // 做选择，标记访问过
// 递归遍历上、下、左、右四个方向
boolean res = backtrack(board, word, visited, i - 1, j, index + 1);//上
if (!res) res = backtrack(board, word, visited, i + 1, j, index + 1);//下
if (!res) res = backtrack(board, word, visited, i, j - 1, index + 1);//左
if (!res) res = backtrack(board, word, visited, i, j + 1, index + 1);//右
visited[i][j] = false; // 撤销选择，恢复现场（关键！回溯）
return res;
}
1 |
|
false
1 |
|
board = [
[‘A’,‘B’,‘C’,‘E’],
[‘S’,‘F’,‘C’,‘S’],
[‘A’,‘D’,‘E’,‘E’]
]
word = “ABCCED”
1 |
|
class Solution {
public List<List
if(s == null || s.length() == 0){
return new ArrayList<>();
}
// 存放结果集
List<List
// 存放当前路径
List
// 回溯法,从0开始遍历字符串s
backtrack(s, 0, res, path);
return res;
}
private void backtrack(String s, int i, List<List<String>> res, List<String> path) {
// 终止条件：切到了字符串末尾，说明当前 path 是一个合法方案
if(i == s.length()){
res.add(new ArrayList<>(path));// 必须拷贝
return;
}
// 枚举“下一刀”切到哪里：j 从 i 走到 s.length()-1
for(int j = i; j < s.length(); j++){
// 剪枝：只有 s[i..j] 是回文才继续
if(!isPalindrome(s, i, j)){
continue;
}
// 做选择：把这一段加入路径
path.add(s.substring(i, j+1));
// 递归：从 j+1 处继续切
backtrack(s, j+1, res, path);
// 撤销选择（回溯）
path.remove(path.size()-1);
}
}
// 判断是否是回文串，用双指针从两端往中间比较，O(len) 时间判断 [i..j] 是否回文。
private boolean isPalindrome(String s, int i, int j) {
while(i < j){
// 如果当前字符不相等,则不是回文串
if(s.charAt(i++) != s.charAt(j--)){
return false;
}
}
return true;
}
}
1 |
|
class Solution {
/**
* 计算二叉树中路径和等于目标值的路径数目
* @param root 二叉树的根节点
* @param targetSum 目标路径和
* @return 满足条件的路径数目
*/
public int pathSum(TreeNode root, int targetSum) {
return pathSum(root, (long) targetSum);
}
/**
* 递归计算以当前节点为根的所有路径中满足条件的路径数目
* @param root 当前子树根节点
* @param target 目标路径和
* @return 满足条件的路径数目
*/
private int pathSum(TreeNode root, long target) {
if (root == null) return 0;
// 计算从当前节点开始的路径 + 左子树路径 + 右子树路径
return pathSumFrom(root, target)
+ pathSum(root.left, target)
+ pathSum(root.right, target);
}
/**
* 计算从当前节点开始向下满足条件的路径数目
* @param node 当前节点
* @param target 剩余需要满足的路径和
* @return 满足条件的路径数目
*/
private int pathSumFrom(TreeNode node, long target) {
if (node == null) return 0;
long remain = target - (long) node.val;
// 如果当前节点值等于剩余目标值，则计数1
int cnt = (target == (long) node.val) ? 1 : 0;
// 递归计算左子树和右子树
return cnt + pathSumFrom(node.left, remain)
+ pathSumFrom(node.right, remain);
}
}
1 |
|
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;// 行数
int n = matrix[0].length;// 列数
// 从右上角开始搜索
int i = 0, j = n - 1;
while (i < m && j >= 0) {
if (matrix[i][j] == target) {
// 找到目标值，返回true
return true;
} else if (matrix[i][j] > target) {
// 当前值大于目标值，向左移动
j–;
} else {
// 当前值小于目标值，向下移动
i++;
}
}
// 遍历完整个矩阵，没有找到目标值，返回false
return false;
}
}
1 |
|
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;// 行数
int n = matrix[0].length;// 列数
// 从右上角开始搜索
int i = 0, j = n - 1;
while (i < m && j >= 0) {
if (matrix[i][j] == target) {
// 找到目标值，返回true
return true;
} else if (matrix[i][j] > target) {
// 当前值大于目标值，向左移动
j–;
} else {
// 当前值小于目标值，向下移动
i++;
}
}
// 遍历完整个矩阵，没有找到目标值，返回false
return false;
}
}
1 |
|
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length;// 行数
int n = matrix[0].length;// 列数
boolean[] rowZeroes = new boolean[m];// 记录哪些行需要置零
boolean[] colZeroes = new boolean[n];// 记录哪些列需要置零
// 遍历矩阵，记录哪些行和列需要置零
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
rowZeroes[i] = true;
colZeroes[j] = true;
}
}
}
// 遍历矩阵，将需要置零的行和列都置为零
//行列分开置零，避免重复置零
//首先是行置零，然后是列置零
for (int i = 0; i < m; i++) {
if (rowZeroes[i]) {
for (int j = 0; j < n; j++) {
matrix[i][j] = 0;
}
}
}
//列置零
for (int j = 0; j < n; j++) {
if (colZeroes[j]) {
for (int i = 0; i < m; i++) {
matrix[i][j] = 0;
}
}
}
}
}
1 |
|
class Solution {
public void rotate(int[][] matrix) {
int m =matrix.length;//行数
int n = matrix[0].length;//列数
// 先沿对角线翻转
for (int i = 0; i < m; i++) {
for (int j = i; j < n; j++) {
//交换行列元素:行列互换，第一列变成了第一行
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
// 再按行左右翻转
for (int i = 0; i < m; i++) {
for (int j = 0; j < n / 2; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[i][n - j - 1];
matrix[i][n - j - 1] = temp;
}
}
}
}
1 |
|
class Solution {
public int[] searchRange(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
//二分查找，查找第一个等于target的元素和最后一个等于target的元素
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
//找到目标值，继续向左查找第一个等于target的元素
int start = mid;
while (start >= 0 && nums[start] == target) {
start–;
}
//找到目标值，继续向右查找最后一个等于target的元素
int end = mid;
while (end < nums.length && nums[end] == target) {
end++;
}
return new int[]{start + 1, end - 1};
}
}
return new int[]{-1, -1};
}
}
1 |
|
class Solution {
//返回target的下标值，若不存在返回-1
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
//二分查找
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
//先判断mid是否为目标值
if (nums[mid] == target) {
return mid;
}
//左半边有序
if (nums[left] <= nums[mid]) {
//判断target是否在左半边
if (nums[left] <= target && nums[mid] >= target) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
//右半边有序
if (nums[mid] <= target && nums[right] >= target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
}
1 |
|
class Solution {
public int findMin(int[] nums) {
if(nums.length == 1) return nums[0];
int left = 0;
int right = nums.length - 1;
//二分查找
while(left < right){
int mid = (right + left) / 2;
//如果中间值大于右边，说明最小值在右半边
if(nums[mid] > nums[right]){
//最小值在右半边
left = mid + 1;
}else{
//最小值在左半边或者就是中间的值
right = mid;
}
}
//因为是升序排列，所以最小值一定在left的位置
return nums[left];
}
}
1 |
|
public List
int m = matrix.length; // 行数
int n = matrix[0].length; // 列数
List
// 定义四条边界：当前未遍历区域是 [top..bottom] × [left..right]
int top = 0, bottom = m - 1, left = 0, right = n - 1;
// 输出总数达到 m*n 即结束
while (res.size() < m * n) {
// 1) 走上边：固定行 top，列从 left -> right
if (top <= bottom) {
for (int j = left; j <= right; j++) res.add(matrix[top][j]);
top++; // 上边用完，往下缩一行
}
// 2) 走右边：固定列 right，行从 top -> bottom
if (left <= right) {
for (int i = top; i <= bottom; i++) res.add(matrix[i][right]);
right--; // 右边用完，往左缩一列
}
// 3) 走下边：固定行 bottom，列从 right -> left
if (top <= bottom) {
for (int j = right; j >= left; j--) res.add(matrix[bottom][j]);
bottom--; // 下边用完，往上缩一行
}
// 4) 走左边：固定列 left，行从 bottom -> top
if (left <= right) {
for (int i = bottom; i >= top; i--) res.add(matrix[i][left]);
left++; // 左边用完，往右缩一列
}
}
return res;
}
1 |
|
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return Collections.emptyList();
1 |
|
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if (n == 0) return 0;//当没有长度返回0
if (n == 1) return nums[0];//当只有一个房间时，直接返回金额
int[] dp = new int[n];//定义dp数组，dp[i]表示偷到第i个房间时能得到的最大金额
dp[0] = nums[0];//初始化dp数组，第一个房间金额即为最大金额
dp[1] = Math.max(nums[0], nums[1]);//第二个房间金额为前两个房间的最大值
for (int i = 2; i < n; i++) {
/**
* 对第 i 个房子，有两种选择：
* 1.不偷第 i 个房子
* 那么最大金额就是前一个房子能偷到的最大金额：
* dp[i - 1]
* 2.偷第 i 个房子
* 由于相邻房子不能偷，所以第 i-1 个房子一定不能偷。
* 最大金额是：
* dp[i - 2] + nums[i]
*/
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[n - 1];
}
}
1 |
|
public int numSquares(int n) {
if (n == 0) return 0;
int[] dp = new int[n + 1];
// 1) 初始化
for (int i = 1; i <= n; i++) {
dp[i] = i; // 最坏情况：i = 1^2 + 1^2 + ... + 1^2（i 个 1），所以上界是 i
}
// 2) 状态转移
for (int i = 1; i <= n; i++) { // 逐个求 dp[i]
for (int j = 1; j * j <= i; j++) { // 尝试最后一个平方数是 j^2
dp[i] = Math.min(dp[i], dp[i - j*j] + 1);
// 解释：把 i 拆成 (i - j^2) + j^2
// 其中 dp[i - j^2] 是“凑成 i - j^2 的最优解”，再加上一个 j^2，共 +1 个
}
}
return dp[n];
}
1 |
|
：可选平方数只有
1 | 1 |
-
dp[1] = min(1, dp[0] + 1 = 1)→1 -
i = 211
2
3
：平方数：平方数1
2
3
4
5
- `dp[2] = min(2, dp[1] + 1 = 2)` → `2`
- ```
i = 3- `dp[3] = min(3, dp[2] + 1 = 3)` → `3`1
1
-
i = 41, 41
2
3
：平方数：平方数1
2
3
4
5
6
- 用 `1`：`dp[3] + 1 = 4`
- 用 `4`：`dp[0] + 1 = 1` → **最优是 1（4）**
- ```
i = 5- 用 `1`：`dp[4] + 1 = 2` - 用 `4`：`dp[1] + 1 = 2` → **最优 2（4+1）**1
1, 4
-
i = 61, 41
2
3
：平方数：平方数1
2
3
4
5
6
- 用 `1`：`dp[5] + 1 = 3`
- 用 `4`：`dp[2] + 1 = 3` → **最优 3（4+1+1）**
- ```
i = 7- 用 `1`：`dp[6] + 1 = 4` - 用 `4`：`dp[3] + 1 = 4` → **最优 4**1
1, 4
-
i = 81, 41
2
3
：平方数：平方数1
2
3
4
5
6
- 用 `1`：`dp[7] + 1 = 5`
- 用 `4`：`dp[4] + 1 = 2` → **最优 2（4+4）**
- ```
i = 9- 用 `1`：`dp[8] + 1 = 3` - 用 `4`：`dp[5] + 1 = 3` - 用 `9`：`dp[0] + 1 = 1` → **最优 1（9）**1
1, 4, 9
-
i = 101, 4, 91
2
3
：：1
2
3
4
5
- 得到 **2（9+1）**
- ```
i = 11- 得到 **3（9+1+1）**1
1, 4, 9
-
i = 121, 4, 91
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
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
- 用 `1`：`dp[11] + 1 = 4`
- 用 `4`：`dp[8] + 1 = 3`
- 用 `9`：`dp[3] + 1 = 4` → **最优 3（4+4+4）**
因此 `dp[12] = 3`，与题目样例一致。
初始化为什么是 `dp[i] = i`？
这是一个**安全上界**：
任何 `i` 都能用 `i` 个 `1^2` 凑出来，因此“最坏”需要 `i` 个数，这样初始化后，后续一旦找到更好的组合，就会被 `Math.min` 替换掉。
总结一句话
把「最少平方数和为 n」转化为**完全背包**：
`dp[i] = min(dp[i], dp[i - j^2] + 1)`，外层枚举 `i`，内层枚举所有平方数 `j^2`，逐步把更优的方案“压”到 `dp[i]` 上，最终得到 `dp[n]`。
## 65.零钱兑换（中等 动态规划）
给定硬币面额 `coins`，任取数量，最少用多少枚能凑出 `amount`。凑不出就返回 `-1`。
思路分解
1) 状态定义
- `dp[i]` 表示**恰好**凑出金额 `i` 所需的**最少硬币数量**。
- `dp[0] = 0`（Java 默认 0）；其他位置先设成“不可达”。
- 状态转移
对每个目标金额 `i`，尝试用每种面额 `coin` 作为**最后一枚**：
- 如果 `coin <= i`，且 `dp[i - coin]` 可达（不是 `MAX_VALUE`），
那么：
`dp[i] = min(dp[i], dp[i - coin] + 1)`
含义：凑出 `i - coin` 的最优解 + 这一枚 `coin`。
> 这正是完全背包的转移：**同一枚硬币可以重复使用**，因为我们从 `dp[i - coin]` 过来时，依然可以继续用 `coin`。
3) 初始化与不可达
- `dp[i]` 初始为 `Integer.MAX_VALUE`，表示**暂不可达**。
- 判断条件 `dp[i - coin] != Integer.MAX_VALUE` 的目的是**避免溢出**（`MAX_VALUE + 1` 会溢出为负数），也表示只有子问题可达，当前问题才有可能可达。
- 循环顺序（为什么“金额在外、硬币在内”？）
- 这是完全背包的两种等价写法之一：
- **写法 A（本题）：**
`for (i = 1..amount) for (coin : coins) 更新 dp[i]`
- **写法 B：**
`for (coin : coins) for (i = coin..amount) 更新 dp[i]`
- 两者都会允许重复使用硬币，都是对的。本题使用写法 A。
- 边界与返回
- `amount == 0` 直接返回 0。
- `dp[amount]` 仍是 `MAX_VALUE` 说明不可达 → 返回 `-1`。
public int coinChange(int[] coins, int amount) {
if (amount == 0) return 0;
int[] dp = new int[amount + 1]; // dp[i]：恰好凑出金额 i 的最少硬币数
for (int i = 1; i <= amount; i++) {
dp[i] = Integer.MAX_VALUE; // 初始为“不可达”
for (int coin : coins) {
if (coin <= i && dp[i - coin] != Integer.MAX_VALUE) { // 避免溢出
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}
1 |
|
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
// 结果数组
int[] answer = new int[temperatures.length];
// 单调栈，存放索引
Stack
// 从左向右遍历温度数组
for (int i = 0; i < temperatures.length; ++i) {
// 如果栈不为空，且当前温度大于栈顶索引对应的温度
while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
// 弹出栈顶索引，并计算天数差
int prevIndex = stack.pop();
answer[prevIndex] = i - prevIndex;
}
// 将当前索引压入栈中
stack.push(i);
}
return answer;
}
}
1 |
|
class Solution {
public List
// 边界条件判断
if(s == null || s.length() == 0) return new ArrayList<>();
int[] last = new int[26];
// 记录每个字母最后出现的位置
for(int i = 0; i < s.length(); i++){
last[s.charAt(i) - ‘a’] = i;
}
// 记录每个片段的长度
List
// 记录当前片段的开始和结束位置
int start = 0, end = 0;
// 遍历字符串，更新当前片段的结束位置
for(int i = 0; i < s.length(); i++){
// 更新当前片段的结束位置
end = Math.max(end, last[s.charAt(i) - ‘a’]);
// 如果当前位置是当前片段的结束位置，则将当前片段的长度加入结果列表
if(i == end){
res.add(end - start + 1);
start = end + 1;
}
}
return res;
}
}
1 |
|
int[] last = new int[26];
for (int i = 0; i < s.length(); i++) {
last[s.charAt(i) - ‘a’] = i;
}
1 |
|
List
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
end = Math.max(end, last[s.charAt(i) - ‘a’]); // 片段必须覆盖到当前字符的最远处
if (i == end) { // 到达当前片段的最右边界，可以切分
res.add(end - start + 1);
start = end + 1; // 开启下一个片段
}
}
1 |
|
class Solution {
public int jump(int[] nums) {
int n = nums.length;
int maxPos = 0;// 当前能达到的最远位置
int end = 0;// 当前能达到的最远位置的最后一个元素的位置
int step = 0;// 跳跃次数
// 从第一个元素开始遍历，直到倒数第二个元素
for(int i = 0; i < n - 1; i++){
// 更新当前能达到的最远位置
maxPos = Math.max(maxPos, i + nums[i]);
// 如果当前位置是当前能达到的最远位置的最后一个元素，则更新下一次跳跃的起始位置和跳跃次数
if(i == end){
end = maxPos;
step++;
}
}
return step;
}
}
1 |
|
public int jump(int[] nums) {
int position = nums.length - 1; //要找的位置
int steps = 0;
while (position != 0) { //是否到了第 0 个位置
for (int i = 0; i < position; i++) {
if (nums[i] >= position - i) {
position = i; //更新要找的位置
steps++;
break;
}
}
}
return steps;
}
1 |
|
class Solution {
/**
* 在未排序的数组中找到第 k 个最大的元素。
*
* @param nums 待查找的整数数组
* @param k 要查找的第 k 个最大元素的索引（索引从 1 开始）
* @return 第 k 个最大的元素
*/
public int findKthLargest(int[] nums, int k) {
int n = nums.length;
//为什么target = n-k
// 例如：数组长度为 n，第 k 大元素即为排序后位于下标 n-k 的位置
int target = n - k; // 第 k 大 = 第 n-k 小（0-based）
int left = 0, right = n - 1;
// 快速选择算法，每次分区后判断 pivot 的位置
while (true) {
int p = partition(nums, left, right);
// 判断 pivot 是否为第 k 大元素的位置 如果是返回p的下标
if (p == target) return nums[p];
// 否则根据 pivot 的位置调整查找范围
// 例如：pivot 在左侧，则在右侧查找，pivot在右侧，则在左侧查找
else if (p < target) left = p + 1;
else right = p - 1;
}
}
/**
* 对数组进行分区操作。
*
* @param a 待分区的数组
* @param l 分区起始位置（包含）
* @param r 分区结束位置（不包含）
* @return 基准元素的最终位置
*/
private int partition(int[] a, int l, int r) {
// 随机选基准，避免退化
//为什么用ThreadLocalRandom而不是Random？
//随机 pivot 用 ThreadLocalRandom.current().nextInt(l, r+1)，参数永远是“左闭右开”，且保证 l <= r 时范围合法。
int pivotIdx = ThreadLocalRandom.current().nextInt(l, r + 1);
// 随机交换到数组末尾，避免最坏情况
swap(a, pivotIdx, r);
// 升序排列，小于 pivot 的元素放到左侧
int pivot = a[r];
int i = l; // a[l..i-1] < pivot
for (int j = l; j < r; j++) { // a[i..j-1] >= pivot（未分类）
if (a[j] < pivot) { // 升序位置
swap(a, i, j);
i++;
}
}
swap(a, i, r); // pivot 放到最终位置 i
return i;
}
/**
* 交换数组中的两个元素。
*
* @param a 要操作的数组
* @param i 第一个元素的索引
* @param j 第二个元素的索引
*/
private void swap(int[] a, int i, int j) {
int t = a[i]; a[i] = a[j]; a[j] = t;
}
}
1 |
|
nums = [3,2,3,1,2,4,5,5,6]
k = 4
1 |
|
left = 0, right = 8, target = 5
1 |
|
a[l…i-1] < pivot
1 |
|
p = 1, target = 5
p < target → left = p + 1 = 2
现在区间缩小为 [2, 8]
1 |
|
p = 6, target = 5
p > target → right = p - 1 = 5
现在区间缩小为 [2, 5]
1 |
|
p = 3, target = 5
p < target → left = p + 1 = 4
现在区间缩小为 [4, 5]
1 |
|
swap(5, 5) → 不变
pivot = 4, i=4, j=4…4
j=4: a[4]=3 < 4 ? 是 → swap(4,4) 不变，i=5
swap(i=5, r=5) 不变
返回 p = 5
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
这时 `p == target(5)`，返回 `nums[5]`。
最终答案：`nums[5] = 4`，与题意示例一致（第 4 大是 4）。
------
代码里两处关键点再解释一下
- **为什么 `target = n - k`？**
按升序排序后，第 k 大的元素位于 0-based 下标 `n-k`（例如 n=9、k=4 ⇒ 第 5 个（下标 5））。
- **为什么用 `ThreadLocalRandom`？**
它是更轻量的每线程单例随机数生成器，避免了 `new Random()` 的共享竞争与额外开销，并且有方便的 `nextInt(l, r+1)`（左闭右开区间）形式，写起来也不容易越界。
------
方法2：
好问题 👍，我来详细讲讲这段 `Solution1` 代码是如何实现「数组中第 k 个最大元素」的。
class Solution{
private int quickSelect(List
//随机选择基准数
Random random = new Random();
int pivot = nums.get(random.nextInt(nums.size()));
//分区，将大于，小于，等于pivot的元素划分到big，small，equal中
List
List
List
for (int num : nums) {
//num > pivot, num < pivot, num == pivot分别划分到对应的分区
if (num > pivot) {
big.add(num);
} else if (num < pivot) {
small.add(num);
} else {
equal.add(num);
}
}
//将第k大的元素在big中递归划分
if (k <= big.size()) {
return quickSelect(big, k);
}
//如果k在small中，则在small中进行递归划分
if (big.size() + equal.size() < k) {
return quickSelect(small, k - (big.size() + equal.size()));
}
//如果k在equal中，则直接返回pivot
return pivot;
}
//查找数组中的第k大元素
public int findKthLargest(int[] nums, int k) {
List<Integer> numsList = new ArrayList<>();
for (int num : nums) {
numsList.add(num);
}
return quickSelect(numsList, k);
}
}
1 |
|
private int quickSelect(List
//随机选择基准数
Random random = new Random();
int pivot = nums.get(random.nextInt(nums.size()));
1 |
|
//分区
List<Integer> big = new ArrayList<>();
List<Integer> small = new ArrayList<>();
List<Integer> equal = new ArrayList<>();
for (int num : nums) {
if (num > pivot) {
big.add(num);
} else if (num < pivot) {
small.add(num);
} else {
equal.add(num);
}
}
1 |
|
// 如果第k大在big中
if (k <= big.size()) {
return quickSelect(big, k);
}
1 |
|
// 如果第k大在small中
if (big.size()+equal.size()<k) {
return quickSelect(small, k - (big.size()+equal.size()));
}
1 |
|
// 如果第k大在equal中，直接返回pivot
return pivot;
}
1 |
|
public int findKthLargest(int[] nums, int k) {
List
for (int num : nums) {
numsList.add(num);
}
return quickSelect(numsList, k);
}
1 |
|
nums = [3,2,1,5,6,4], k = 2
1 |
|
5
1 |
|
class Solution {
public int[] topKFrequent(int[] nums, int k) {
//统计每一个数字出现的次数
Map<Integer, Integer> map = new HashMap<>();
//遍历数组，统计每个数字出现的次数
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
//根据数字出现的次数进行排序,取出前k个高频元素并获取key最后收集到数组中
int[] array = map.entrySet().stream()
.sorted((e1, e2) -> e2.getValue() - e1.getValue())
.limit(k)
.mapToInt(Map.Entry::getKey)
.toArray();
return array;
}
}
1 |
|
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer,Integer>map = new HashMap<>();//统计每个元素出现的次数
//遍历数组，统计每个元素出现的次数,默认值为0
for(int num:nums){
map.put(num,map.getOrDefault(num,0)+1);
}
//构建一个小顶堆，按照频次升序排列
PriorityQueue<int[]>head = new PriorityQueue<>((a,b)->a[1]-b[1]);//小顶堆：按频次升序
//将元素加入到小顶堆中，如果堆的大小超过k，则移除堆顶的元素
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
head.offer(new int[]{entry.getKey(), entry.getValue()});
if(head.size()>k){
head.poll();
}
}
//将堆中的元素放入结果数组中
int[]res = new int[k];
//堆顶元素即为频次最高的元素，依次取出放入结果数组中
for(int i=k-1;i>=0;i–){
res[i] = head.poll()[0];
}
return res;
}
}
1 |
|
class Solution {
public boolean wordBreak(String s, List
//放到HashSet中，便于快速查找
Set
int n = s.length();//字符串长度
boolean[] dp = new boolean[n + 1];//dp[i]表示s的前i个字符是否可以拆分
dp[0] = true;//初始化，空字符串可以拆分
//遍历字符串s，枚举分割点j
for (int i = 1; i <= n; i++) {
//如果前j个字符可以拆分，并且s[j,i)在字典中存在
for (int j = 0; j < i; j++) {
if (dp[j] && set.contains(s.substring(j, i))) {
//那么s的前i个字符也可以拆分，更新dp[i]为true
dp[i] = true;
break;//跳出内层循环，因为我们已经找到了一个可行的拆分方式
}
}
}
return dp[n];
}
}
1 |
|
s = “leetcode”, wordDict = [“leet”,“code”]
1 |
|
Set
n = 8;
boolean[] dp = new boolean[9]; // 长度 = n+1
dp[0] = true;
1 |
|
dp = [true, false, false, false, false, false, false, false, false]
1 |
|
dp = [true, false, false, false, false, false, false, false, false]
1 |
|
dp = [true, false, false, false, false, false, false, false, false]
1 |
|
dp = [true, false, false, false, false, false, false, false, false]
1 |
|
dp = [true, false, false, false, true, false, false, false, false]
1 |
|
dp = [true, false, false, false, true, false, false, false, false]
1 |
|
dp = [true, false, false, false, true, false, false, false, true]
1 |
|
dp[8] = true→ 返回true
1 |
|
class Solution {
public int lengthOfLIS(int[] nums) {
//边界条件判断
if(nums==null||nums.length==0) return 0;
int n=nums.length;
int[]dp = new int[n];//dp[i]表示以nums[i]结尾的最长递增子序列的长度
//初始化dp数组
for(int i=0;i<n;i++){
dp[i]=1;
//遍历dp数组，更新dp[i]的值
for(int j=0;j<i;j++){
if(nums[i]>nums[j]){
dp[i]=Math.max(dp[i],dp[j]+1);
}
}
}
//找到dp数组中的最大值
int max=0;
for(int i=0;i<n;i++){
max=Math.max(max,dp[i]);
}
return max;
}
}
1 |
|
class Solution {
public int maxProduct(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int n = nums.length;//数组长度
int maxProduct = nums[0];//最大乘积
int minProduct = nums[0];//最小乘积
int result = nums[0];
//i！=0，因为第一个元素已经被初始化了
for (int i = 1; i < n; i++) {
if (nums[i] < 0) {//如果当前元素为负数，则交换最大最小乘积
int temp = maxProduct;
maxProduct = minProduct;
minProduct = temp;
}
//更新最大最小乘积
maxProduct = Math.max(nums[i], maxProduct * nums[i]);
minProduct = Math.min(nums[i], minProduct * nums[i]);
result = Math.max(result, maxProduct);
}
return result;
}
}
1 |
|
nums = [2, 3, -2, 4]
1 |
|
class Solution {
public boolean canPartition(int[] nums) {
int sum =0;
for (int num : nums) {
sum += num;
}
if (sum % 2 != 0) {
return false;
}
int target = sum / 2;
//dp[j] 表示背包容量为j时，能否凑出总和为j的组合
boolean[] dp = new boolean[target + 1];
dp[0] = true;//初始化
for (int num : nums) {
//从target倒序遍历，保证每个物品只用一次
for (int j = target; j >= num; j--) {
dp[j] = dp[j] || dp[j - num];//要么不装，要么装上
}
//剪枝，如果找到了就直接返回
if(dp[target]) return true;
//如果背包容量为0，但是没有找到总和为target的组合，则返回false(背包容量为0，但是总和不为0，说明总和不可能凑出)
}
return dp[target];
}
}
1 |
|
class Solution {
public int uniquePaths(int m, int n) {
if(m == 0 || n == 0) return 0;
int[][] dp = new int[m][n];//初始化dp数组
//初始化第一列
for(int i = 0;i < m;i++){
dp[i][0] = 1;
}
//初始化第一行
for(int j = 0;j < n;j++){
dp[0][j] = 1;
}
//填充dp数组
for(int i = 1;i < m;i++){
for(int j = 1;j < n;j++){
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
}
1 |
|
class Solution {
public int minPathSum(int[][] grid) {
if(grid == null || grid.length == 0) {
return 0;
}
int m = grid.length; //行数
int n = grid[0].length;//列数
//初始化第一列
for(int i = 1; i < m; i++) {
grid[i][0] += grid[i-1][0];
}
//初始化第一行
for (int j = 1; j < n; j++) {
grid[0][j] += grid[0][j-1];
}
//动态规划
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
//当前位置的最小路径和等于左边或者上边的最小路径和加上当前位置的数
grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
}
}
return grid[m-1][n-1];
}
}
class Solution {
public int minPathSum(int[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int m = grid.length; //行数
int n = grid[0].length;//列数
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) continue; //左上角，不用处理
else if (i == 0) grid[i][j] += grid[i][j - 1];//第一行，只能从左边来
else if (j == 0) grid[i][j] += grid[i - 1][j];//第一列，只能从上边来
else {
grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
}
}
}
return grid[m - 1][n - 1];
}
}
1 |
|
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
if (n < 2) {
return s;
}
int bestL = 0, bestR = 0;// 最长回文子串的左右边界
// 枚举中心点，枚举回文串的长度
for (int i = 0; i < n; i++) {
//以s[i]为中心（奇数长度）
int[] p1 = expand(s, i, i);
//以s[i]和s[i+1]为中心（偶数长度）
int[] p2 = expand(s, i, i + 1);
// 取最长的回文子串
if (p1[1] - p1[0] > bestR - bestL) {
bestL = p1[0];
bestR = p1[1];
}
// 取最长的回文子串
if (p2[1] - p2[0] > bestR - bestL) {
bestL = p2[0];
bestR = p2[1];
}
}
// 返回最长回文子串
return s.substring(bestL, bestR + 1);
}
private int[] expand (String s,int L, int R){
//当L和R指向同一个字符时，L向左移动到边界，R向右移动到边界
while(L>=0 && R<s.length() && s.charAt(L)==s.charAt(R)){
--L;
++R;
}
//返回回文子串的左右边界
return new int[]{L+1,R-1};
}
}
1 |
|
class Solution {
public String longestPalindrome(String s) {
if(s.length() < 2) return s;
int maxLen = 1; // 初始化最长回文子串的长度，至少为 1
int begin = 0; // 记录最长回文子串的起始下标
char[] chars = s.toCharArray();
// 遍历所有可能的回文中心
for(int i = 0; i < chars.length - 1; i++){
// 情况1：以 i 作为中心（奇数回文）
int len1 = expandAroundCenter(chars,i,i);
// 情况2：以 i 和 i+1 作为中心（偶数回文）
int len2 = expandAroundCenter(chars,i,i+1);
// 取两者中的最大长度
int len = Math.max(len1,len2);
// 如果发现更长的回文，更新起始位置和最大长度
if(len > maxLen){
begin = i - (len-1)/2;
maxLen = len;
}
}
// substring 的右边界是开区间，所以要写 begin + maxLen
return s.substring(begin, begin + maxLen);
}
// 中心扩展函数：返回以 left 和 right 为中心的最长回文子串长度
private int expandAroundCenter(char[] chars,int left,int right){
while (left >= 0 && right < chars.length && chars[left] == chars[right]){
--left;
++right;
}
// 跳出循环时，left 和 right 分别越界或不相等
// 有效回文串的长度 = (right-1) - (left+1) + 1 = right-left-1
return right - left - 1;
}
}
1 |
|
s = “babad”
1 |
|
(
1 | b |
)
-
len1 = 1 (
"b") -
len2 = 0 (
"") -
最大 = 1，不更新
-
i = 1a1
2
3
((1
2
3
4
5
6
7
8
9
10
11
)
- len1 = 3 (`"bab"`)
- len2 = 0
- 最大 = 3 > 1，更新：
- `begin = 1 - (3-1)/2 = 0`
- `maxLen = 3`
- ```
i = 2) - len1 = 3 (`"aba"`) - len2 = 0 - 最大 = 3，等于 maxLen，不更新1
b
-
继续扫描… 最长子串始终
"bab"或"aba"
第三步：结果
substring(0, 0+3) = "bab"
✅ 总结
- 这段代码用 中心扩展法，复杂度是 O(n²)，空间是 O(1)。
- 思路很直观：从每个位置开始，往两边扩展，找到所有可能的回文串，再记录最长的。
要不要我帮你画一个 二维表格（索引 × 回文中心扩展结果），一步步展示 "babad" 的中心扩展过程？这样你能更清楚看到每一步最长回文是怎么更新的。
78.最长公共子序列（中等 多维动态规划）
1 | class Solution { |
这段代码是在用滚动数组的一维 DP来求两个字符串的最长公共子序列（LCS）。先给出标准二维写法，再解释它是如何被压缩到一维的，以及代码里 leftup、nextLeftup 的作用。
1）标准二维 DP（便于理解）
设
dp[i+1][j+1] = text1[0..i] 与 text2[0..j] 的 LCS 长度。
状态转移：
- 若
text1[i] == text2[j]，这个字符可以作为公共子序列的一部分：
dp[i+1][j+1] = dp[i][j] + 1 - 否则只能继承较长的那个：
dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
边界：dp[0][*] = 0, dp[*][0] = 0。
2）滚动数组（一维 DP）如何实现
我们只保留上一行的信息，将二维压缩成长度为 n+1 的一维数组 dp（n = text2.length()）：
- 在外层遍历
i（text1 的下标），每一轮都会把dp更新为“第i+1行”的值； - 在内层遍历
j，从左到右更新dp[j+1]。
关键是：在更新 dp[j+1] 时，我们需要用到左上角 dp[i][j]（二维定义里的）。
此时：
dp[j+1]（更新前）其实是上一行的dp[i][j+1]dp[j]（已经被本行更新）是当前行的dp[i+1][j]leftup用来保存“上一行的 dp[i][j]”（也就是二维里的左上角）nextLeftup = dp[j+1]在覆盖dp[j+1]之前，先把它（上一行的dp[i][j+1]）存起来，给下一个j当作左上角使用
于是转移式在一维里变成：
1 | if (text1[i] == text2[j]) |
3）逐步模拟（text1=“abcde”, text2=“ace”）
初始化：dp = [0, 0, 0, 0]，对应 j=-1,0,1,2（方便处理空前缀）
- i=0（‘a’）
- j=0（‘a’）：相等 →
dp[1]=leftup+1=1；更新leftup=旧dp[1]=0 - j=1（‘c’）：不等 →
dp[2]=max(旧dp[2]=0, dp[1]=1)=1；leftup=旧dp[2]=0 - j=2（‘e’）：不等 →
dp[3]=max(0, dp[2]=1)=1；leftup=旧dp[3]=0
dp = [0,1,1,1]
- j=0（‘a’）：相等 →
- i=1（‘b’）：
- j=0：不等 →
dp[1]=max(1,0)=1；leftup=旧dp[1]=1 - j=1：不等 →
dp[2]=max(1, dp[1]=1)=1；leftup=旧dp[2]=1 - j=2：不等 →
dp[3]=max(1, dp[2]=1)=1；leftup=旧dp[3]=1
dp = [0,1,1,1]
- j=0：不等 →
- i=2（‘c’）：
- j=0：不等 →
dp[1]=max(1,0)=1；leftup=旧dp[1]=1 - j=1：相等 →
dp[2]=leftup+1=2；leftup=旧dp[2]=1 - j=2：不等 →
dp[3]=max(1, dp[2]=2)=2；leftup=旧dp[3]=1
dp = [0,1,2,2]
- j=0：不等 →
- i=3（‘d’）：
- 更新后仍为
dp = [0,1,2,2]
- 更新后仍为
- i=4（‘e’）：
- j=0：不等 →
dp[1]=1 - j=1：不等 →
dp[2]=2 - j=2：相等 →
dp[3]=leftup+1=3（此时leftup是上一行的dp[2]=2）
dp = [0,1,2,3]
- j=0：不等 →
最终返回 dp[n] = dp[3] = 3。
4）复杂度
- 时间：
O(m * n) - 空间：
O(n)（滚动数组）
5）把代码和上面的解释对上
1 | int[] dp = new int[n+1]; // 一维滚动：dp[j+1] 表示“当前行”的值，初始化为 0 |
只要把“二维版的三种位置关系”在脑子里对应好（上、左、左上），你就能看懂这段一维 DP：
dp[j+1]更新前 = 上dp[j]（本行已更新）= 左leftup= 左上（上一轮保存的）
这样就完全等价于二维 DP 的写法了。
79.编辑距离（中等 多维动态规划）
1 | class Solution { |
你这份代码实现的是 编辑距离（Levenshtein Distance） 的经典动态规划解法，我给你分两步讲清楚：
🔹代码逻辑解析
-
特殊情况处理
- 如果
word1 == word2，返回0（不需要操作）。 - 如果
word1为空，结果就是word2.length()（全靠插入）。 - 如果
word2为空，结果就是word1.length()（全靠删除）。
- 如果
-
DP 数组定义
dp[i][j]表示 word1 的前 i 个字符 和 word2 的前 j 个字符 的最小编辑距离。- 数组大小
(len1+1) * (len2+1)，因为我们要考虑空串情况。
-
初始化
dp[i][0] = i：word1 转换成空串，需删除 i 个字符。dp[0][j] = j：空串转换成 word2，需要插入 j 个字符。
-
状态转移方程
-
如果
word1[i-1] == word2[j-1]→ 不需要操作dp[i][j] = dp[i-1][j-1]; -
否则 → 取三种操作的最小值：
- 插入：
dp[i][j-1] + 1 - 删除：
dp[i-1][j] + 1 - 替换：
dp[i-1][j-1] + 1
1
dp[i][j] = Math.min(Math.min(dp[i-1][j]+1, dp[i][j-1]+1), dp[i-1][j-1]+1);
- 插入：
-
🔹示例 1
输入：
1 | word1 = "horse", word2 = "ros" |
我们画出 DP 表格（行：word1，列：word2）：
| dp[i][j] | “” | r | ro | ros |
|---|---|---|---|---|
| “” | 0 | 1 | 2 | 3 |
| h | 1 | 1 | 2 | 3 |
| ho | 2 | 2 | 1 | 2 |
| hor | 3 | 2 | 2 | 2 |
| hors | 4 | 3 | 3 | 2 |
| horse | 5 | 4 | 4 | 3 |
最终答案：dp[5][3] = 3
对应操作路径：
- horse → rorse （替换 h → r）
- rorse → rose （删除 r）
- rose → ros （删除 e）
🔹示例 2
输入：
1 | word1 = "intention", word2 = "execution" |
DP 表太大我就不完全画了，但结果是 dp[9][9] = 5，操作过程：
- intention → inention （删 t）
- inention → enention （i → e）
- enention → exention （n → x）
- exention → exection （n → c）
- exection → execution （插入 u）
✅ 总结：
- DP 表的本质就是 逐步缩小问题规模，把大问题拆成小问题。
- 表格里每一格
dp[i][j]记录的是“前 i 个字符”和“前 j 个字符”变成一样所需的最小操作数。
思路2：
1 | class Solution { |
你这份代码用的是 递归 + 记忆化搜索（Top-down DP） 的写法，和之前二维 DP 表的思路是一致的，只是换了一种实现方式。
我帮你拆解一下：
🔹思路核心
-
递归定义
1
dfs(i, j)
表示
word1[0…i] 转换为 word2[0…j] 的最小编辑距离
。
- 如果
i < 0，说明 word1 已经用完，只能插入剩下的j+1个字符。 - 如果
j < 0，说明 word2 已经用完，只能删除剩下的i+1个字符。
- 如果
-
状态转移
- 如果
w1[i] == w2[j]→ 不需要操作，递归到dfs(i-1, j-1)。 - 否则 → 三种操作取最小值 + 1：
- 替换：
dfs(i-1, j-1) - 删除：
dfs(i-1, j) - 插入：
dfs(i, j-1)
- 替换：
1
memo[i][j] = w1[i] == w2[j] ? dfs(i-1, j-1) : Math.min(dfs(i-1, j-1), Math.min(dfs(i-1, j), dfs(i, j-1))) + 1;
- 如果
-
记忆化缓存
- 用
memo[i][j]缓存子问题结果，避免重复计算。 - 如果已经算过，就直接返回。
- 用
🔹代码运行过程举例
以 word1 = "horse"，word2 = "ros" 为例：
-
递归树最顶层是
dfs(4, 2)→ 对应word1="horse", word2="ros" -
因为
1
e != s
，所以需要考虑三种操作：
- 替换
dfs(3,1) - 删除
dfs(3,2) - 插入
dfs(4,1)
- 替换
逐层递归下去，最终会走到边界情况（i < 0 或 j < 0），然后逐步返回。
同时，由于 memo 缓存，重复子问题只会计算一次。
最后返回结果：3。
🔹与二维 DP 的区别
- 二维 DP（Bottom-up）
- 从小问题开始，逐步填表，直到最终答案。
- 优点：迭代更直观，容易画表格。
- 缺点：必须额外开一个二维数组。
- 递归 + 记忆化（Top-down）
- 从大问题出发，递归拆分为子问题。
- 优点：写法简洁，符合思维逻辑。
- 缺点：递归开销大，如果没有
memo会超时。
✅ 总结：
这份代码就是用 dfs(i, j) 表示前缀的最小编辑距离，
通过递归去解决问题，并用 memo 避免重复计算，
实质上和二维 DP 是完全等价的。
要不要我帮你把这个 递归搜索过程（以 horse → ros 为例）画成一棵递归调用树？这样你能直观看到每一步怎么拆分。
80.颜色分类（中等 技巧）
你这段就是著名的「荷兰国旗问题」解法（Dutch National Flag），用三指针一次扫描把 0/1/2 原地排成 0、1、2 的顺序。思路既直观又高效：O(n) 时间、O(1) 额外空间，不调用 sort。
核心指针与不变量
s（start）：左边界，维护区间[0 .. s-1]都是 0i（index）：当前扫描位置n（end）：右边界，维护区间[n+1 .. 末尾]都是 2
因此任意时刻数组被分成 4 段：
1 | [ 0区 | 未处理 | 2区 ] |
初始化：s = 0, i = 0, n = nums.length - 1
扫描规则（while/for 都可，本质一样）
对 i 从左向右处理，直到 i > n：
-
nums[i] == 0：把它丢到最右边 - `swap(nums, n, i)`，然后 `n--`，**但 `i` 不动** - 理由：右端 `n` 位置换过来的数**还没检查**（可能是 0/1/2），所以要继续用同一个 `i` 重新判断一次1
2
3
4
5
6
7
8
：把它丢到最左边
- `swap(nums, s, i)`，然后 `s++，i++`
- 理由：交换后 `i` 位置是旧的 `nums[s]`，但 `s` 左侧保证全 0，且被换来的元素至多是 1（因为 2 会被放在右端），而 `i` 右移继续安全
2. ```
nums[i] == 2 -
nums[i] == 11
2
3
4
5
6
7
8
9
10
11
12
13
：本来就应该在中间
- `i++` 即可
这三条保证每一步都在扩大“已归位”的 0 区/2 区，缩小“未处理区”。
------
举例走一遍：`[2,0,2,1,1,0]`
初始：`s=0, i=0, n=5`
i=0: nums[i]=2 → 与 n 交换 → [0,0,2,1,1,2], n=4, i=0（不动）
i=0: nums[i]=0 → 与 s 交换(同位置) → [0,0,2,1,1,2], s=1, i=1
i=1: nums[i]=0 → 与 s 交换(同位置) → [0,0,2,1,1,2], s=2, i=2
i=2: nums[i]=2 → 与 n 交换 → [0,0,1,1,2,2], n=3, i=2（不动）
i=2: nums[i]=1 → i=3
i=3: nums[i]=1 → i=4
结束条件：i(4) > n(3) ⇒ done
结果：[0,0,1,1,2,2]
1 |
|
public void sortColors(int[] nums) {
if (nums.length == 0) return;
int s = 0, n = nums.length - 1;
for (int i = 0; i <= n; ) {
if (nums[i] == 0) {
swap(nums, s++, i++);
} else if (nums[i] == 2) {
swap(nums, n–, i); // i 不变
} else {
i++;
}
}
}
1 |
|
class Solution {
public void nextPermutation(int[] nums) {
int n = nums.length;
//第一步，从右往左找到第一个小于右侧相邻数字的数nums[i]
int i = n - 2;//从倒数第二个数开始，因为倒数第一个数要作为比较对象
//从右往左找到第一个小于右侧相邻数字的数nums[i]
// 只有符合nums[i]<nums[i+1]的数才是我们要找的就会跳出循环，否则i–继续找
while (i >= 0 && nums[i] >= nums[i + 1]) {
i–;
}
//如果找到了就进入第二步，否则跳过第二步，翻转整个数组
if (i >= 0) {
//第二步，在nums[i]的右侧找到第一个大于nums[i]的数nums[j]，交换这两个数字
int j = n - 1;
//只有符合nums[j]>nums[i]的数才是我们要找的就会跳出循环，否则j--继续找
while (nums[j] <= nums[i]) {
j--;
}
//找到了交换nums[i]与nums[j]的位置
swap(nums, i, j);
}
//第三步，翻转n[i+1,n-1]范围的数组顺序（如果上面跳过了第二步，此时i=-1，也就是翻转整个数组）
reverse(nums, i + 1, n - 1);
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private void reverse(int[] nums, int i, int j) {
while (i < j) {
swap(nums, i, j);
i++;
j--;
}
}
}
1 |
|
class Solution {
public int findDuplicate(int[] nums) {
// 快慢指针法，快指针每次走两步，慢指针每次走一步，当它们相遇时，说明有环。
// 然后将其中一个指针重新指向数组的起始位置，然后两个指针每次都走一步，直到再次相遇，即为环的开始点，也就是重复的数。
int slow = nums[0];// 慢指针，走一步
int fast = nums[nums[0]];// 快指针，走两步
// 当它们未相遇时，继续循环
while (slow != fast) {
slow = nums[slow];// 慢指针继续走一步
fast = nums[nums[fast]];// 快指针继续走两步
}
//当它们相遇时，将其中一个指针重新指向数组的起始位置
fast = 0;
// 然后两个指针每次都走一步，直到再次相遇，即为环的开始点，也就是重复的数。
while (slow != fast) {
slow = nums[slow];// 慢指针继续走一步
fast = nums[fast];// 快指针继续走一步
}
// 当它们再次相遇时，即为环的开始点，也就是重复的数。
return slow;
}
}
1 |
|
public int lengthOfLongestSubstring(String s) {
int n = s.length();
int ans = 0; // 答案：最长子串长度
Map<Character, Integer> map = new HashMap<>(); // 记录字符最近一次出现的位置 + 1
// 双指针滑动窗口：start为左边界，end为右边界
for (int start = 0, end = 0; end < n; end++) {
char alpha = s.charAt(end); // 当前右指针字符
// 如果当前字符见过，且上次出现位置在当前窗口内，
// 就把左边界跳到“上次出现位置的下一位”
if (map.containsKey(alpha)) {
start = Math.max(map.get(alpha), start);
// 注意：map里存的是 index + 1，所以这里直接取值即可
}
// 记录当前字符的“下一位位置”（end + 1）
map.put(alpha, end + 1);
// 用当前窗口长度更新答案
ans = Math.max(ans, end - start + 1);
}
return ans;
}
1 |
|
m
1 |
|
[left, right]
1 |
|
s
1 |
|
class Solution {
public List
List
int n = s.length();
int m = p.length();
if (n < m) return res;// 如果s的长度小于p，直接返回空列表
int[] sCount = new int[26];// 用于统计s中每个字符的频次
for (int i = 0; i < m; i++) {
sCount[p.charAt(i) - 'a']++;// 初始化，统计p中每个字符的频次
}
int left = 0;
for (int right = 0; right < n; right++) {
sCount[s.charAt(right) - 'a']--;// 将当前字符的频次减1
if (right - left + 1 > m) {// 当窗口大小大于p的长度时，移动左指针
sCount[s.charAt(left) - 'a']++;// 将移出窗口的字符频次加1
left++;// 左指针右移
}
//长度等于m时检查是否全为0
if (right - left + 1 == m && checkZero(sCount)) {
res.add(left);
}
}
return res;
}
private boolean checkZero(int[] sCount) {
for (int i = 0; i < sCount.length; i++) {
if (sCount[i] != 0) {
return false;
}
}
return true;
}
}
1 |
|
s = “cbaebabacd”, p = “abc”, m = 3
1 |
|
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 1) 递归的终止条件（返回“我在这棵子树里看到了谁”）
if (root == null || root == p || root == q) return root;
// 2) 分别在左子树、右子树里找
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
// 3) 归并子结果
if (left != null && right != null) return root; // p、q 分别出现在左右子树 ⇒ 当前 root 就是最近公共祖先
else return (left != null ? left : right); // p、q 只在一边 ⇒ 把那一边向上传
}
1 |
|
left
1 |
|
right
1 |
|
root = 3, p = 5, q = 1
1 |
|
count > 0
1 |
|
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
个橘子逐个出队，检查其四个方向（上、下、左、右）：
- 邻格是新鲜橘子（值为 1）→ 立刻置为 2（表示被感染）；
- `count--`（新鲜数量减少）；
- 新感染的橘子加入队列（将在下一分钟继续传染）。
1. **结束判断**
- 循环结束后：
- 如果 `count > 0`，说明还有新鲜橘子没被感染（被 0 隔开等），返回 `-1`；
- 否则返回 `round`（用掉的分钟数）。
关键变量
- `queue`：当前“这一分钟内会传播的腐烂橘子”集合（坐标）。
- `count`：剩余的新鲜橘子数量；每感染一个就减 1。
- `round`：BFS 的层数，也就是分钟数。
复杂度
- 时间：`O(m*n)`，每个格子最多入队一次。
- 空间：`O(m*n)`，最坏队列装下大部分格子。
import java.util.LinkedList;
import java.util.Queue;
/**
-
- 腐烂的橘子
-
多源 BFS：把所有初始为 2 的格子作为源点同时入队，按层(分钟)向四周传播。
-
每完成一层传播，分钟数 +1；当所有 1 都被感染后返回累计分钟数；若仍有 1 无法被感染，返回 -1。
*/
public class Solution {
public int orangesRotting(int[][] grid) {
// 行数 M、列数 N
int M = grid.length;
int N = grid[0].length;// 队列存放将要“传播”的腐烂橘子坐标 (r, c) // 这里是“多源 BFS”，初始把所有 2 都入队 Queue<int[]> queue = new LinkedList<>(); // count 统计当前网格中“新鲜橘子”的数量 int count = 0; // 1) 预处理：统计新鲜橘子数量，并把所有初始腐烂橘子入队 for (int r = 0; r < M; r++) { for (int c = 0; c < N; c++) { if (grid[r][c] == 1) { // 新鲜橘子 count++; } else if (grid[r][c] == 2) { // 腐烂橘子：作为当前 BFS 的源点入队 queue.add(new int[]{r, c}); } // grid[r][c] == 0 为空气，忽略 } } // 如果一开始没有新鲜橘子，直接 0 分钟 // （如果题目一定要求走 BFS 也可以不加，但这个剪枝能快些） // if (count == 0) return 0; // round 表示已经经过的“分钟数”（BFS层数） int round = 0; // 2) BFS 层序遍历（每一层 = 一分钟） // 条件：还存在新鲜橘子(count>0) 并且 队列里还有能继续传播的腐烂橘子 while (count > 0 && !queue.isEmpty()) { // 进入下一分钟 round++; // 当前队列中的结点数，恰好是“本分钟内”会向外传播的腐烂橘子数量 int n = queue.size(); // 把这一层的所有腐烂橘子逐个出队，并尝试感染其四邻的新鲜橘子 for (int i = 0; i < n; i++) { int[] orange = queue.poll(); int r = orange[0]; int c = orange[1]; // 上：r-1, c if (r - 1 >= 0 && grid[r - 1][c] == 1) { grid[r - 1][c] = 2; // 感染为腐烂 count--; // 新鲜橘子总数减少 queue.add(new int[]{r - 1, c}); // 入队，下一分钟继续传播 } // 下：r+1, c if (r + 1 < M && grid[r + 1][c] == 1) { grid[r + 1][c] = 2; count--; queue.add(new int[]{r + 1, c}); } // 左：r, c-1 if (c - 1 >= 0 && grid[r][c - 1] == 1) { grid[r][c - 1] = 2; count--; queue.add(new int[]{r, c - 1}); } // 右：r, c+1 if (c + 1 < N && grid[r][c + 1] == 1) { grid[r][c + 1] = 2; count--; queue.add(new int[]{r, c + 1}); } } // 至此，完成了“本分钟”的所有传播；下一轮 while 即进入“下一分钟” } // 3) 结束判断 // 如果还有新鲜橘子残留（count>0），说明有些 1 被 0 隔断，无法被感染，返回 -1 if (count > 0) { return -1; } else { // 所有新鲜橘子都被感染，返回累计的“分钟数” return round; }}
}
1 |
|
grid =
2 1 1
1 1 0
0 1 1
初始：queue=[(0,0)], count=7
round=0
第1分钟：感染 (0,1),(1,0)
queue=[(0,1),(1,0)], count=5, round=1
第2分钟：由 (0,1),(1,0) 继续感染 (0,2),(1,1)
queue=[(0,2),(1,1)], count=3, round=2
第3分钟：由 (0,2),(1,1) 继续感染 (2,1)
queue=[(2,1)], count=2, round=3
第4分钟：由 (2,1) 感染 (2,2)
queue=[(2,2)], count=1, round=4
第5分钟：由 (2,2) 感染 (1,2)（如果存在且为1）
…
直到 count==0 返回 round；若中途 queue 空了但 count>0，则返回 -1
1 |
|
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 初始化入度数组
int[] indegrees = new int[numCourses];
// 初始化邻接表
List<List
// 初始化队列
Queue
// 初始化邻接表的大小为课程数量
for(int i = 0; i < numCourses; i++)
// 添加一个空的ArrayList到邻接表中
adjacency.add(new ArrayList<>());
// 遍历先决条件数组
for(int[] cp : prerequisites) {
// 增加课程cp[0]的入度
indegrees[cp[0]]++;
// 将课程cp[0]添加到课程cp[1]的邻接表中
adjacency.get(cp[1]).add(cp[0]);
}
// 遍历所有课程
for(int i = 0; i < numCourses; i++)
// 如果课程i的入度为0，将其加入队列
if(indegrees[i] == 0) queue.add(i);
// 当队列不为空时，循环处理
while(!queue.isEmpty()) {
int pre = queue.poll(); // 从队列中取出一个课程
numCourses--; // 已完成的课程数量减一
// 遍历当前课程的邻接课程
for(int cur : adjacency.get(pre))
// 如果邻接课程的入度减一后为0，将其加入队列
if(--indegrees[cur] == 0) queue.add(cur);
}
// 如果所有课程都已完成，返回true；否则返回false
return numCourses == 0;
}
}
1 |
|
int[] indegrees = new int[numCourses]; // 入度数组：每门课还需要完成的“前置”数量
List<List
for(int i = 0; i < numCourses; i++) adjacency.add(new ArrayList<>());
for (int[] cp : prerequisites) {
// cp = [a, b] 代表要学 a 必须先学 b，也就是边 b -> a
indegrees[cp[0]]++; // a 的入度 +1（多了一个前置 b）
adjacency.get(cp[1]).add(cp[0]); // 在 b 的出边链表里加入 a（b 学完后可以解锁 a）
}
1 |
|
Queue
for (int i = 0; i < numCourses; i++)
if (indegrees[i] == 0) queue.add(i);
1 |
|
while(!queue.isEmpty()) {
int pre = queue.poll(); // 取出一门当前可学的课
numCourses–; // 视为“完成”这门课（剩余待学课程数减一）
// 学完 pre 之后，它指向的后续课程的入度都要 -1
for (int cur : adjacency.get(pre)) {
if (--indegrees[cur] == 0) {
queue.add(cur); // 被完全解锁（入度为 0），可以入队等待学习
}
}
}
1 |
|
return numCourses == 0;
1 |
|
class Trie {
private final TrieNode root;
public Trie() {
// 初始化前缀树对象
root = new TrieNode();
}
public void insert(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (node.children[c - 'a'] == null) {
node.children[c - 'a'] = new TrieNode();
}
node = node.children[c - 'a'];
}
node.isEnd = true;
}
public boolean search(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (node.children[c - 'a'] == null) {
return false;
}
node = node.children[c - 'a'];
}
return node.isEnd;
}
public boolean startsWith(String prefix) {
TrieNode node = root;
for (int i = 0; i < prefix.length(); i++) {
char c = prefix.charAt(i);
if (node.children[c - 'a'] == null) {
return false;
}
node = node.children[c - 'a'];
}
return true;
}
// TrieNode内部类定义
private static class TrieNode {
TrieNode[] children;
boolean isEnd;
public TrieNode() {
children = new TrieNode[26];
isEnd = false;
}
}
}
1 |
|
class Solution {
public int trap(int[] height) {
int n = height.length;
if (n == 0) {
return 0;
}
// 计算每个位置左侧的最大值和右侧的最大值
int[] leftMax = new int[n];
leftMax[0] = height[0];//第一个位置左侧的最大值就是它本身
for (int i = 1; i < n; i++) {
leftMax[i] = Math.max(height[i], leftMax[i - 1]);//每个位置左侧的最大值是它本身和前一个位置的左侧最大值的较大者
}
//计算每个位置右侧的最大值
int[] rightMax = new int[n];
rightMax[n - 1] = height[n - 1];//最后一个位置右侧的最大值就是它本身
for (int i = n - 2; i >= 0; i–) {
rightMax[i] = Math.max(height[i], rightMax[i + 1]);//每个位置右侧的最大值是它本身和后一个位置的右侧最大值的较大者
}
//计算每个位置能接的雨水量
int ans = 0;
for (int i = 0; i < n; i++) {
ans += Math.min(leftMax[i], rightMax[i]) - height[i];//每个位置能接的雨水量是它左侧最大值和右侧最大值的较小者减去它本身的高度
}
return ans;
}
}
1 |
|
while (l < r)
1 |
|
height[l] < height[r]
1
2
3
4
5
6
7
8
9
：
- 若 `height[l] >= leftMax`，更新 `leftMax = height[l]`
- 否则此处可接水 `leftMax - height[l]`，累加到 `ans`
- `l++`
- 否则（
height[r] <= height[l]
1
2
3
4
5
6
7
8
9
10
）：
- 若 `height[r] >= rightMax`，更新 `rightMax = height[r]`
- 否则此处可接水 `rightMax - height[r]`，累加到 `ans`
- `r--`
为什么对较小侧结算？
因为此时两侧较小的那一边已经成为瓶颈，另一边再高也不会让“较小值”变大，当前侧的水量已经确定。
class Solution {
public int trap(int[] height) {
int n = height.length;
if (n <= 2) return 0;
int l = 0, r = n - 1;
int leftMax = 0, rightMax = 0;
int ans = 0;
while (l < r) {
if (height[l] < height[r]) {
// 左侧成为短板，能接的水由 leftMax 决定
if (height[l] >= leftMax) {
leftMax = height[l];
} else {
ans += leftMax - height[l];
}
l++;
} else {
// 右侧成为短板，能接的水由 rightMax 决定
if (height[r] >= rightMax) {
rightMax = height[r];
} else {
ans += rightMax - height[r];
}
r--;
}
}
return ans;
}
}
例子快速过一遍
以 `height = [4,2,0,3,2,5]`：
- 初始：`l=0,r=5,leftMax=0,rightMax=0,ans=0`
- 因为 `height[l]=4 < height[r]=5`，更新 `leftMax=4`，`l=1`
- `height[l]=2 < rightMax(=5)`，加 `leftMax(4)-2=2` → `ans=2`，`l=2`
- `height[l]=0 < rightMax(=5)`，加 `4-0=4` → `ans=6`，`l=3`
- `height[l]=3 < rightMax(=5)`，加 `4-3=1` → `ans=7`，`l=4`
- `height[l]=2 < rightMax(=5)`，加 `4-2=2` → `ans=9`，`l=5`
- 结束，答案 `9`
