LeetCode Hot100 刷题笔记：思路拆解与语法积累

第九题（438 找到字符串中所有字母异位词）

1. 题解是利用 i 的循环代替了显式的 l 或 r 指针
2. return new ArrayList();返回列表为空的情况，方便调用方再使用.size()、.add() 等函数
3. 第 0 遍循环也要记录 s 的字母数量：++sCount[s.charAt(i) - 'a'];

另外，List 是接口，ArrayList 是实现类，该接口被限制只暴露 add、get、size、remove，而不暴露内部实现或 ArrayList 的私有函数。

四、子串

第十题（560 和为 K 的子数组）

1. mp.getOrDefault(pre, 0) + 1：用这个函数的原因：如果 pre 没有出现果，mp.get(pre) 会返回 null，null+1 会崩溃

此题的关键思路是：

首先记录一下，这个题目看完思路以后自己手搓，除了定义 HashMap 和 containsKey 函数名写错了，其他全写对了。

第十一题（239 滑动窗口最大值）

1. 我学习的是单调队列的思路，相关函数有：① deque.isEmpty()；② deque.peekLast()；③ deque.pollLast()；④ deque.offerLast(i)；⑤ deque.peekFirst()；⑥ deque.pollFirst();
2. 注意：int[] ans = new int[n - k + 1];不要忘记 new

Java 是面向实现的编程：

第十二题（76 最小覆盖子串）

1. 首先需要注意，该题目包含大小写字母；其次，思路为：右指针不断右移先找到涵盖了 t 字符串的位置，然后左指针左移，缩小窗口范围找到最短字符串
2. s.substring(ansLeft, ansRight + 1)：加一的原因是，Java 的该函数为左闭右开区间

遍历一个 String 的各个字符串：

五、普通数组

第十三题（53 最大子数组和）

1. 动态规划法：pre = Math.max(pre + x, x);这样才能以 x 为新的字符串起点（而不是 pre = Math.max(pre + x, pre);）
2. Math.max() 函数的利用
3. 分治法？线段树的概念

第十四题（56 合并区间）

1. merged.add(new int[]{L, R});后面是数组的初始化列表
2. return merged.toArray(new int[merged.size()][]);最后的返回值应该转换成题目要求的数据类型

思路关键：排序（可行性由反证法证明），然后遍历区间，根据已有的最末端点与当前区间的起点比较，判断是否合并，积累 comparator 函数的写法（Comparator 函数是写在 Arrays.sort 的括号里的）。

第十五题（189 轮转数组）

1. 选择的是数组翻转的方法
2. nums 需要通过参数传给 reverse 函数，且在 Java 中传入后进行 reverse 是可以改变原数组的，传入的是引用

第十六题（238 除自身以外数组的乘积）

1. 思路：分别后向、前向计算得到前缀乘积和后缀乘积 L、R 数组，再分别相乘得 ans
2. 若想要空间复杂度为 O(1)，则用 answer 数组代替 L 数组，同时取消 R 数组，用 R 来记录即可

第十七题（41 缺失的第一个正数）

1. 注意这里的实现：我们给数组中的第 |x|−1 个位置的数添加一个负号，注意如果它已经有负号，不需要重复添加。nums[num - 1] = -Math.abs(nums[num - 1]);
2. 思路二置换法：将 nums[i] 换到下标为 nums[i]-1 的位置，最多替换 N 次；注意 nums[i] =x=nums[x−1] 的死循环

思路一直接上图：

六、矩阵

第十八题（73 矩阵置零）

1. 似懂非懂：为什么使用一个标记变量需要倒序，而使用两个标记变量的方法不用考虑这一点呢？

第十九题（54 螺旋矩阵）

按层模拟法：

这个方法注意：在每层向左和向上遍历时，要把 for 循环放入 if (left < right && top < bottom) 条件判断中，不是为了越界判断，而是为了防止重复输出。 另外，此题注意最初的矩阵判空。

模拟法可借鉴之处：int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; 以及对方向的判断。

第二十题（48 旋转图像）

法二：用翻转代替旋转 因为这样的操作可以得到关键等式

法一：原地旋转法 处于循环中的四项：

偶数时枚举 n2/4=(n/2)×(n/2) 个位置； 奇数时枚举 (n2−1)/4=((n−1)/2)×((n+1)/2) 个位置； 最后两种情况在代码中可以统一为：

第二十一题（240 搜索二维矩阵Ⅱ）

1. 法二：'Z'字形查找，从右上角为起点（此时它是这一行最大的，这一列最小的）

法一：逐行进行二分查找 这里积累向其他函数传递一行数据的简洁写法：

七、链表

第二十二题（160 相交链表）

