LeetCode 面试题 08.06. 汉诺塔问题
目录
题目描述
题意分析
给三根柱子 A、B、C，A 上自下而上放着若干大小递减的盘子，要把它们原样搬到 C 上。搬动规则有两条：每次只能拿走某根柱子最上面的一个盘子，并且任何时刻都不允许大盘压在小盘上面。函数没有返回值，而是要求直接修改传入的三个列表。
约束信号很直白：盘子最多 14 个。这说明题目根本不打算让你压缩搬动次数，即便次数随盘子数翻倍增长也完全跑得动，考的是能不能把搬动过程组织正确。
表示方式要先看清：列表末尾代表柱子顶部，也就是当前最小的盘子。所以「搬一个盘子」就等价于从一个列表尾部弹出、再压入另一个列表尾部，不需要额外的栈结构。
边界有两处：A 为空时三根柱子应保持原样，什么都不做；只有一个盘子时直接从 A 搬到 C，中间不经过 B。
解法：经典递归移动
核心思路
先固定递归契约：
move(n, from, buffer, to)表示借助buffer，把from顶部的 $n$ 个盘子合法地搬到to，且不改变三根柱子上更下方的盘子。要移动最大的第 $n$ 个盘子，必须先把上面的 $n-1$ 个盘子移到辅助柱；随后将最大盘移到目标柱；最后把那 $n-1$ 个盘子从辅助柱移到目标柱。因此递推结构固定为：
move(n - 1, from, to, buffer)；- 将
from栈顶移到to；move(n - 1, buffer, from, to)。正确性可用归纳法说明：$n=0$ 时无需操作；假设契约对 $n-1$ 成立，第一步会腾空最大盘上方，第二步搬最大盘必然合法，第三步再把小盘叠到它上面，于是契约对 $n$ 也成立。列表末尾表示柱顶，所以一次搬动就是从源列表尾部删除并追加到目标列表尾部。
解题步骤
- 入口调用
move(A.size(), A, B, C)。- 当
n == 0时返回，同时覆盖空输入。- 递归把上方 $n-1$ 个盘子从源柱搬到辅助柱，原目标柱临时充当缓冲柱。
- 把源柱顶部的最大盘搬到目标柱。
- 递归把辅助柱上的 $n-1$ 个盘子搬到目标柱。
例如
A = [2, 1, 0]，先把[1, 0]搬到 B，再把 2 搬到 C，最后把[1, 0]搬到 C，得到C = [2, 1, 0]。每次递归都遵守同一个契约，只是三根柱子的角色发生交换。
代码实现
import java.util.List;
class Solution {
public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
move(A.size(), A, B, C);
}
private void move(int n, List<Integer> from, List<Integer> buffer, List<Integer> to) {
if (n == 0) {
return;
}
move(n - 1, from, to, buffer);
to.add(from.remove(from.size() - 1));
move(n - 1, buffer, from, to);
}
}
func hanota(A []int, B []int, C []int) []int {
var move func(int, *[]int, *[]int, *[]int)
move = func(n int, from, buffer, to *[]int) {
if n == 0 {
return
}
move(n-1, from, to, buffer)
top := len(*from) - 1
*to = append(*to, (*from)[top])
*from = (*from)[:top]
move(n-1, buffer, from, to)
}
move(len(A), &A, &B, &C)
return C
}
复杂度分析
- 时间复杂度：$O(2^n)$。递推式为 $T(n) = 2T(n-1) + 1$，实际搬动次数恰好是 $2^n - 1$。
- 空间复杂度：$O(n)$。递归调用栈最大深度为 $n$；题目要求的目标列表不计入额外空间。
关键点总结
- 先说清
move的递归契约，再按“移走小盘、移动最大盘、移回小盘”展开，参数顺序才不容易错。- 两次子问题都是规模 $n-1$，但源柱、辅助柱、目标柱的角色不同。
- 使用列表尾部表示柱顶，搬动只操作尾部。
- $2^n - 1$ 不只是算法代价，也是最少搬动次数：最大盘前后各至少需要解决一次 $n-1$ 规模的问题。
易错点总结
- 第一趟误写为
move(n - 1, from, buffer, to)，会让小盘占住目标柱，最大盘无法合法落下。- 第三趟没有交换源柱和辅助柱，盘子会被搬回 A 而不是 C。
- 从列表下标 0 删除元素会取走柱底的大盘；柱顶位于列表末尾。
- 递归出口只判断
n == 1，空输入会持续递归到负数；使用n == 0更完整。- Go 中递归过程需要修改切片长度，因此传递切片头指针；只传
[]int值会让append和截断后的新切片头无法回写给上层。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 面试题 08.05. 递归乘法 | 中等 | 用递归拆解算术运算 |
| 面试题 08.04. 幂集 | 中等 | 递归枚举全部子集 |
| 面试题 08.01. 三步问题 | 简单 | 递推式方案计数 |
| 50. Pow(x, n) | 中等 | 折半递归求幂 |
| 509. 斐波那契数 | 简单 | 递归转迭代消除重叠 |