1. Hot100算法题解析71-80题作为一名在算法领域摸爬滚打多年的老码农我深知LeetCode Hot100题库在面试准备中的重要性。这个系列收录了各大厂最高频的算法考题今天我们就来深度拆解第71-80题这些题目覆盖了二叉树、动态规划、回溯算法等核心考点。2. 题目分类与核心考点2.1 题目类型分布这10道题中二叉树相关3题包括遍历、路径和等问题动态规划4题涉及字符串处理、股票买卖等经典模型回溯算法2题排列组合问题其他1题位运算2.2 重点题目解析以第75题颜色分类为例这是道经典的荷兰国旗问题。要求原地对包含红、白、蓝三种颜色的数组进行排序时间复杂度必须控制在O(n)。def sortColors(nums): p0 curr 0 p2 len(nums) - 1 while curr p2: if nums[curr] 0: nums[p0], nums[curr] nums[curr], nums[p0] p0 1 curr 1 elif nums[curr] 2: nums[curr], nums[p2] nums[p2], nums[curr] p2 - 1 else: curr 1这个解法使用了三指针技巧p0指向0的最右边界p2指向2的最左边界curr用于遍历数组注意边界条件当curr与p2交换后curr不能立即前进因为交换过来的元素可能是0或1需要再次判断3. 动态规划专题精讲3.1 股票买卖问题第121题这是动态规划的经典案例要求计算一次买卖的最大利润。关键在于找出历史最低点然后在每个价格计算可能的最大利润。def maxProfit(prices): min_price float(inf) max_profit 0 for price in prices: min_price min(min_price, price) max_profit max(max_profit, price - min_price) return max_profit时间复杂度O(n)空间复杂度O(1)。这个解法展示了动态规划中状态压缩的技巧将原本需要O(n)空间的DP数组优化为O(1)空间。3.2 最大子序和第53题Kadane算法的典型应用要求找到具有最大和的连续子数组def maxSubArray(nums): curr_sum max_sum nums[0] for num in nums[1:]: curr_sum max(num, curr_sum num) max_sum max(max_sum, curr_sum) return max_sum这个算法背后的DP思想是当前最大子序和要么是当前元素本身要么是当前元素加上之前的最大子序和。4. 二叉树高频考题4.1 二叉树的中序遍历第94题虽然题目简单但要求使用迭代而非递归实现考察对栈的理解def inorderTraversal(root): res [] stack [] curr root while curr or stack: while curr: stack.append(curr) curr curr.left curr stack.pop() res.append(curr.val) curr curr.right return res这个解法模拟了递归的调用栈时间复杂度O(n)空间复杂度O(n)。4.2 路径总和III第437题要求找出二叉树中路径和等于目标值的路径数量路径不需要从根节点开始def pathSum(root, targetSum): from collections import defaultdict prefix defaultdict(int) prefix[0] 1 def dfs(node, curr): if not node: return 0 curr node.val res prefix[curr - targetSum] prefix[curr] 1 res dfs(node.left, curr) res dfs(node.node.right, curr) prefix[curr] - 1 return res return dfs(root, 0)这个解法使用了前缀和哈希表的技巧将时间复杂度优化到O(n)是二叉树与哈希表结合的典型案例。5. 回溯算法实战5.1 全排列第46题经典回溯问题要求生成数组的所有可能排列def permute(nums): res [] def backtrack(path, used): if len(path) len(nums): res.append(path.copy()) return for i in range(len(nums)): if not used[i]: used[i] True path.append(nums[i]) backtrack(path, used) path.pop() used[i] False backtrack([], [False]*len(nums)) return res回溯算法的三个关键点选择列表当前可选的元素路径已经做出的选择结束条件达到决策树的底层5.2 组合总和第39题找出所有可以使数字和为目标数的组合数字可以重复使用def combinationSum(candidates, target): res [] def backtrack(start, path, target): if target 0: res.append(path.copy()) return for i in range(start, len(candidates)): if candidates[i] target: continue path.append(candidates[i]) backtrack(i, path, target - candidates[i]) path.pop() backtrack(0, [], target) return res这个解法通过控制start参数避免生成重复组合是回溯剪枝的典型应用。6. 位运算妙用6.1 只出现一次的数字第136题要求找出数组中唯一不重复的元素其他元素都出现两次def singleNumber(nums): res 0 for num in nums: res ^ num return res这个解法利用了异或运算的两个性质a ^ a 0a ^ 0 a 因此所有成对出现的数字都会相互抵消最后剩下的就是唯一数字。7. 解题技巧总结7.1 高频考点速查表题型核心技巧相关题目动态规划状态定义、转移方程、边界条件53, 62, 64, 70二叉树递归/迭代遍历、路径问题94, 101, 104回溯选择列表、路径记录、剪枝39, 46双指针快慢指针、左右指针75位运算异或特性、掩码操作1367.2 面试准备建议每个题型至少掌握3道经典题目重点理解算法背后的思想而非死记硬背白板编程时先理清思路再写代码注意边界条件和特殊测试用例在实际面试中面试官更看重解题思路的清晰度和沟通能力。我建议在练习时养成边写代码边解释的习惯这样在真实面试场景中会更加从容。 
长河君 · 2026/11/3 11:38:42 · 阅读 1.2k LeetCode Hot100算法精解：二叉树与动态规划实战
1. Hot100算法题解析71-80题作为一名在算法领域摸爬滚打多年的老码农我深知LeetCode Hot100题库在面试准备中的重要性。这个系列收录了各大厂最高频的算法考题今天我们就来深度拆解第71-80题这些题目覆盖了二叉树、动态规划、回溯算法等核心考点。2. 题目分类与核心考点2.1 题目类型分布这10道题中二叉树相关3题包括遍历、路径和等问题动态规划4题涉及字符串处理、股票买卖等经典模型回溯算法2题排列组合问题其他1题位运算2.2 重点题目解析以第75题颜色分类为例这是道经典的荷兰国旗问题。要求原地对包含红、白、蓝三种颜色的数组进行排序时间复杂度必须控制在O(n)。def sortColors(nums): p0 curr 0 p2 len(nums) - 1 while curr p2: if nums[curr] 0: nums[p0], nums[curr] nums[curr], nums[p0] p0 1 curr 1 elif nums[curr] 2: nums[curr], nums[p2] nums[p2], nums[curr] p2 - 1 else: curr 1这个解法使用了三指针技巧p0指向0的最右边界p2指向2的最左边界curr用于遍历数组注意边界条件当curr与p2交换后curr不能立即前进因为交换过来的元素可能是0或1需要再次判断3. 动态规划专题精讲3.1 股票买卖问题第121题这是动态规划的经典案例要求计算一次买卖的最大利润。关键在于找出历史最低点然后在每个价格计算可能的最大利润。def maxProfit(prices): min_price float(inf) max_profit 0 for price in prices: min_price min(min_price, price) max_profit max(max_profit, price - min_price) return max_profit时间复杂度O(n)空间复杂度O(1)。这个解法展示了动态规划中状态压缩的技巧将原本需要O(n)空间的DP数组优化为O(1)空间。3.2 最大子序和第53题Kadane算法的典型应用要求找到具有最大和的连续子数组def maxSubArray(nums): curr_sum max_sum nums[0] for num in nums[1:]: curr_sum max(num, curr_sum num) max_sum max(max_sum, curr_sum) return max_sum这个算法背后的DP思想是当前最大子序和要么是当前元素本身要么是当前元素加上之前的最大子序和。4. 二叉树高频考题4.1 二叉树的中序遍历第94题虽然题目简单但要求使用迭代而非递归实现考察对栈的理解def inorderTraversal(root): res [] stack [] curr root while curr or stack: while curr: stack.append(curr) curr curr.left curr stack.pop() res.append(curr.val) curr curr.right return res这个解法模拟了递归的调用栈时间复杂度O(n)空间复杂度O(n)。4.2 路径总和III第437题要求找出二叉树中路径和等于目标值的路径数量路径不需要从根节点开始def pathSum(root, targetSum): from collections import defaultdict prefix defaultdict(int) prefix[0] 1 def dfs(node, curr): if not node: return 0 curr node.val res prefix[curr - targetSum] prefix[curr] 1 res dfs(node.left, curr) res dfs(node.node.right, curr) prefix[curr] - 1 return res return dfs(root, 0)这个解法使用了前缀和哈希表的技巧将时间复杂度优化到O(n)是二叉树与哈希表结合的典型案例。5. 回溯算法实战5.1 全排列第46题经典回溯问题要求生成数组的所有可能排列def permute(nums): res [] def backtrack(path, used): if len(path) len(nums): res.append(path.copy()) return for i in range(len(nums)): if not used[i]: used[i] True path.append(nums[i]) backtrack(path, used) path.pop() used[i] False backtrack([], [False]*len(nums)) return res回溯算法的三个关键点选择列表当前可选的元素路径已经做出的选择结束条件达到决策树的底层5.2 组合总和第39题找出所有可以使数字和为目标数的组合数字可以重复使用def combinationSum(candidates, target): res [] def backtrack(start, path, target): if target 0: res.append(path.copy()) return for i in range(start, len(candidates)): if candidates[i] target: continue path.append(candidates[i]) backtrack(i, path, target - candidates[i]) path.pop() backtrack(0, [], target) return res这个解法通过控制start参数避免生成重复组合是回溯剪枝的典型应用。6. 位运算妙用6.1 只出现一次的数字第136题要求找出数组中唯一不重复的元素其他元素都出现两次def singleNumber(nums): res 0 for num in nums: res ^ num return res这个解法利用了异或运算的两个性质a ^ a 0a ^ 0 a 因此所有成对出现的数字都会相互抵消最后剩下的就是唯一数字。7. 解题技巧总结7.1 高频考点速查表题型核心技巧相关题目动态规划状态定义、转移方程、边界条件53, 62, 64, 70二叉树递归/迭代遍历、路径问题94, 101, 104回溯选择列表、路径记录、剪枝39, 46双指针快慢指针、左右指针75位运算异或特性、掩码操作1367.2 面试准备建议每个题型至少掌握3道经典题目重点理解算法背后的思想而非死记硬背白板编程时先理清思路再写代码注意边界条件和特殊测试用例在实际面试中面试官更看重解题思路的清晰度和沟通能力。我建议在练习时养成边写代码边解释的习惯这样在真实面试场景中会更加从容。