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 = 0
- a ^ 0 = a 因此所有成对出现的数字都会相互抵消，最后剩下的就是唯一数字。
7. 解题技巧总结
7.1 高频考点速查表
| 题型 | 核心技巧 | 相关题目 |
|---|---|---|
| 动态规划 | 状态定义、转移方程、边界条件 | 53, 62, 64, 70 |
| 二叉树 | 递归/迭代遍历、路径问题 | 94, 101, 104 |
| 回溯 | 选择列表、路径记录、剪枝 | 39, 46 |
| 双指针 | 快慢指针、左右指针 | 75 |
| 位运算 | 异或特性、掩码操作 | 136 |
7.2 面试准备建议
- 每个题型至少掌握3道经典题目
- 重点理解算法背后的思想而非死记硬背
- 白板编程时先理清思路再写代码
- 注意边界条件和特殊测试用例
在实际面试中，面试官更看重解题思路的清晰度和沟通能力。我建议在练习时养成边写代码边解释的习惯，这样在真实面试场景中会更加从容。