1. 法一：将链表 A 存入名为 visited 的哈希表中，逐个判断链表 B 的各个节点是否在哈希表中：visited.contains(temp)；注意：temp 为 ListNode 类型，比较的是是否为同一个节点而不仅仅是 val 是否相同

法二：双指针的方法，过于巧妙：

第二十三题（206 反转链表）

1. 迭代法，注意：要用 next = cur.next 将下一个节点存储下来
2. 递归法，结束条件判断为 if (head == null || head.next == null) 递归找到新的头，然后 head.next.next = head;

第二十四题（234 回文链表）

1. 快慢指针，最后还原链表

第二十五题（141 环形链表）

1. 快慢指针，根据结果来看，把两个指针最初都放在 head 再移动和比较效率会更高

第二十六题（142 环形链表Ⅱ）

1. 快慢指针

关键公式：含义是从相遇点，再走几圈和 c 步，和从 head 出发的节点会在环的入口相遇

第二十七题（21 合并两个有序链表）

1. 递归法：关键语句：l1.next = mergeTwoLists(l1.next, l2);
2. 迭代法：使用一个 prev（初始化语句：ListNode prehead = new ListNode(-1);）来记录头节点，最终返回 return prehead.next; 合并后至多有一个不为空 prev.next = l1 == null ? l2 : l1;

第二十八题（2 两数相加）

1. 若一个数（链表）长度较短，则相当于后面有好多 0
2. 最后如果 carry>0，则需要多加一位
3. l1 进行.next 操作时需要判断是否为空，因为为空时也在循环里，当成 0 处理了

第二十九题（2 两数相加）

1. 栈的方法：加入 dummy（用的是哑节点的方法）的目的是统一删除头节点和后续节点的操作。定义额外的哑节点的方法（ListNode dummy = new ListNode(0, head);） 栈保存的是对节点的引用（其地址，相当于这个节点多了一条被指向的线）
2. 双指针的方法：加入哑节点后，先让 first 指针走 n 下，然后让 first 和 second 一起走，直到 second 走到要删除的前一个节点的位置

第三十题（24 两两交换链表中的节点）

1. 加入哑节点后，在 temp.next != null && temp.next.next != null 的条件下进行交换即可

第三十一题（25K 个一组翻转链表）

思路不难，就是代码复杂，这里的翻转链表和前面的思路一样吗？

第三十二题（138 随机链表的复制）

这里直接放了哈希表法的代码，因为对这个题的理解还不是很深

第三十三题（148 排序链表）

1. 快慢指针找中点
2. 左右子链表分别递归调用 sortList()
3. 最后记得加上剩余的长度 h.next = left == null ? right : left;

第三十四题（23 合并 K 个升序链表）

1. 顺序合并、分治合并
2. 使用优先队列合并：定义一个类来存储状态用以比较节点值的大小，使用接口 class Status implements Comparable，并在后面定义比较函数：public int compareTo(Status status2)； for (ListNode node: lists) 取出每个链表的第一个节点，然后从最小堆中取出堆顶 queue.poll()；然后放入最小值节点的下一个 queue.offer(new Status(f.ptr.next.val, f.ptr.next))
3. 复杂度的分析没明白……

第三十五题（146LRU 缓存）

1. 这道题目代码写起来不难，就是思路很新之前没有学过，然后会有很多小细节

唯一一个私有函数有返回值类型的，因为要将其用在删除 cache 对应的一对映射中

将新节点插入链表的同时要更新哈希表，删除同理（cache.remove()）

初始化头尾哑节点要记得把他们连起来（后两句）

无参构造函数和带参构造函数 （注意：构造函数无返回值类型）

八、二叉树

第三十六题（94 二叉树的中序遍历）

1. 递归代码很简单，这里用的是迭代的方法'颜色标记法'
2. 一些语法知识： ①Deque stack = new LinkedList<>();既可以当作栈（stack.push(x);stack.pop()）也可以当作队列（deque.offer(x);deque.poll()），关键是看使用了什么方法 ②构造函数前是否加 public 根据需求

关键代码：

第三十七题（104 二叉树的最大深度）

1. 深度优先遍历：利用递归
2. 广度优先遍历：利用队列，逐层加入所有节点，统一弹出上层所有节点
3. Queue 与 Deque 的区别： ①Queue 是单向队列，方法：offer(x); poll(); peek()。使用场景：二叉树层次遍历、拓扑遍历 ②Deque 是两头都能进出的双端队列，方法：addFirst(e) / addLast(e) / pollFirst() / pollLast()；以及栈语义：push(e) / pop()。使用场景：当栈用、双端操作（滑动窗口、单调队列）

第三十八题（226 翻转二叉树）

1. 深度和广度两种方法

第三十九题（101 对称二叉树）

迭代法：如果比较的两个位置都为空，应该 continue；而不是返回 true

