Hot100算法题精解：动态规划与回溯法实战

1. 理解hot100算法题的本质

hot100算法题是程序员社区中广为流传的一个经典题目集合，它精选了100道高频出现的算法面试题。这个系列之所以被称为"hot"，是因为这些题目在各大科技公司的技术面试中出现概率极高，堪称算法准备路上的必刷题库。

我最初接触hot100是在准备跳槽期间，当时发现无论去哪个技术论坛，关于算法面试准备的讨论都绕不开这个系列。经过系统刷题后，我顺利通过了多家一线互联网公司的技术面试，这让我深刻体会到掌握hot100的价值。

2. hot100(71-80)题目精析

2.1 第71题：编辑距离

这道题要求计算将一个单词转换成另一个单词所需的最少操作次数。操作包括插入、删除和替换字符。

核心解法：使用动态规划，构建一个(m+1)×(n+1)的DP表格，其中m和n分别是两个单词的长度。DP[i][j]表示word1前i个字符转换为word2前j个字符的最小操作次数。

def minDistance(word1, word2): m, n = len(word1), 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] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) return dp[m][n]

优化技巧：

• 空间复杂度可优化到O(n)
• 对于某些特殊情况可以提前返回

2.2 第72题：矩阵置零

给定一个m×n矩阵，如果一个元素为0，则将其所在行和列的所有元素都设为0。

最优解法：使用矩阵的第一行和第一列来标记是否需要置零，同时用两个额外变量记录第一行和第一列本身是否需要置零。

def setZeroes(matrix): m, n = len(matrix), len(matrix[0]) first_row_has_zero = any(matrix[0][j] == 0 for j in range(n)) first_col_has_zero = any(matrix[i][0] == 0 for i in range(m)) for i in range(1, m): for j in range(1, n): if matrix[i][j] == 0: matrix[i][0] = 0 matrix[0][j] = 0 for i in range(1, m): for j in range(1, n): if matrix[i][0] == 0 or matrix[0][j] == 0: matrix[i][j] = 0 if first_row_has_zero: for j in range(n): matrix[0][j] = 0 if first_col_has_zero: for i in range(m): matrix[i][0] = 0

注意事项：

• 必须先处理标记，再根据标记置零
• 要特别注意第一行和第一列的特殊处理

2.3 第73题：搜索二维矩阵

编写一个高效的算法来判断m×n矩阵中是否存在一个目标值。该矩阵具有以下特性：

• 每行中的整数从左到右按升序排列
• 每行的第一个整数大于前一行的最后一个整数

二分查找解法：将二维矩阵视为一维数组进行二分查找。

def searchMatrix(matrix, target): if not matrix or not matrix[0]: return False m, n = len(matrix), len(matrix[0]) left, right = 0, m * n - 1 while left <= right: mid = (left + right) // 2 row, col = mid // n, mid % n if matrix[row][col] == target: return True elif matrix[row][col] < target: left = mid + 1 else: right = mid - 1 return False

时间复杂度：O(log(mn))，与常规二分查找相同

2.4 第74题：颜色分类

给定一个包含红色、白色和蓝色元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，且按照红色、白色、蓝色的顺序排列。

荷兰国旗问题解法：使用三指针法，一个指针跟踪红色位置，一个跟踪蓝色位置，一个用于遍历。

def sortColors(nums): red, white, blue = 0, 0, len(nums)-1 while white <= blue: if nums[white] == 0: nums[red], nums[white] = nums[white], nums[red] red += 1 white += 1 elif nums[white] == 1: white += 1 else: nums[white], nums[blue] = nums[blue], nums[white] blue -= 1

关键点：

• white指针是主遍历指针
• 遇到红色时交换并同时移动red和white
• 遇到蓝色时只交换并移动blue

2.5 第75题：最小覆盖子串

给定一个字符串S和一个字符串T，在S中找到包含T所有字符的最小子串。

滑动窗口解法：使用哈希表记录T中字符出现次数，用滑动窗口在S中寻找满足条件的最小窗口。

from collections import defaultdict def minWindow(s, t): need = defaultdict(int) for c in t: need[c] += 1 left, right = 0, 0 missing = len(t) min_len = float('inf') result = "" while right < len(s): if s[right] in need: if need[s[right]] > 0: missing -= 1 need[s[right]] -= 1 right += 1 while missing == 0: if right - left < min_len: min_len = right - left result = s[left:right] if s[left] in need: need[s[left]] += 1 if need[s[left]] > 0: missing += 1 left += 1 return result

优化技巧：

• 使用counter记录当前窗口内字符满足情况
• 可以预先过滤S中不在T的字符，减少处理量

3. hot100(76-80)题目详解

3.1 第76题：子集

给定一组不含重复元素的整数数组nums，返回所有可能的子集（幂集）。

回溯法解法：通过递归生成所有可能的子集组合。

def subsets(nums): res = [] def backtrack(start, path): res.append(path.copy()) for i in range(start, len(nums)): path.append(nums[i]) backtrack(i+1, path) path.pop() backtrack(0, []) return res

位运算解法：利用位掩码表示元素是否在子集中。

def subsets(nums): n = len(nums) res = [] for mask in range(1 << n): subset = [] for i in range(n): if mask & (1 << i): subset.append(nums[i]) res.append(subset) return res

