1. 理解hot100算法题的本质hot100算法题是程序员社区中广为流传的一个经典题目集合它精选了100道高频出现的算法面试题。这个系列之所以被称为hot是因为这些题目在各大科技公司的技术面试中出现概率极高堪称算法准备路上的必刷题库。我最初接触hot100是在准备跳槽期间当时发现无论去哪个技术论坛关于算法面试准备的讨论都绕不开这个系列。经过系统刷题后我顺利通过了多家一线互联网公司的技术面试这让我深刻体会到掌握hot100的价值。2. hot100(71-80)题目精析2.1 第71题编辑距离这道题要求计算将一个单词转换成另一个单词所需的最少操作次数。操作包括插入、删除和替换字符。核心解法使用动态规划构建一个(m1)×(n1)的DP表格其中m和n分别是两个单词的长度。DP[i][j]表示word1前i个字符转换为word2前j个字符的最小操作次数。def minDistance(word1, word2): m, n len(word1), len(word2) dp [[0]*(n1) for _ in range(m1)] for i in range(m1): dp[i][0] i for j in range(n1): dp[0][j] j for i in range(1, m1): for j in range(1, n1): 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遇到蓝色时只交换并移动blue2.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(i1, 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 res3.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(i1, j, k1) or dfs(i-1, j, k1) or dfs(i, j1, k1) or dfs(i, j-1, k1) 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, val0, leftNone, rightNone): 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 五遍刷题法第一遍理解题目思考解法看答案第二遍自己实现确保理解每个细节第三遍24小时后重新实现第四遍一周后重新实现第五遍面试前复习实现4.3 常见错误与调试技巧边界条件错误数组为空或只有一个元素整数溢出特别是Python中容易被忽略递归终止条件不正确调试方法打印关键变量值使用小规模测试用例画图辅助理解特别是树和图问题4.4 面试实战技巧先明确问题要求确认输入输出提出暴力解法分析时间复杂度思考优化方向逐步改进编写代码时注意变量命名和代码结构测试边缘案例解释代码逻辑5. hot100题目延伸学习5.1 相似题目推荐编辑距离扩展实现实际编辑操作序列矩阵置零扩展处理稀疏矩阵存储颜色分类扩展处理更多颜色分类最大矩形扩展处理三维情况下的最大立方体5.2 进阶学习资源《算法导论》深入理解算法原理LeetCode讨论区学习他人优秀解法算法可视化网站直观理解算法执行过程在线判题系统大量练习提升熟练度5.3 算法竞赛与面试区别面试更注重代码可读性和沟通能力竞赛追求极致性能面试更看重正确性面试常考经典算法竞赛常有创新题型面试需要解释思路竞赛只需通过测试用例在实际刷题过程中我发现hot100的71-80这组题目特别考验对多种算法技巧的综合运用能力。比如编辑距离需要深入理解动态规划而颜色分类则需要巧妙运用双指针技巧。建议每做完一道题后花时间总结这类问题的通用解法模式这样在遇到类似问题时能够快速识别并应用相应解法。 
长河君 · 2026/11/3 11:38:42 · 阅读 1.2k Hot100算法题精解：动态规划与回溯法实战
1. 理解hot100算法题的本质hot100算法题是程序员社区中广为流传的一个经典题目集合它精选了100道高频出现的算法面试题。这个系列之所以被称为hot是因为这些题目在各大科技公司的技术面试中出现概率极高堪称算法准备路上的必刷题库。我最初接触hot100是在准备跳槽期间当时发现无论去哪个技术论坛关于算法面试准备的讨论都绕不开这个系列。经过系统刷题后我顺利通过了多家一线互联网公司的技术面试这让我深刻体会到掌握hot100的价值。2. hot100(71-80)题目精析2.1 第71题编辑距离这道题要求计算将一个单词转换成另一个单词所需的最少操作次数。操作包括插入、删除和替换字符。核心解法使用动态规划构建一个(m1)×(n1)的DP表格其中m和n分别是两个单词的长度。DP[i][j]表示word1前i个字符转换为word2前j个字符的最小操作次数。def minDistance(word1, word2): m, n len(word1), len(word2) dp [[0]*(n1) for _ in range(m1)] for i in range(m1): dp[i][0] i for j in range(n1): dp[0][j] j for i in range(1, m1): for j in range(1, n1): 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遇到蓝色时只交换并移动blue2.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(i1, 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 res3.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(i1, j, k1) or dfs(i-1, j, k1) or dfs(i, j1, k1) or dfs(i, j-1, k1) 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, val0, leftNone, rightNone): 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 五遍刷题法第一遍理解题目思考解法看答案第二遍自己实现确保理解每个细节第三遍24小时后重新实现第四遍一周后重新实现第五遍面试前复习实现4.3 常见错误与调试技巧边界条件错误数组为空或只有一个元素整数溢出特别是Python中容易被忽略递归终止条件不正确调试方法打印关键变量值使用小规模测试用例画图辅助理解特别是树和图问题4.4 面试实战技巧先明确问题要求确认输入输出提出暴力解法分析时间复杂度思考优化方向逐步改进编写代码时注意变量命名和代码结构测试边缘案例解释代码逻辑5. hot100题目延伸学习5.1 相似题目推荐编辑距离扩展实现实际编辑操作序列矩阵置零扩展处理稀疏矩阵存储颜色分类扩展处理更多颜色分类最大矩形扩展处理三维情况下的最大立方体5.2 进阶学习资源《算法导论》深入理解算法原理LeetCode讨论区学习他人优秀解法算法可视化网站直观理解算法执行过程在线判题系统大量练习提升熟练度5.3 算法竞赛与面试区别面试更注重代码可读性和沟通能力竞赛追求极致性能面试更看重正确性面试常考经典算法竞赛常有创新题型面试需要解释思路竞赛只需通过测试用例在实际刷题过程中我发现hot100的71-80这组题目特别考验对多种算法技巧的综合运用能力。比如编辑距离需要深入理解动态规划而颜色分类则需要巧妙运用双指针技巧。建议每做完一道题后花时间总结这类问题的通用解法模式这样在遇到类似问题时能够快速识别并应用相应解法。