关键语句：

递归法：关键语句

第四十题（543 二叉树的直径）

1. 递归计算每一个节点的 L+R

第四十一题（102 二叉树的层序遍历）

1. 广度优先遍历即可
2. List ans = new ArrayList();这种定义方式只关心<>中是'List< Integer >'，而不是实现类

第四十二题（108 将有序数组转换为二叉搜索树 BST）

1. 递归为 root 的 val、left、right 赋值

第四十三题（98 验证二叉搜索树）

1. Long.MIN_VALUE 与 Long.MAX_VALUE：定义为 long 类型的数
2. 递归法：为每一个 node 的验证限制范围：min 和 max，在递归调用中改变上下限
3. 中序遍历法，先访问到最左节点，再逐层向上向右访问

第四十四题（230 二叉搜索树中第 K 小的元素）

1. 思路同上中序遍历法，循环条件 while (root != null || !stack.isEmpty()) 表示此节点还没有遍历完（还在往下走）或栈内不为空（还有之前的祖先节点没处理）

第四十九题（236 二叉树的最近公共祖先）

1. 深度优先遍历：当左子树或右子树中有 p/q 或此时正在遍历的节点即为 p 或 q 时，dfs 函数可以返回 true；
2. 当满足 if (lson && rson || (root.val == p.val || root.val == q.val) && (lson || rson)) 条件时，即为找到了最近公共祖先

九、图论

第五十一题（200 岛屿数量）

1. 深度优先方法：依次遍历矩阵中的各个元素，并将与该元素能构成岛屿的节点的值设置为'0'（注意这里是字符），对于每个节点上下左右依次进行判断是否要进行深度遍历 时间复杂度：O(MN) 每个格子最多处理一次，邻居最多检查 4MN，≤5MN

第五十二题（994 腐烂的橘子）

1. 多源广度优先遍历：使用队列存储腐烂的橘子，然后从每一个节点向四个方向延申，同时更新腐烂时间记录数组的值，这些操作使得每个节点最多被遍历一次
2. 本题目使用 C++ 编程练习，注意的语句：memset(dis, -1,sizeof(dis)); Q.emplace(i, j); Q.empty(); ~dis[tx][ty] (只有 -1 按位取反后的值为 0)

第五十三题（207 课程表）

1. 思路转化：检查改题目的场景对应的图是否存在拓扑排序
2. BFS 方法：使用队列来保存入度初始为 0 或减至 0 的节点，每取出一个节点，就将以其为起点的边的另一头节点的入度减一，减至 0 时加入队列，每取出一个节点并访问其相邻节点时，将答案数量增加一
3. 本题目使用 Java 编程，注意的语句：queue.offer(i); queue.poll(); edges.add(new ArrayList());

第五十四题（208 实现 Trie (前缀树)）

十、回溯

第五十五题（46 全排列）

1. 设置 output 的目的是：亦可用标记数组来表示哪些数已经放入结果数组中，若不使用，那么可以通过划分左右两侧的数据来实现，左侧为已经放入结果数组的，右侧为还没有的
2. 如果 first 等于 n，也就是 n 及以后的数还没有放入结果数组，即等价于所有数字已经全部放入结果数组，那么将该排列加入结果数组中
3. 恢复现场的操作

第五十六题（78 子集）

1. 每个元素要么加入（1），要么不加入（0）集合，因此可以使用与其对应的（1 << n）个二进制数来表示集合中的存在情况
2. 关键判断语句：if ((mask & (1<<i)) != 0)：哪一位是 1，则将其加入集合
3. 最后一句为 ans.add(new ArrayList(t));，而不能是 ans.add(t);？否则 ans 所有值都指向同一块 t 的内存地址，会存储最后一个子集的内容，即各个相同

第五十七题（17 电话号码的字母组合）

1. 建立按键字母 Map 后，回溯，直至每种情况下达到字母的最大长度
2. 需要注意的语法：backtrack() 函数中的 new StringBuffer()：支持 append 和 delete，适合回溯，不同于 String（字符串不可变）；字符串取出某一个字母：digits.charAt(index)

第五十八题（39 组合总和）

1. 要想剪枝，需要排序：Arrays.sort(candidates);

第五十九题（22 括号生成）

1. 思路（合法的情况）：当 open 括号个数比 n 小时，仍然可以加入 open 括号（即前括号），当 close 括号个数比 open 括号个数小时，可以加入 close 括号（即后括号）
2. ans.add(cur.toString());（其中 cur 为 StringBuilder 类型），这里不需要在 add() 方法中 new，因为 toString() 方法就创建了一个新的 String 对象，不变地存储字符数组的内容

第六十题（79 单词搜索）

