LeetCode Hot 100 题目记录
哈希
- 1. 两数之和：使用字典保存出现过的数字及其坐标，判断 target - new_val 是否在集合里即可
- 49. 字母异位词分组：将字符串排序，作为 key，将相同 key 的字符串存储成列表（主要就是排序后的字符串 ss 作为 key）
- 128. 最长连续序列：将数组放到集合里，判别起始数字开始的最大长度（判断是否是起始数字可以看上一个数字在不在集合里）
双指针
- 283. 移动零：使用 gap 统计 0 的个数，也就是向前覆盖的差值，最后将末尾赋值成 0 就可以了
- 11. 盛最多水的容器：设置左右两个指针，向内收缩两边高度较小的一个，维护这个过程中的盛水容量最大值（原理：较小的指针不会再作为容器边界）
- 15. 三数之和：坐标 i 维护最左侧数字位置，l 和 r 在右侧区间找和为 target 的两个数字，并跳过相同的数字
- 42. 接雨水：维护单调减栈，如果出现单调增，计算形成的空区间（栈顶为底，弹出后的栈顶作为左位置，待 push 元素作为右位置）能够装的雨水量
滑动窗口
- 3. 无重复字符的最长子串：维护字母统计窗口，使用双指针维护滑动窗口内不会出现重复的字符，记录双指针之间的最大距离
- 438. 找到字符串中所有字母异位词：统计待匹配字符串的 p_counter，统计被匹配字符串 s 的 n 个值（滑动窗口初始化），依次移动 s 上的滑动窗口（维护滑动窗口），判断 s_counter 是否等于 p_counter 即可
字串
- 560. 和为 K 的子数组：记录前缀和，两个前缀和相减等于 target，将前缀和保存成字典即可（需要记录指定前缀和的数量）
- 239. 滑动窗口最大值：
- 76. 最小覆盖子串：对目标串建立字典，使用双指针，移动 r 的过程看是否满足字典匹配（check），如果匹配开始移动 l，记录 l 的最右位置，记录此时 l 与 r 之间的距离，并保存最小距离时的字串
普通数组
- 53. 最大子数组和：动态规划，dp[i] = max(nums[i], dp[i-1]+nums[i])，也就是前一个是负数就不加入到后续的最大和子数组了
- 56. 合并区间：逐个判断是否能与上一个 merged 区间合并，如果合并不了将上一个 merged 区间归档
- 189. 轮转数组：旋转三次，注意 k 对 n 取模即可
- 238. 除自身以外数组的乘积：从左向右递乘LR，从右向左递乘RL，然后记录 LR[i-1]* RL[i+1]（注意边界即可）
- 41. 缺失的第一个正数：
矩阵
- 73. 矩阵置零：统计横向为 0 的 set 和 纵向为 0 的 set，遍历两个 set 分别设置对应行或者列为 0
- 54. 螺旋矩阵：一共 n * n 个元素，设置四个轮转方向，遇到 flag 就转向（flag 可以设置为一个最小值 - 1）
- 48. 旋转图像：四个值轮转（找四个特殊点计算关系）
- 240. 搜索二维矩阵 II：类似于二分查找树，右上角作为根节点
链表
- 160. 相交链表：统计长度，让长的链表先移动，等长之后一起移动（移动前判别节点是否相等）
- 206. 反转链表：使用 pre 节点记录上一个，使用 p 记录本节点（初始化为 head ），逐个处理即可
- 234. 回文链表：链表计数，反转后半部分，使用快慢指针逐个判别
- 141. 环形链表：使用快慢指针判断（先转移指针，在判断是否是相同的指针）
- 142. 环形链表 II：使用快慢指针判别，重置 f 指针，一步一步移动直到相等（需要排除节点个数小于1且没有环的情况）
- 21. 合并两个有序链表：选择较小的逐个合并即可
- 2. 两数相加：reverse 两个数字，节点逐个相加（节点合并，短链表合到长链表上），然后再 reverse 回来
- 19. 删除链表的倒数第 N 个结点：统计链表长度 L，设置 p 移动 L - N - 1 长度，然后跳过下一个节点即可
- 24. 两两交换链表中的节点：
- 25. K 个一组翻转链表
- 138. 随机链表的复制：
- 148. 排序链表：归并排序思想（对子链表统计长度，分成两部分，分别排序）
- 23. 合并 K 个升序链表：ListNode.lt = lambda a, b : a.val < b.val，定义节点的比较函数，使用堆对链表头节点排序
- 146. LRU 缓存：
二叉树
- 94. 二叉树的中序遍历：递归进行中序遍历即可；非递归，使用栈保存节点（cur指针一直往左，否则弹出节点往右移动一个，记录弹出节点的值）
- 104. 二叉树的最大深度：层次遍历，记录最大层数；递归方法，向上返回左右节点深度
- 226. 翻转二叉树：空时返回，否则递归反转左右并赋给右左
- 101. 对称二叉树：当前节点值判别 + 四个节点两两对应的判别
- 543. 二叉树的直径：当左右节点都是 None 时，返回直径为 0，否则计算非空左右的直径，相加即为总直径（保存最大值），向上返回最大直径
- 102. 二叉树的层序遍历：使用队列逐层遍历即可
- 108. 将有序数组转换为二叉搜索树：构建build函数，传入中序左右位置，每次选中间节点作为根节点，逐级构建
- 98. 验证二叉搜索树：中序遍历，判断元素是否是严格递增的
- 230. 二叉搜索树中第 K 小的元素：中序遍历，取 k - 1
- 199. 二叉树的右视图：层序遍历，每次取最后一个
- 114. 二叉树展开为链表：
- 105. 从前序与中序遍历序列构造二叉树：前序第一个节点是中间节点，找到该节点在中序中的位置 & 计算左子树大小 & 前序遍历拆分 & 中序遍历拆分，分别构建左右子树即可
- 437. 路径总和 III：记录路径的前缀和字典（前缀和个数），判断target - 当前前缀是否在前缀和字典里，并统计数量即可（注意退出当前节点需要删除当前的前缀和）
- 236. 二叉树的最近公共祖先：自底向上收缩树，遇到 None 和 p q 向上收缩，判断当前节点的左右情况，如果一边为 None，祖先（或者p q）在另一边，如果两边都不是 None，说明当前节点就是祖先，向上返回即可
- 124. 二叉树中的最大路径和：返回左右路径与 0 相比的最大值，计算左右路径与根节点相加的路径和（记录这个过程中的最大值）
栈
- 84. 柱状图中最大的矩形：单调增栈，确定每一个元素的左右边界（遇到减的元素，当前元素就是栈顶的右边界；加入元素前，栈顶元素就是当前元素的左边界）
多维动态规划
- 139. 单词拆分：i 是字符串目标位置，j 是字符串切分起始位置，判断 j 处是否能切分，如果能切分，更新 i 位置能否切分
- 140. 单词拆分 II：i 是字符串目标位置，j 是字符串切分起始位置，判断 j 处是否能切分，如果能切分，更新 i 位置的切分字符串，并更新 i 位置是否能切分（带记录的动态规划）
原文链接: https://www.delta1037.cn/2025/Algorithm/面试-算法Hot100/
版权声明: 转载请注明出处.