Hot 100 题解（三）
Hot 100 第三部分
Hot 100 指的是 LeetCode 上的一个题单
撰写第 68 ~ 100 题
15 三数之和
双指针枚举，需要尤其注意用排序去重
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
n = len(nums)
ret = []
for i in range(n - 2):
if nums[i] > 0:
continue
if i != 0 and nums[i - 1] == nums[i]: # 重复值去重
continue
target = -nums[i]
l = i + 1
r = n - 1
while l < r:
curr = nums[l] + nums[r]
if curr < target:
l += 1
elif curr > target:
r -= 1
else:
ret.append([nums[i], nums[l], nums[r]])
l += 1
r -= 1
while l < r and nums[l] == nums[l - 1]: # 重复值去重
l += 1
while l < r and nums[r] == nums[r + 1]: # 重复值去重
r -= 1
return ret11 盛最多水的容器
双指针算法，永远移动更短的那个，因为最大值永远受制于更短的那个值
class Solution:
def maxArea(self, height: List[int]) -> int:
n = len(height)
l, r = 0, n - 1
size = 0
while l < r:
if height[l] < height[r]:
size = max(size, (r - l) * height[l])
l += 1
else:
size = max(size, (r - l) * height[r])
r -= 1
return size10 正则表达式匹配
这是一个 dp 题目，初见难想到
dp[i][j] 表示s[:i]（前 i 个字符）是否能匹配 p[:j]（前 j 个字符）
这个 dp 的初始化也要注意，算是一个相对困难的题目了
class Solution:
def isMatch(self, s: str, p: str) -> bool:
m = len(s) + 1
n = len(p) + 1
dp = [[False] * n for _ in range(m)] # dp[i][j]表示 s[:i] 匹配 p[:j]
# 初始化
dp[0][0] = True
for j in range(2, n):
if p[j - 1] == '*':
dp[0][j] = dp[0][j - 2]
def _match(sc, pc):
return pc == '.' or sc == pc
for i in range(1, m):
for j in range(1, n):
sc = s[i - 1]
pc = p[j - 1]
if pc != "*":
dp[i][j] = dp[i - 1][j - 1] and _match(sc, pc)
else:
dp[i][j] = dp[i][j - 2] # 跳过不匹配
dp[i][j] |= _match(sc, p[j - 2]) and dp[i - 1][j] # 尝试匹配一次
return dp[m - 1][n - 1]5 最长回文子串
Manacher 算法，背诵一下，其他时候直接遍历中心扩展就行了
class Solution:
def longestPalindrome(self, s: str) -> str:
# 预处理
t = "^#" + "#".join(s) + "#$"
n = len(t)
p = [0] * n # 回文半径长度
# center/right：当前已知“最右回文”的中心与其右边界（right 为该回文最右端索引）
center = 0
right = 0
best_center = 0 # z最长字符串在预处理串 t 中的中心位置
# 线性扫描每个中心 i
for i in range(1, n - 1):
mirror = 2 * center - i # i 关于 center 的对称点
# i 在当前最右回文覆盖范围内，可以用对称性给 p[i] 一个下界
if i < right:
# right - i：i 到右边界还剩多少可用空间
# p[mirror]：对称点的半径
p[i] = min(right - i, p[mirror])
# 在已有半径基础上继续向两侧暴力扩展
while t[i + p[i] + 1] == t[i - p[i] - 1]:
p[i] += 1
# 如果以 i 为中心的回文超出了当前 right，则更新 center/right
if i + p[i] > right:
center = i
right = i + p[i]
# 维护全局最优
if p[i] > p[best_center]:
best_center = i
# 映射回原串，注意到原来的 radius 就是回文串长度
start = (best_center - p[best_center]) // 2
return s[start:start + p[best_center]]
4 寻找两个正序数组的中位数
背诵题，用二分法切割最小长度的数组得到，尤其需要注意边界条件（很麻烦）
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
A, B = nums1, nums2
if len(A) > len(B):
A, B = B, A
m, n = len(A), len(B)
half = (m + n + 1) // 2
low, high = 0, m
while low <= high:
i = (low + high) // 2
j = half - i
A_left = A[i - 1] if i > 0 else float("-inf")
A_right = A[i] if i < m else float("inf")
B_left = B[j - 1] if j > 0 else float("-inf")
B_right = B[j] if j < n else float("inf")
if A_left > B_right:
high = i - 1
elif B_left > A_right:
low = i + 1
else:
left_max = max(A_left, B_left)
if (m + n) % 2 == 1:
return float(left_max)
right_min = min(A_right, B_right)
return (left_max + right_min) / 2.0
raise RuntimeError("unreachable")3 无重复字符的最长子串
假如 [a, b] 区间是一个不重复的字串，那么 [a + 1, b] 一定也是，从下标 b 开始用 hash 扩展
本质是利用了下一个不重复字串的结尾一定 大于等于上一个的字串的性质
另外要注意的就是 python 中 set 的用法： add, discard 分别对应了增加和删除
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# 双指针滑动窗口
n = len(s)
mp = set()
r = 0
ret = 0
for l in range(n): # 闭区间区间窗口 [l, r]
while r < n and s[r] not in mp: # 不在则加入，同时最长长度更新
mp.add(s[r])
ret = max(r - l + 1, ret)
r += 1
mp.discard(s[l]) # 左边界前移
return ret2 两数相加
罗列所有情况即可，能考虑到所有的情况就没有难度
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
curr = dummy
p1, p2 = l1, l2
pre = 0 # 低位来的进位
while p1 and p2:
s = p1.val + p2.val + pre
pre = s // 10
new = ListNode(val=s % 10)
curr.next = new
curr = new
p1, p2 = p1.next, p2.next
left = p1 if p1 is not None else p2
while left is not None: # 有一个没结束
s = left.val + pre
pre = s // 10
new = ListNode(val=s % 10)
curr.next = new
curr = new
left = left.next
if pre != 0: # 还有进位
new = ListNode(val=pre)
curr.next = new
return dummy.next79 单词搜索
就是 dfs 回溯，可以有多种剪枝的方式
这里可以注意以下，能不用 hash 就不用，如果用到了 set() 尽可能用 remove() 因为能减少一次分支判断（代价是如果删除不存在的键会直接报错）
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
direction = [(-1, 0), (1, 0), (0, 1), (0, -1)]
start = word[0]
m = len(board) # m * n 矩形
n = len(board[0])
l = len(word)
def dfs(x, y, idx): # [0, idx) 匹配成功
if idx == l:
return True
for dir in direction:
xn = x + dir[0]
yn = y + dir[1]
if not (0 <= xn < m and 0 <= yn < n):
continue
if board[xn][yn] != word[idx]:
continue
board[xn][yn] = '#'
if (dfs(xn, yn, idx + 1)):
return True # 上报直接返回
board[xn][yn] = word[idx]
return False # 4 个边界都不对
for i in range(m):
for j in range(n):
if board[i][j] == start:
board[i][j] = '#'
if dfs(i, j, 1):
return True
board[i][j] = start
return False114 二叉树展开为链表
这道题的 O(1) 解法还是需要学习一下的
核心思想和 Morris 遍历算法类似，本质是能够确定两个点：
- 当前递归分支的“结束节点”是谁
- 结束之后的“唯一下一步”是谁
确定完毕后，把这两个点接上，就能展开递归栈为线性，不使用递归，改成循环
class Solution:
def flatten(self, root):
cur = root
while cur:
if cur.left:
# 1. 找左子树最右节点（展开后左链表的尾）
pre = cur.left
while pre.right:
pre = pre.right
# 2. 原右子树接到左子树尾部
pre.right = cur.right
# 3. 左子树整体搬到右边
cur.right = cur.left
cur.left = None
# 4. 沿着先序链继续
cur = cur.right621 任务调度器
数学题，永远是任务数最多的影响总长度，同时最长的个数有可能是多个
class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
m = len(tasks)
count = [0] * 26
tmax = 0 # 最多的任务的数量
cmax = 1 # 有几个并列最多的
for t in tasks:
idx = ord(t) - ord('A')
count[idx] += 1
if count[idx] > tmax:
cmax = 1
tmax = count[idx]
elif count[idx] == tmax:
cmax += 1
return max(m, (tmax - 1) * (n + 1) + cmax)617 合并二叉树
前序遍历标准解法
class Solution:
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
# 先序遍历
def pretraversal(r1, r2):
if not r1:
return r2
if not r2:
return r1
curr = TreeNode(r1.val + r2.val)
curr.left = pretraversal(r1.left, r2.left)
curr.right = pretraversal(r1.right, r2.right)
return curr
return pretraversal(root1, root2)
105 从前序与中序遍历序列构造二叉树
递归分割，有很多的细节需要注意一下
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
n = len(preorder)
pos = {v: i for i, v in enumerate(inorder)} # O(n)
def build(pre_a, pre_b, in_a, in_b):
if pre_a == pre_b:
return None
# 中分节点
root_val = preorder[pre_a] # 前序遍历的第一个
mid_idx = pos[root_val]
left_len = mid_idx - in_a
root = TreeNode(root_val)
root.left = build(pre_a + 1, pre_a + 1 + left_len, in_a, mid_idx)
root.right = build(pre_a + 1 + left_len, pre_b, mid_idx + 1, in_b)
return root
ret = build(0, n, 0, n)
return ret104 二叉树的最大深度
简单 dfs，另外还有层序遍历的方法，参考下一题
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
def dfs(curr):
if curr is None:
return 0
l = dfs(curr.left)
r = dfs(curr.right)
return max(l , r) + 1
return dfs(root)102 二叉树的层序遍历
BFS 用队列实现层序遍历，唯一要注意的就是如何判断是同一层
用两重循环 + 队列大小就可以控制，保证外层循环一定是同一层
注意一下：BFS 中一般不会把没有意义的节点放入队列，这会破坏 BFS 的语义逻辑
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
# 规定左进右出， 二重循环保证层级关系
q = deque()
if root is None:
return []
q.appendleft(root)
ret = []
while q:
size = len(q) # 当前层的节点数量
level = []
for _ in range(size):
curr = q.pop()
level.append(curr.val)
if curr.left:
q.appendleft(curr.left)
if curr.right:
q.appendleft(curr.right)
ret.append(level)
return ret101 对称二叉树
对称性用左右节点对比，递归保持比较逻辑不变（只对比根节点逻辑，孩子交给下一层递归）
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
def dfs(l, r):
if l is None:
return r is None
if r is None:
return l is None
if l.val != r.val:
return False
return dfs(l.left, r.right) and dfs(l.right, r.left)
if root is None:
return True
return dfs(root.left, root.right)98 验证二叉搜索树
BST 最重要的性质就是中序遍历是递增的
所以实际上就是中序遍历把树线性化，然后检查这个序列的严格递增性
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
# 先写一个中序遍历
pre = float("-inf")
def dfs(curr):
nonlocal pre
if curr is None:
return True
if not dfs(curr.left):
return False
if curr.val <= pre:
return False
pre = curr.val
if not dfs(curr.right):
return False
return True
return dfs(root)96 不同的二叉搜索树
动态规划题目（数学解法就不用考虑了）
BST 的个数只和节点的数量有关，就可以分析了，起始条件n = 0和 n = 1
class Solution:
def numTrees(self, n: int) -> int:
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
for j in range(1, i + 1):
dp[i] += dp[j - 1] * dp[i - j]
return dp[n]94 二叉树的中序遍历
递归不赘述了，这里写一个迭代法，迭代法还是要记忆一下逻辑的
当一个节点从栈顶 pop() 出来时，意味着：
- 它的左子树已经完全处理完（否则它不可能位于栈顶并被弹出）
- 现在该做的唯一事情就是：访问它自己（中）
- 然后把问题切换到它的右子树
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
stk = []
ret = []
curr = root
while curr or stk:
# 一直向左走
while curr:
stk.append(curr)
curr = curr.left
# 访问中间节点
curr = stk.pop()
ret.append(curr.val)
# 转向右子树
curr = curr.right
return ret85 最大矩形
先写 84 再写 85，是 84 的扩展解法，逐行计算 84
class Solution:
@staticmethod
def largestRectangleArea(heights: List[int]) -> int:
hs = [0] + heights + [0] # 不修改入参
stk = [0]
ret = 0
for i in range(1, len(hs)):
while hs[i] < hs[stk[-1]]:
mid = stk.pop()
left = stk[-1]
ret = max(ret, hs[mid] * (i - left - 1))
stk.append(i)
return ret
def maximalRectangle(self, matrix: List[List[str]]) -> int:
if not matrix or not matrix[0]:
return 0
R, C = len(matrix), len(matrix[0])
heights = [0] * C
ret = 0
# 从最小的高度开始逐步上升，一旦中断就归零
for r in range(R):
for c in range(C):
heights[c] = heights[c] + 1 if matrix[r][c] == '1' else 0
ret = max(ret, self.largestRectangleArea(heights),)
return ret84 柱状图中最大的矩形
单调栈的经典题目，这里使用了哨兵来处理栈中剩下的值
这里有隐患就是，如果heights中间出现了 0 值会出错，这在 85 题是比较麻烦的，具体修改可以看 85 解法
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
stk = []
heights.insert(0, 0)
heights.append(0)
n = len(heights)
ret = 0
for i in range(n):
while stk and heights[i] < heights[stk[-1]]:
# 不满足递减了，要弹出
mid_idx = stk.pop()
right_idx = i
left_idx = stk[-1]
sz = (right_idx - left_idx - 1) * heights[mid_idx]
ret = max(sz, ret)
stk.append(i)
return ret
1 两数之和
哈希经典题
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
s = dict()
n = len(nums)
ret = [] * n
for i in range(n):
if target - nums[i] not in s:
s[nums[i]] = i
else:
return [i, s[target - nums[i]]]78 子集
回溯经典题
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
ret = [[]]
n = len(nums)
def dfs(idx, path):
if idx >= n:
return
for i in range(idx, n):
path.append(nums[i])
ret.append(path.copy())
dfs(i + 1, path)
path.pop()
dfs(0, [])
return ret76 最小覆盖子串
难题，建议掌握一下，滑动窗口思路
class Solution:
def minWindow(self, s: str, t: str) -> str:
need = {}
n = len(s)
for c in t:
need[c] = need.get(c, 0) + 1
missing = len(need) # 表示窗口还缺多少字母种类
l, r = 0, 0 # [l, r)
best_l = 0
ret = float('inf') # 表示最短窗口
for r, ch in enumerate(s): # [l , r]
if ch in need:
need[ch] -= 1
if need[ch] == 0:
missing -= 1
while missing == 0: # 窗口齐了，开始收缩左边
# 左压缩窗口
window = r - l + 1
if window < ret:
best_l = l
ret = window
if s[l] in need:
need[s[l]] += 1
if need[s[l]] == 1:
missing += 1
l += 1
return "" if ret == float('inf') else s[best_l:best_l + ret]75 颜色分类
三指针算法，利用了快速排序的思想，维护两个已经确定的区间，并逐步扩大这个区间直到整个数组满足
class Solution:
def sortColors(self, nums: List[int]) -> None:
n = len(nums)
l, r, i = 0, n - 1, 0
while i <= r:
if nums[i] == 0:
nums[i], nums[l] = nums[l], nums[i]
l += 1
i += 1
elif nums[i] == 1:
i += 1
elif nums[i] == 2:
nums[i], nums[r] = nums[r], nums[i]
r -= 172 编辑距离
字符串 dp 经典题，遇到过就不难
这里写了个二维的，一维的优化一下就有了，不过一般是二维写出来再优化
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m = len(word1)
n = len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 初始化
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1 # 删减
dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1)
return dp[m][n]70 爬楼梯
dp 入门
class Solution:
def climbStairs(self, n: int) -> int:
now, pre1, pre2 = 1, 1, 1
for i in range(2, n + 1):
now = pre1 + pre2
pre1, pre2 = pre2, now
return now581 最短无序连续子数组
双向扩展区间法，可以参考一下，有点贪心的思想
class Solution:
def findUnsortedSubarray(self, nums: List[int]) -> int:
n = len(nums)
l, r = 0, -1
max_num = float('-inf')
min_num = float('inf')
for i in range(n):
if nums[i] >= max_num: # 递增允许
max_num = nums[i]
else:
r = i # 破坏递增了
if r == -1:
return 0 # 有序
for j in range(n - 1, -1, -1):
if nums[j] <= min_num:
min_num = nums[j]
else:
l = j
return r - l + 1 64 最小路径和
动态规划，压缩 1 维 dp 的时候有很多特判边界条件
这里用第一行特判+从第二行开始只对第一列特判，解决了 [0][0] 的下标问题
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
dp = [float('inf')] * n
dp[0] = grid[0][0]
# 初始化第一行
for j in range(1, n):
dp[j] = dp[j - 1] + grid[0][j]
# 从第二行开始
for i in range(1, m):
dp[0] += grid[i][0] # 第一列只能从上面来
for j in range(1, n):
dp[j] = min(dp[j], dp[j - 1]) + grid[i][j]
return dp[-1]62 不同路径
上一题的简化版本，用同样的方式从二维压缩到一维
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [1] * (n + 1) # 第一列全是 1
dp[0] = 1
for i in range(1, m):
dp[0] = 0 # 最上面一个不允许从上来
for j in range(1, n + 1):
dp[j] += dp [j - 1]
return dp[n]56 合并区间
排序后模拟即可，这里注意一下 python 中的排序语法就行了
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda x : (x[0], x[1]))
ret = []
path = intervals[0].copy()
for interval in intervals:
# 可以扩展
if interval[0] <= path[1]:
path[1] = max(interval[1], path[1]) # 扩展右区间
else: # 断开了
ret.append(path.copy())
path = interval.copy()
if path:
ret.append(path)
return ret55 跳跃游戏
简单贪心
class Solution:
def canJump(self, nums: List[int]) -> bool:
i, far = 0, 0
n = len(nums)
while i <= far and i < n:
far = max(far, i + nums[i])
i += 1
return i == n53 最大子数组和
简答贪心
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
# 前缀和
ret = float('-inf')
curr = 0
for n in nums:
curr += n
ret = max(ret, curr)
if curr < 0:
curr = 0
return ret