3.2 第77题：单词搜索

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

回溯法解法：在网格中深度优先搜索匹配的单词路径。

def exist(board, word): m, n = len(board), len(board[0]) def dfs(i, j, k): if not (0 <= i < m and 0 <= j < n) or board[i][j] != word[k]: return False if k == len(word) - 1: return True tmp, board[i][j] = board[i][j], '#' found = dfs(i+1, j, k+1) or dfs(i-1, j, k+1) or dfs(i, j+1, k+1) or dfs(i, j-1, k+1) board[i][j] = tmp return found for i in range(m): for j in range(n): if dfs(i, j, 0): return True return False

优化技巧：

• 提前检查word首字母和尾字母出现频率
• 使用Trie树优化多单词搜索场景

3.3 第78题：柱状图中最大的矩形

给定n个非负整数，表示柱状图中各个柱子的高度，求该柱状图中能够勾勒出来的最大矩形的面积。

单调栈解法：维护一个单调递增的栈，计算以每个柱子为高的最大矩形面积。

def largestRectangleArea(heights): stack = [] max_area = 0 heights.append(0) for i in range(len(heights)): while stack and heights[stack[-1]] > heights[i]: h = heights[stack.pop()] w = i - stack[-1] - 1 if stack else i max_area = max(max_area, h * w) stack.append(i) return max_area

关键点：

• 需要在末尾添加一个0高度确保所有柱子都被处理
• 栈中存储的是索引而非高度值
• 宽度计算要考虑栈是否为空

3.4 第79题：最大矩形

给定一个仅包含0和1的二维二进制矩阵，找出只包含1的最大矩形，并返回其面积。

动态规划解法：将问题转化为多个柱状图最大矩形问题。

def maximalRectangle(matrix): if not matrix: return 0 m, n = len(matrix), len(matrix[0]) heights = [0] * n max_area = 0 for i in range(m): for j in range(n): heights[j] = heights[j] + 1 if matrix[i][j] == '1' else 0 max_area = max(max_area, largestRectangleArea(heights.copy())) return max_area

优化方向：

• 复用柱状图最大矩形的解法
• 可以边构建高度数组边计算最大面积

3.5 第80题：二叉树中的最大路径和

给定一个非空二叉树，返回其最大路径和。路径定义为从树中任意节点出发，达到任意节点的序列。

递归解法：后序遍历计算每个节点的最大贡献值。

class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def maxPathSum(root): max_sum = -float('inf') def max_gain(node): nonlocal max_sum if not node: return 0 left_gain = max(max_gain(node.left), 0) right_gain = max(max_gain(node.right), 0) price_newpath = node.val + left_gain + right_gain max_sum = max(max_sum, price_newpath) return node.val + max(left_gain, right_gain) max_gain(root) return max_sum

注意事项：

• 路径可以不经过根节点
• 节点值可能为负数，需要与0比较
• 最大路径可能存在于左子树或右子树中

4. hot100刷题策略与技巧

4.1 分类刷题法

将hot100题目按类型分类，集中攻克同一类型的题目：

• 动态规划：编辑距离、最大子序和等
• 回溯法：子集、组合、排列等
• 双指针：盛最多水的容器、三数之和等
• 贪心算法：跳跃游戏、买卖股票最佳时机等

4.2 五遍刷题法

1. 第一遍：理解题目，思考解法，看答案
2. 第二遍：自己实现，确保理解每个细节
3. 第三遍：24小时后重新实现
4. 第四遍：一周后重新实现
5. 第五遍：面试前复习实现

4.3 常见错误与调试技巧

边界条件错误：

• 数组为空或只有一个元素
• 整数溢出（特别是Python中容易被忽略）
• 递归终止条件不正确

调试方法：

• 打印关键变量值
• 使用小规模测试用例
• 画图辅助理解（特别是树和图问题）

4.4 面试实战技巧

1. 先明确问题要求，确认输入输出
2. 提出暴力解法，分析时间复杂度
3. 思考优化方向，逐步改进
4. 编写代码时注意变量命名和代码结构
5. 测试边缘案例，解释代码逻辑

5. hot100题目延伸学习

5.1 相似题目推荐

1. 编辑距离扩展：实现实际编辑操作序列
2. 矩阵置零扩展：处理稀疏矩阵存储
3. 颜色分类扩展：处理更多颜色分类
4. 最大矩形扩展：处理三维情况下的最大立方体

5.2 进阶学习资源

1. 《算法导论》：深入理解算法原理
2. LeetCode讨论区：学习他人优秀解法
3. 算法可视化网站：直观理解算法执行过程
4. 在线判题系统：大量练习提升熟练度

5.3 算法竞赛与面试区别

1. 面试更注重代码可读性和沟通能力
2. 竞赛追求极致性能，面试更看重正确性
3. 面试常考经典算法，竞赛常有创新题型
4. 面试需要解释思路，竞赛只需通过测试用例

在实际刷题过程中，我发现hot100的71-80这组题目特别考验对多种算法技巧的综合运用能力。比如编辑距离需要深入理解动态规划，而颜色分类则需要巧妙运用双指针技巧。建议每做完一道题后，花时间总结这类问题的通用解法模式，这样在遇到类似问题时能够快速识别并应用相应解法。