当前位置：首页 > news >正文

【软件设计师-从小白到大牛】下午题进阶篇：第四章算法策略实战与代码填空精解

news 2026/7/15 9:12:18

1. 算法策略实战精要

下午题中的算法策略就像工具箱里的不同工具，每种都有最适合的使用场景。我当年备考时最大的误区就是死记硬背模板，直到实际刷题才发现理解本质特征才是关键。举个例子，分治法和动态规划都涉及子问题分解，但前者像拆积木（独立求解），后者更像拼马赛克（子问题重叠需要查表）。

1.1 四大算法特征识别

分治法的典型标志是：

问题可以等分为独立子问题（如归并排序的左右半边）
递归式通常呈现T(n)=aT(n/b)+f(n)形式
代码中常见数组分段操作（begin/mid/end三件套）

# 经典二分查找模板 def binary_search(arr, left, right, target): if right >= left: mid = left + (right - left) // 2 if arr[mid] == target: return mid elif arr[mid] > target: return binary_search(arr, left, mid-1, target) # 左半段 else: return binary_search(arr, mid+1, right, target) # 右半段 return -1

动态规划的三大识别特征：

最优子结构（全局最优包含局部最优）
重叠子问题（递归树有重复计算节点）
状态转移方程（如斐波那契数列的dp[i]=dp[i-1]+dp[i-2]）

2. 代码填空破题技巧

2.1 递归边界条件定位

递归就像俄罗斯套娃，必须有个最小的娃娃作为终止条件。在代码填空中，递归出口通常出现在这三个位置：

数组/链表遍历结束时（指针==null或index>=length）
数值达到临界值时（如阶乘的n==1）
问题规模足够小时（如归并排序的区间长度<=1）

# 快速排序填空常见陷阱 def quick_sort(arr, low, high): if low < high: # 填空高频点1：递归继续条件 pivot = partition(arr, low, high) quick_sort(arr, low, pivot-1) # 填空高频点2：左子区间 quick_sort(arr, pivot+1, high) # 填空高频点3：右子区间

2.2 动态规划填表规律

DP类填空要特别注意：

初始化条件（通常dp[0]、dp[1]需要特殊处理）
状态转移方向（自底向上还是自顶向下）
返回值位置（可能是dp数组末尾或最大值）

比如背包问题中：

def knapsack(W, wt, val, n): dp = [[0]*(W+1) for _ in range(n+1)] for i in range(1, n+1): # 填空点1：物品循环 for w in range(1, W+1): # 填空点2：容量循环 if wt[i-1] <= w: dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], # 填空点3：状态转移 dp[i-1][w]) else: dp[i][w] = dp[i-1][w] # 填空点4：继承状态 return dp[n][W]

3. 贪心与回溯实战对比

3.1 贪心选择性质验证

贪心算法就像吃自助餐——每次拿最贵的食物。验证贪心选择性质需要证明：

局部最优能导致全局最优
无后效性（当前选择不影响后续选择）

典型错题：硬币找零问题（当硬币面值为[1,3,4]时，贪心法找6元会得到4+1+1而非最优解3+3）

3.2 回溯法的剪枝优化

回溯法就像走迷宫，遇到死路要回撤。代码填空中常见：

路径选择列表（for循环遍历选项）
终止条件（找到解或超出限制）
状态回退（撤销当前选择）

def backtrack(路径, 选择列表): if 满足结束条件: # 填空点1：终止条件 结果.append(路径) return for 选择 in 选择列表: if 剪枝条件: # 填空点2：可行性剪枝 continue 做选择 # 填空点3：状态标记 backtrack(路径, 选择列表) 撤销选择 # 填空点4：状态回退

4. 经典案例深度剖析

4.1 装箱问题双解法

问题描述：将n个物品装入容量为C的箱子，求最少箱子数。

贪心解法（近似解）：

def first_fit(items, C): bins = [0] # 初始化第一个箱子 for item in items: placed = False for i in range(len(bins)): if bins[i] + item <= C: # 填空点1：检查容量 bins[i] += item # 填空点2：放入物品 placed = True break if not placed: bins.append(item) # 填空点3：开新箱 return len(bins)

动态规划解法（精确解）：

def min_bins(items, C): n = len(items) dp = [float('inf')] * (n + 1) dp[0] = 0 for i in range(1, n+1): current_weight = 0 min_bins = float('inf') for j in range(i, 0, -1): current_weight += items[j-1] if current_weight > C: break min_bins = min(min_bins, dp[j-1] + 1) # 关键状态转移 dp[i] = min_bins return dp[n]

4.2 合并排序关键填空

归并排序是分治法的经典案例，填空常出现在：

递归终止条件（序列长度<=1）
合并时的临时数组操作
左右子序列的边界处理

def merge_sort(arr, left, right): if left < right: # 填空点1：递归继续条件 mid = (left + right) // 2 merge_sort(arr, left, mid) merge_sort(arr, mid+1, right) merge(arr, left, mid, right) def merge(arr, left, mid, right): temp = [0]*(right-left+1) i, j, k = left, mid+1, 0 while i <= mid and j <= right: # 填空点2：双指针移动 if arr[i] <= arr[j]: temp[k] = arr[i] i += 1 else: temp[k] = arr[j] # 填空点3：右半部元素放入 j += 1 k += 1 while i <= mid: # 填空点4：左剩余处理 temp[k] = arr[i] i += 1 k += 1 while j <= right: # 填空点5：右剩余处理 temp[k] = arr[j] j += 1 k += 1 for p in range(len(temp)): arr[left+p] = temp[p] # 填空点6：回写数组