数据结构与算法 / 系统课时
用小样例手动走完整算法
用小样例手动走完整算法
代码写得快并不代表边界一定正确。编码前先挑一个足够小、但能触发关键分支的样例,把指针、状态和判断条件逐轮写出来,可以在几分钟内暴露循环边界、更新顺序和终止条件的问题。
学习目标
- 选择能覆盖关键分支的最小样例
- 用状态表逐轮验证循环边界与更新顺序
- 把手动推演结果与实际程序输出进行对照
先选能暴露错误的小样例
手动模拟不是随便找一组输入。样例应当足够小,让你能完整走完算法,同时至少触发一次状态更新和一次关键判断。以二分查找 [1, 3, 5, 7] 中的 5 为例,两轮循环就能检查中点计算、左右边界更新和命中后的终止行为。
如果只拿目标恰好位于第一次中点的位置测试,很多错误分支根本不会执行。更稳妥的做法是先问自己:这个样例能不能迫使算法至少走一次我最担心的分支?
把每一轮状态写出来
假设采用闭区间 [left, right],初始状态为 left = 0、right = 3。每轮只记录会影响下一轮的状态:
| 轮次 | left | right | mid | nums[mid] | 动作 |
|---|---|---|---|---|---|
| 1 | 0 | 3 | 1 | 3 | 3 < 5,令 left = mid + 1 |
| 2 | 2 | 3 | 2 | 5 | 命中,立即结束 |
这张表能直接检查三个问题:循环条件是否允许检查最后一个元素;排除 mid 后是否使用 mid + 1 或 mid - 1;命中后是否真的停止。若你的代码状态变化与表格不同,就应该先修正模板,而不是继续补更多测试数据。
用程序复现手动过程
下面把每轮状态打印出来,让程序执行轨迹与手工表格一一对应。
python
def binary_search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
print(f'left={left}, right={right}, mid={mid}, value={nums[mid]}')
if nums[mid] == target:
return mid
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
nums = [1, 3, 5, 7]
index = binary_search(nums, 5)
print(f'index={index}')预期输出
text
left=0, right=3, mid=1, value=3
left=2, right=3, mid=2, value=5
index=2输出与手动状态表一致,说明这条执行路径上的边界、更新顺序和终止条件彼此匹配。实际面试中不需要把整张表写得很正式,只要在纸上或脑中维护关键状态即可。
优先推演最危险的地方
不同算法需要观察的状态不同。双指针重点看两个指针是否可能越界或错过答案;滑动窗口重点看扩张、统计、收缩的先后顺序;动态规划重点看当前状态依赖的数据是否已经计算完成;DFS 和回溯则要确认选择、递归与撤销操作是否成对出现。
当一个样例无法覆盖这些关键动作时,再补第二个针对性样例,而不是一开始就手算很大的输入。编码前的手动推演目标不是证明算法对所有输入都正确,而是尽早发现模板中的结构性错误。
按自己的节奏,确认真正理解。