Hot 100 题解（二）
Hot 100 第二部分
Hot 100 指的是 LeetCode 上的一个题单
撰写第 34 ~ 68 题
为什么是 67 呢，因为没开会员写不了 253 会议室 II 哈哈哈
339 除法求值
图论，先跳过
394 字符串解码
因为有嵌套的存在，所以一般使用栈的形式处理这种
遇到 ‘[’ 就进，遇到 ‘]’ 就退到上一个 ‘[’ ，然后把处理完的字符串放进去
数字处理时候，遇到 ‘[’ 表示当前数字完结了，把数字放进栈
标准解答会更加简洁，我这边写的则相对直观一点
class Solution:
def decodeString(self, s: str) -> str:
str_stk = []
num_stk = []
num = 0
for c in s:
if c.isdigit():
num = num * 10 + int(c)
elif c == '[':
num_stk.append(num)
num = 0 # 这个数字处理完了，清空并入栈
str_stk.append(c)
elif c == ']':
parts = []
while str_stk and str_stk[-1] != '[':
parts.append(str_stk.pop())
str_stk.pop() # 弹出 '['
repeat_str = "".join(reversed(parts)) # 注意这里弹出来是颠倒的
k = num_stk.pop()
str_stk.append(repeat_str * k) # 放回栈中
else:
str_stk.append(c)
return "".join(str_stk)347 前 K 个高频元素
使用 heapq 的 api，小顶堆解法
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
mp = Counter(nums)
heap = []
for key, val in mp.items():
if len(heap) < k:
heapq.heappush(heap, (val, key))
elif val > heap[0][0]:
heapq.heapreplace(heap, (val, key))
return [key for _, key in heap]338 比特位计数
这个实际上使用dp来写，而不是逐个运算，最后一个用位运算
class Solution:
def countBits(self, n: int) -> List[int]:
dp = [0] * (n + 1)
for num in range(1, n + 1):
dp[num] = dp[num >> 1] + (num & 1)
return dp 337 打家劫舍 III
经典 dp, 注意是取最优解, 而不是一定偷
class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
def dfs(node):
if not node:
return (0, 0) # (不偷, 偷)
l0, l1 = dfs(node.left)
r0, r1 = dfs(node.right)
not_rob = max(l0, l1) + max(r0, r1) # 孩子可以偷也可以不偷
rob = l0 + r0 + node.val # 一定不能偷
return (not_rob, rob)
return max(dfs(root))121 买卖股票的最佳时机
计算最大差值，抛砖引玉的砖
class Solution:
def maxProfit(self, prices: List[int]) -> int:
min_p = float('inf')
ret = 0
for p in prices:
ret = max(p - min_p, ret)
min_p = min(p, min_p)
return ret312 戳气球
这道题是一个 hard 的区间dp，将一个长问题分为多个子区间去完成，要点就是状态转移是“最后一步的操作”，区间有可能是二维双向扩展的，他们的特点是dp需要重建，做一个决策会改变问题结构
相似的题目还有：516, 647, 1039, 1130, 375, 546（越来越难）
dp 数组含义：在区间 (l, r)（注意是开区间）里最后戳的是 k，那么最后一次得到的金币
这个就能够固定左右边界，然后获得的收益只和 k 有关系了，而问题被分成了 k 左右两个区间
把 dp 数组设置为 dp[a][b] 是区间 (a, b) 之间的最优解，从最小的区间开始向上推进
class Solution:
def maxCoins(self, nums: List[int]) -> int:
a = [1] + nums + [1]
m = len(a)
dp = [[0] * m for _ in range(m)]
# dp[l][r] 表示开区间 (l, r) 全部戳完的最大金币
for l in range(m - 1, -1, -1):
for r in range(l + 2, m): # 至少留一个 k：l < k < r
best = 0
for k in range(l + 1, r):
best = max(best, dp[l][k] + dp[k][r] + a[l] * a[k] * a[r])
dp[l][r] = best
return dp[0][m - 1]309 买卖股票的最佳时机含冷冻期
代码随想录经典题，略
class Solution:
def maxProfit(self, prices: List[int]) -> int:
free, hold, frozen = 0, -prices[0], 0
for p in prices[1:]:
new_frozen = hold + p
new_free = max(free, frozen)
new_hold = max(hold, free - p)
free, hold, frozen = new_free, new_hold, new_frozen
return max(free, frozen)301 删除无效的括号
hard 回溯，有一定的难度，注意回溯的一个特征就是找到所有的解
注意到：在某个区间内，) 数量一定是小于等于 ( 数量的，否则必定无法匹配成功，这是剪枝的关键地方
不能全局到结尾来统计左右括号数量，一定要逐个区间计算，否则会出现 )( 不用删的错误情况
class Solution:
def removeInvalidParentheses(self, s: str) -> List[str]:
lrem = rrem = 0
for c in s:
if c == '(':
lrem += 1
elif c == ')':
if lrem == 0:
rrem += 1 # 左边没了，只能删右边
else:
lrem -= 1 # 预计匹配，左边少删一个
def is_valid(s):
balance = 0
for c in s:
if c == '(':
balance += 1
elif c == ')':
balance -= 1
if balance < 0:
return False
return (balance == 0)
def dfs(start: int, lrem: int, rrem: int, cur: str):
# 只要超删就剪枝
if lrem < 0 or rrem < 0:
return
# 删够了才检查合法性
if lrem == 0 and rrem == 0 and is_valid(cur):
ret.append(cur)
return
for i in range(start, len(cur)):
# 只对括号尝试删除
if cur[i] not in '()':
continue
# 去重：同一层如果连续相同字符，只删第一个
if i > start and cur[i] == cur[i - 1]:
continue
nxt = cur[:i] + cur[i + 1:]
if cur[i] == '(':
dfs(i, lrem - 1, rrem, nxt)
else: # cur[i] == ')'
dfs(i, lrem, rrem - 1, nxt)
ret = []
dfs(0, lrem, rrem, s)
return ret300 最长递增子序列
dp方法就是从前面找一个比他小的进行状态累加
但是有 二分+贪心 的最优解，比较难想：如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小
贪心就在于：我一定会在同一个位置选择更小的那个数，使得后面的数尽可能比我这个位置的数字大
如果这个数比我所有已知的数字都大，那么就是我的序列就上升一次，否则替换一个台阶
具体的讲解可以看看
from bisect import bisect_left
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
tails = [] # 这是一个有序数组
for n in nums:
idx = bisect_left(tails, n) # 找到 <= x 的下标位置
if idx == len(tails): # 是结尾，直接加入
tails.append(n)
else:
tails[idx] = n
return len(tails)287 寻找重复数
图论判环算法
297 二叉树的序列化与反序列化
主要是要标记 null 这一个注意点，如果是前序遍历就是顺序解码
可以回去复习一下：根据前+中遍历来恢复一个二叉树的算法
class Codec:
def serialize(self, root):
# 前序遍历
ret: str = []
def preTraversal(curr):
nonlocal ret
if curr is None:
ret.append('#')
return
ret.append(str(curr.val))
preTraversal(curr.left)
preTraversal(curr.right)
preTraversal(root)
# print(ret)
return ','.join(ret)
def deserialize(self, data):
it = iter(data.split(','))
def build():
x = next(it)
if x == '#':
return None
node = TreeNode(int(x))
node.left = build()
node.right = build()
return node
return build()
287 寻找重复数
这题目和 142 环形链表 II 都使用 Floyid 算法可以判断环的位置
把下标看成是一个节点，把 nums[i] 看成是下一个节点，就是一个链表找环的题目
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
# Floyid 环算法
slow = nums[0]
fast = nums[nums[0]]
while slow != fast:
slow = nums[slow]
fast = nums[nums[fast]]
# 找到相遇点，回去找入环点
slow = 0
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow283 移动零
双指针移动所有不是 0 的数据
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
# 原地修改不返回， 把所有不是 0 的全部向前移动
n = len(nums)
slow = 0
for fast in range(n):
if nums[fast] != 0:
nums[slow] = nums[fast]
slow += 1
while slow < n:
nums[slow] = 0
slow += 1279 完全平方数
动态规划经典题目
class Solution:
def numSquares(self, n: int) -> int:
dp = [float('inf')] * (n + 1) # 1 ~ n
dp[0] = 0
for i in range(1, n + 1):
for sq in range(int(sqrt(i)) + 1):
dp[i] = min(dp[i], dp[i - sq * sq] + 1)
return dp[n]253 会议室 II
没会员，下次一定
240 搜索二维矩阵 II
把起点设置在左下角，或者右上角，就可以每次判断去除一整行或者列
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m = len(matrix)
n = len(matrix[0])
i, j = m -1, 0
while i >= 0 and j < n:
if matrix[i][j] > target:
i -= 1
elif matrix[i][j] < target:
j += 1
else:
return True
else:
return False239 滑动窗口最大值
可以用 top k 的同样思路，使用大顶堆，一旦堆顶过期了就弹出，否则只需要 push 就行了
这里写一下更优解法，单调队列的方式，这个还是蛮难写的，要重点学一学：
- 如果遇到
i < j且nums[i] <= nums[j]的时候，一旦nums[j]入队就可以把nums[i]直接丢弃了（只要nums[j]在就一定是他更大） - 如果出口处这个最大的元素已经被窗口抛弃了，则正常弹出
这两条规则分别对应 窗口右侧加入，窗口左侧放入两种操作，这就构成了我们的整个单调队列，最大值永远是出口处的元素
从右侧放进来的元素，会从右边一直删除元素直到，他左边那个值比他大（或者他就是最大的），这样左边永远是更大的值
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
q = deque() # 存下标，保证 nums[q] 单调递减（队首最大）
for i in range(k):
while q and nums[q[-1]] <= nums[i]:
q.pop() # 从队尾弹出更小/相等的
q.append(i)
ret = [nums[q[0]]]
for i in range(k, n):
if q and q[0] <= i - k:
q.popleft() # 先移除过期（只可能在队首）
while q and nums[q[-1]] <= nums[i]:
q.pop() # 比当前值来的早，还比当前值小，没有任何维护的意义
q.append(i)
ret.append(nums[q[0]])
return ret22 括号生成
是 LeetCode 301 删除无效的括号 的派生题目，是那道题的子集，更简单的版本
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = []
path = []
def backtrace(left, right):
if left == 0 and right == 0:
res.append("".join(path))
return
if left > right: # 右括号数 > 左括号
return
if left > 0:
path.append('(')
backtrace(left - 1, right)
path.pop()
if right > 0:
path.append(')')
backtrace(left, right - 1)
path.pop()
backtrace(n, n)
return res49 字母异位词分组
判断异位词应该使用 Hash，这里主要使用一个 26 维的向量（实际上就是一个 hash）作为 key
外层再进行一个 hash 将所有的（26维向量相同）异位词放一起
这里插播一个 python 的要点，dict.get() 拿到的不是原来的数据，修改是不会写入到 dict 中的，应该使用 dict.setdefault 或者直接初始化 dict 为 mp = defaultdict(list)
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
mp = {}
for s in strs:
count = [0] * 26
for c in s:
count[ord(c) - ord('a')] += 1
key = tuple(count)
mp.setdefault(key, []).append(s)
return list(mp.values())48 旋转图像
这题有两种解法，一个是四点交换（算边界条件麻烦点），一个是转置+对称交换
其中四点变换（计算机方法）的方法更加适合 cpp 因为看起来清晰点，而且操作更加底层
实际上这两个算法的复杂度都是空间 O(1) 时间 O(n^2) ，没有什么区别，这里用 cpp 写吧，逻辑清楚点，不然就是 4 元素 tuple 直接交换了
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for (int i = 0; i <= n / 2 - 1; i++) {
for (int j = 0; j <= (n - 1) / 2; j++) {
// 四点变换
int tmp = matrix[i][j];
matrix[i][j] = matrix[n - j - 1][i];
matrix[n - j - 1][i] = matrix[n - i -1][n - j -1];
matrix[n - i -1][n - j -1] = matrix[j][n - i -1];
matrix[j][n - i -1] = tmp;
}
}
}
};46 全排列
全排列回溯可以用 标记数组的方式来一个个遍历
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
used = [False] * n
ret = []
curr = []
def backtrace():
if len(curr) == n:
ret.append(curr.copy())
return
for i in range(n):
if used[i]:
continue
used[i] = True
curr.append(nums[i])
backtrace()
curr.pop()
used[i] = False
backtrace()
print(ret)
return ret42 接雨水
传奇背诵题接雨水，要么单调栈，要么双指针
class Solution:
def trap(self, height: List[int]) -> int:
stk = []
ret = 0
n = len(height)
for i in range(n):
while stk and height[stk[-1]] <= height[i]:
# 单调栈：非空且栈顶 <= 当前值，需要弹出
mid_idx = stk.pop()
if stk: # 表示 mid_idx 左边有比他大的, 可以接水
left_idx = stk[-1]
l = i - left_idx -1
h = min(height[left_idx], height[i]) - height[mid_idx]
ret += l * h
# print(f"{l} * {h}, {ret}, ({left_idx}, {mid_idx}, {i})")
stk.append(i)
return ret39 组合总和
经典回溯
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
ret = []
n = len(candidates)
def backtrace(idx, path, left):
if left == 0:
ret.append(path.copy())
return
for i in range(idx, n):
if candidates[i] > left:
path.append(candidates[i])
break
backtrace(i, path, left - candidates[i])
path.pop()
backtrace(0, [], target)
return ret543 二叉树的直径
递归简单题
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
ret = 0
def dfs(root):
if root is None:
return 0
l = dfs(root.left)
r = dfs(root.right)
nonlocal ret
ret = max(l + r, ret)
return max(l, r) + 1
dfs(root)
return ret34 在排序数组中查找元素的第一个和最后一个位置
这道题目很好，涉及到了二分查找的本质，我们可以从中抽象出二分查找的通用模板
二分查找边界的本质：一个结构，对某一个 bool 表达式的值呈现单调性，我们通过对半取区间来找到第一个发生变化的区间
False False False True True True
↑
我们要找的点所以说，找下界就是找到第一个让 nums[i] >= target 从 false 变为 true 的点，上界就是第一个让 nums[i] > target 从 false 变为 true的点
我们列出循环不变量的表达式（伪代码）：bool [0, l) == Talse , bool [r, n) == True
所以有这个通用公式（面向于我们从 False 转到 True 的数组单调性）：
if f(mid) == True: # f(mid) == True, 保证了 [r, n) 是 True
r = mid
else: # 保证了 [0, mid + 1) 是 False
l = mid + 1最后这道题的解法是
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
# 二分查找, 一个是 [0, l) <= target, 另一个是 [l, n) > target
n = len(nums)
def lower(): # 找到第一个 nums[i] >= target
l, r = 0, n
while l < r: # [l, r)
mid = (l + r) >> 1
if nums[mid] >= target:
r = mid
else:
l = mid + 1
return l
def upper(): # 找到第一个 nums[i] > target
l, r = 0, n
while l < r: # [l, r)
mid = (l + r) >> 1
if nums[mid] > target:
r = mid
else:
l = mid + 1
return l
l = lower()
u = upper()
if l == n or nums[l] != target:
return(-1, -1)
else:
return(l, u - 1)33 搜索旋转排序数组
两次二分，实际上和上一题目同类型，理解了二分就很快写得出来
class Solution:
def search(self, nums: List[int], target: int) -> int:
n = len(nums)
last = nums[-1]
def find_split():
l, r = 0, n
while l < r:
mid = (l + r) // 2
if nums[mid] <= last:
r = mid
else:
l = mid + 1
return l
pivot = find_split()
def bin_search(l, r): # 等值二分查找
while l < r:
mid = (l + r) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
l = mid + 1
else:
r = mid
return -1
if target <= last:
return bin_search(pivot, n)
else:
return bin_search(0, pivot)32 最长有效括号
这道题有两种写法，一个是 dp （讨论两种情况），另一个是双向扫描贪心（太难想到了）
由于 dp 虽然不是最优解但是也有一定的参考价值，这里把两种方式都写一下
class Solution:
def longestValidParentheses(self, s: str) -> int:
n = len(s)
dp = [0] * n # dp[i]: 以 i 结尾的最长有效括号长度
ret = 0
for i in range(1, n):
if s[i] == '(':
continue # 以 '(' 结尾不可能是有效括号
if s[i - 1] == '(':
# 情况1：紧邻 ()
dp[i] = (dp[i - 2] if i >= 2 else 0) + 2
else:
# 情况2：...)) 尝试跨过 dp[i-1] 那段去找 '('
pre = dp[i - 1]
j = i - pre - 1 # 可能与 s[i] 匹配的 '(' 位置
if j >= 0 and s[j] == '(':
dp[i] = pre + 2 + (dp[j - 1] if j >= 1 else 0)
ret = max(ret, dp[i])
return ret遇到 '('：left += 1，遇到 ')'：right += 1
若 right > left：说明右括号过多，当前段不可能再变合法，重置 left = right = 0
若 left == right：当前段合法，长度 2 * right，更新答案
左右各扫描一次就能补齐所有答案
class Solution:
def longestValidParentheses(self, s: str) -> int:
ans = 0
# left -> right
left = right = 0
for ch in s:
if ch == '(':
left += 1
else:
right += 1
if right > left:
left = right = 0
elif left == right:
ans = max(ans, 2 * right)
# right -> left
left = right = 0
for ch in reversed(s):
if ch == '(':
left += 1
else:
right += 1
if left > right:
left = right = 0
elif left == right:
ans = max(ans, 2 * left)
return ans31 下一个排列
模拟思路题目，写过一遍就好了
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
n = len(nums)
pre = -1
i = n - 1
def reverse_nums(nums, a, b):
while a < b:
nums[a], nums[b] = nums[b], nums[a]
a += 1
b -= 1
while i >= 0:
if nums[i] < pre:
break
pre = nums[i]
i -= 1
else:
reverse_nums(nums, 0, n - 1) # 重新排列最小值
return
# 找到第一个 比 nums[i] 大的交换一下
for j in range(n - 1, i, -1):
if nums[i] < nums[j]:
nums[i], nums[j] = nums[j], nums[i]
break
reverse_nums(nums, i + 1, n - 1)538 把二叉搜索树转换为累加树
这道题有一个 Moris 遍历的方法，可以使用 O(1) 的空间，后面可以学习一下，这里先放一个普通DFS 解法
class Solution:
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
total = 0
def dfs(root):
if root is None:
return
# 右中左
nonlocal total
dfs(root.right)
total += root.val
root.val = total
dfs(root.left)
dfs(root)
return root23 合并 K 个升序链表
这里直接使用最小堆，注意 heapq 中没有 cmp 的 key 只能自行构造元组
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
heap = []
heapq.heapify(heap)
uid = 0
for node in lists:
if node:
uid += 1
heapq.heappush(heap, (node.val, uid, node))
dummy = ListNode()
curr = dummy
while heap: # 只要非空
_, _, nd = heapq.heappop(heap)
curr.next = nd
curr = curr.next
if nd.next is not None:
uid += 1
heapq.heappush(heap, (nd.next.val, uid, nd.next))
return dummy.next560 和为 K 的子数组
这不是一个 dp 题目，连续子数组求和是前缀和的应用场景
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
total = 0
count = defaultdict(int)
count[0] = 1
ret = 0
for n in nums:
total += n # 当前位置的前缀和
ret += count[total - k] # 找已经遇到的更小的前缀和点
count[total] += 1
return ret21 合并两个有序链表
白给题目
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
curr = dummy
l1, l2 = list1, list2
while l1 and l2:
if l1.val < l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 if l1 is not None else l2
return dummy.next20 有效的括号
白给题经典栈解法，注意最后栈一定要保持是空的
class Solution:
def isValid(self, s: str) -> bool:
mp = {')' : '(', '}' : '{', ']' : '['}
stk = []
for c in s:
if c not in mp:
stk.append(c)
else:
if not stk or stk.pop() != mp[c]:
return False
return not stk # 最后栈必须是空的 19 删除链表的倒数第 N 个结点
简单的双指针题目，但是要注意的边界条件其实蛮多的，建议是实际手写一次试一下
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
slow, fast = dummy, dummy
for i in range(n):
fast = fast.next
while fast.next is not None:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return dummy.next
17 电话号码的字母组合
相对简单好想到的回溯算法
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
mp = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno',
'pqrs', 'tuv', 'wxyz']
n = len(digits)
ret = []
if not digits:
return []
def backtrace(path, idx):
if idx == n:
ret.append("".join(path))
return
for c in mp[int(digits[idx])]:
path.append(c)
backtrace(path, idx + 1) # 下一个字母
path.pop()
backtrace([], 0)
return retHot 100 题解（二）
https://rainerseventeen.cn/index.php/Algorithm/55.html