1. 算法刷题日课八道经典题目精解今天要啃的八道算法题涵盖了动态规划、双指针、二分查找等核心解题技巧。作为过来人我特别理解初学算法时看到这些名词的茫然感——就像第一次走进五金店面对满墙专业工具不知从何下手。但别担心我会用修水管、找钥匙这些生活场景帮你理解每个算法的精髓。2. 动态规划专题打家劫舍问题剖析2.1 问题场景还原想象你是个专业小偷当然只是假设要在一排房子里选择偷窃目标。规则很简单不能偷相邻的两家否则会触发警报。我们需要设计算法计算最大收益。2.2 DP状态定义技巧定义dp[i]为偷到第i家时的最大收益。这里有个关键点对于第i家我们有两种选择偷这家收益 nums[i] dp[i-2]不偷这家收益 dp[i-1]状态转移方程dp[i] max(dp[i-1], nums[i] dp[i-2])2.3 空间优化实战实际编码时不需要维护整个dp数组只需保存前两个状态prev_max 0 # dp[i-2] curr_max 0 # dp[i-1] for num in nums: temp curr_max curr_max max(curr_max, prev_max num) prev_max temp return curr_max避坑指南初始化时prev_max和curr_max都设为0处理空数组情况更安全3. 双指针算法深度应用3.1 快慢指针解环形链表就像两个人在操场跑步快指针每次走两步慢指针每次走一步。如果存在环快指针最终会追上慢指针。slow fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return False3.2 对撞指针解两数之和将数组排序后用左右指针从两端向中间逼近left, right 0, len(nums)-1 while left right: s nums[left] nums[right] if s target: return [left1, right1] elif s target: left 1 else: right - 14. 二分查找的变体实战4.1 旋转数组搜索当数组被旋转后二分时需要先判断哪半边是有序的left, right 0, len(nums)-1 while left right: mid (left right) // 2 if nums[mid] target: return mid # 左半部分有序 if nums[left] nums[mid]: if nums[left] target nums[mid]: right mid - 1 else: left mid 1 else: if nums[mid] target nums[right]: left mid 1 else: right mid - 14.2 寻找峰值元素利用二分特性快速定位峰值left, right 0, len(nums)-1 while left right: mid (left right) // 2 if nums[mid] nums[mid1]: right mid else: left mid 1 return left5. 滑动窗口技巧精讲5.1 最小覆盖子串用哈希表记录字符需求滑动窗口动态调整from collections import defaultdict need defaultdict(int) for c in t: need[c] 1 left 0 missing len(t) res for right, c in enumerate(s): if need[c] 0: missing - 1 need[c] - 1 while missing 0: if not res or right-left1 len(res): res s[left:right1] if need[s[left]] 0: missing 1 need[s[left]] 1 left 1 return res5.2 最长无重复子串维护字符最后出现位置的字典last_pos {} start max_len 0 for end, c in enumerate(s): if c in last_pos and last_pos[c] start: start last_pos[c] 1 last_pos[c] end max_len max(max_len, end - start 1) return max_len6. 方向控制问题解析6.1 螺旋矩阵生成模拟转圈过程注意边界收缩directions [(0,1),(1,0),(0,-1),(-1,0)] dir_idx 0 row col 0 res [[0]*n for _ in range(n)] for num in range(1, n*n1): res[row][col] num next_row row directions[dir_idx][0] next_col col directions[dir_idx][1] if not (0next_rown and 0next_coln and res[next_row][next_col]0): dir_idx (dir_idx 1) % 4 row directions[dir_idx][0] col directions[dir_idx][1] return res7. 前缀和技巧实战7.1 区域和检索预处理前缀和数组self.prefix [0] for num in nums: self.prefix.append(self.prefix[-1] num) def sumRange(self, left: int, right: int) - int: return self.prefix[right1] - self.prefix[left]7.2 和为K的子数组利用哈希表记录前缀和出现次数from collections import defaultdict prefix_sum defaultdict(int) prefix_sum[0] 1 curr_sum 0 count 0 for num in nums: curr_sum num count prefix_sum.get(curr_sum - k, 0) prefix_sum[curr_sum] 1 return count8. 算法实战经验总结刷题时我习惯用三种颜色的标记笔红色标注边界条件空输入、极端值等蓝色标记算法核心逻辑绿色标出可以复用的代码模板对于DP问题建议先在纸上画出状态转移图。就像玩数独先填确定性的格子再推导关联位置。遇到二分查找时要特别注意循环终止条件和中间值计算方式——我曾经因为使用(left right) // 2导致整数溢出改用left (right - left) // 2后才解决问题。