LeetCode 面试题 08.06. 汉诺塔问题

约 4 分钟
文章信息 12 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 10-20 程序员面试金典（第 6 版） 腾讯 字节 华为 微软 美团 快手
标签
数组 递归

题目描述

✅ 面试题 08.06. 汉诺塔问题

image-20260928224957066

题意分析

将 A 上的全部盘子借助 B 搬到 C。每次只能移动柱顶的一个盘子，而且只能放到空柱或更大的盘子上。列表末尾表示柱顶；Java 修改传入列表，Go 入口返回最终的 C 切片。

解法：经典递归移动

核心思路

[!blue]

要移动当前的最大盘，必须先移走它上面的 $n-1$ 个小盘；这些小盘也不能留在目标柱，否则最大盘无法放下。因此，先把小盘全部搬到辅助柱，再移动最大盘，最后把小盘搬到最大盘上。

定义 move(n, from, buffer, to) 为：借助 buffer，将 from 顶部的 $n$ 个盘子按原有大小顺序搬到 to。于是第一步是 move(n - 1, from, to, buffer)，第三步是 move(n - 1, buffer, from, to)。柱子的角色随调用改变，不能固定把 A 当作源柱、B 当作辅助柱。

两次递归只处理更小的盘子，中间的大盘移动时已经露在源柱顶部，目标柱上也没有小盘挡住；大盘落下后又能合法承接所有小盘。以 n == 0 为结束条件，就能从空操作逐层推出整个过程合法。

解题步骤

  1. 入口调用 move(A.size(), A, B, C)。
  2. 当 n == 0 时返回，同时覆盖空输入。
  3. 递归把上方 $n-1$ 个盘子从源柱搬到辅助柱，原目标柱临时充当缓冲柱。
  4. 删除源列表末尾的盘子，并追加到目标列表末尾，完成当前最大盘的一次移动。
  5. 递归把辅助柱上的 $n-1$ 个盘子搬到目标柱。

代码实现

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)$。递归调用栈深度与盘子数成正比；Go 中各柱切片占用的存储也不超过这个量级。

关键点总结

[!green]

  • 每次递归都完成一次完整的搬运，调用者只需处理当前最大盘的一次移动。
  • 两次子问题都是规模 $n-1$，但源柱、辅助柱、目标柱的角色不同。
  • 使用列表尾部表示柱顶，搬动只操作尾部。
  • $2^n - 1$ 也是最少搬动次数：最大盘搬到目标前后，各至少要完成一次 $n-1$ 个小盘的搬运。题目至多 14 个盘子，可以直接执行这些移动。

易错点总结

[!yellow]

  • 第一趟误写为 move(n - 1, from, buffer, to)，会让小盘占住目标柱，最大盘无法合法落下。
  • 第三趟没有交换源柱和辅助柱，盘子会被搬回 A 而不是 C。
  • 从列表下标 0 删除元素会取走柱底的大盘；柱顶位于列表末尾。
  • 递归出口只判断 n == 1，空输入会持续递归到负数；使用 n == 0 更完整。
  • Go 中递归过程需要修改切片长度，因此传递切片头指针；只传 []int 值会让 append 和截断后的新切片头无法回写给上层。入口仍通过返回值交付最终的 C，调用方应接收它。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/32910729
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！