1. 各个数值作为第一个字符逐次遍历，而后对每一个的上下左右进行遍历，访问过的字符标记为'\0'，最后再赋值 words[k] 恢复现场（因为能执行到这里说明该元素值与 work[k] 是一致的）
2. 将 String 转换为字符数组：char[] words = word.toCharArray();

第六十一题（131 分割回文串）

第六十二题（51 N 皇后）

十一、二分查找

第六十三题（35 搜索插入位置）

1. 找到序列中第一个≥target 的值对应的位置

第六十四题（74 搜索二维矩阵）

1. 法一：两次二分查找；第一次首列上的二分查找，使用 while(left < right) 作为循环条件找到范围，第二次那一行上的二分查找，使用 while(left <= right) 作为循环条件找到是否有符合的值。
2. 法二：一次二分查找，假想把各个行拼成一个序列，使用 matrix[mid/n][mid%n] 定位元素数值

第六十五题（34 在排序数组中查找元素的第一个和最后一个位置）

1. 需要使用一个 lower 变量，选择在寻找不小于还是大于的元素位置：if (nums[mid] > target || (lower && nums[mid] >= target))
2. while (left <= right) 与 right = mid - 1、left = mid + 1 通常一起出现

判断条件的必要性：

第六十六题（33 搜索旋转排序数组）

1. if (nums[l] <= nums[mid]) 来判断左边的半个区间是否有序
2. if (nums[l] <= target && target < nums[mid]) 来判断 target 是否在有序的那一侧范围内，如果不在则考虑另一侧

第六十七题（153 寻找旋转排序数组中的最小值）

1. 判断条件 while (l < r) 与 r = mid; 和 l = mid +1; 配对出现

如图，以 high（最右侧的点的值）为基准，min 至 (high-1) 的值都小于 high 的值，0 至 (min-1) 的值都大于 high 的值

第六十八题（4 寻找两个正序数组的中位数）

十二、栈

第六十九题（20 有效的括号）

if (pairs.containsKey(chars[i])) 将括号映射为下面的哈希表，该语句用来判断目前是否正在处理后括号

第七十题（155 最小栈）

使用一个辅助栈，用来记录每一次压入一个数据时当前的最小值是多少（因为后面元素的进出栈不影响前面的最小值）

第七十一题（394 字符串解码）

1. 这个题目思路比较清晰，但是编写起来需要注意的细节非常多，涉及到的数据类型很多
2. 本题目中定义栈一定要使用 LinkedList sub = new LinkedList();因为 Collections.reverse 接收的是 List 类型的参数，不能声明为 Deque
3. 进而，这里要用 addLast、removeLast()、peekLast() 方法，
4. 如果我把代码中的 addLast()、removeLast()、peekLast() 都换成 push()、pop()、peek()，本应该输出 aaabcbc 的就会输出 cbcbaaa，为什么呢？

两种转型语法

第七十二题（739 每日温度）

1. 使用单调栈，依次存入当前温度最高的那一天的下标（因为要计算的是 i - prevIndex）；若新来的温度比栈顶下标对应的温度高，则弹出栈顶，因为距离它最近的比它温度高的那一天已经找到

第七十三题（84 柱状图中最大的矩形）

十三、堆

第七十四题（215 数组中的第 K 个最大元素）

1. 堆排序方法：在一次 heapify 调用中，一个节点最多下沉：树的高度 次，也就是 O(log n)
2. 快速排序方法：挖坑法，随机选取一个数字，让其左边都比他小，右边都比他大，这个题目只需要不断递归寻找 k 所在的那一侧

第七十五题（347 前 K 个高频元素）

1. 使用最小堆，维持个数为 k，利用记录的每个数字的频率，仅当遍历到的（数字，频率）对的频率大于堆顶时，弹出堆顶并压入；最终堆中保留的 k 个（数字，频率）对几位前 K 个高频元素
2. for (Map.Entry<Integer, Integer> entry : occs.entrySet())，这是 Java 的增强 for 循环（for-each），类似使用方法：for (int num: nums)；因此可以理解 Map.Entry<Integer, Integer>在这里表示一种数据类型
3. 语法积累：queue.offer(new int[]{num, count});

第七十六题（295 数据流的中位数）

十四、贪心算法

第七十七题（121 买卖股票的最佳时机）

使用一个变量记录最小值，遍历一遍即可得到答案

第七十八题（55 跳跃游戏）

1. 使用 rightmost 变量在遍历过程中保存可到达的最右端位置

第七十九题（45 跳跃游戏Ⅱ）

在每一个 [0……end] 范围中，遍历各个数字，得到下一步可到达的最远位置

第八十题（763 划分字母区间）

记录每个字母出现的最后位置，然后在遍历过程中不断更新这个范围的 end 值，直到遍历变量 i 走到 end 的位置（说明该字母区间无需再延长）