LeetCode 08.06 面试题 汉诺塔 （Java）

经典递归解决汉诺塔问题：清晰的三步移动策略

问题描述

在汉诺塔问题中，有 3 根柱子和 N 个大小不同的盘子，盘子初始按升序堆叠在第一根柱子上（最小的在顶部）。目标是将所有盘子移动到第三根柱子上，并满足以下规则：

1. 每次只能移动一个盘子
2. 盘子只能从柱子的顶端移出
3. 盘子只能叠放在比它大的盘子上

递归思路

汉诺塔问题的核心思想是将问题分解为三个步骤（假设有 n 个盘子）：

1. 移动上层 n-1 个盘子：将前 n-1 个盘子从源柱 A 借助目标柱 C 移动到辅助柱 B
2. 移动底层最大盘子：将剩余的最后一个盘子（最大的）从 A 直接移动到目标柱 C
3. 移动 n-1 个盘子归位：将 B 上的 n-1 个盘子借助 A 移动到目标柱 C

通过递归重复这三个步骤，最终完成所有盘子的移动。递归终止条件是当盘子数量为 0 时直接返回。

代码实现（带详细注释）

class Solution {
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        move(A.size(), A, B, C); // 启动递归过程
        print(C);	//打印结果
    }

    /**
     * 递归移动盘子
     * @param n 要移动的盘子数量
     * @param a 源柱（起始柱）
     * @param b 辅助柱（借助柱）
     * @param c 目标柱（目标柱）
     */
    public static void move(int n, List<Integer> a, List<Integer> b, List<Integer> c) {
        // 递归终止条件：没有盘子可移动时返回
        if (n == 0) {
            return;
        }

        // 1. 将 a 上方的 n-1 个盘子借助 c 移动到 b
        move(n - 1, a, c, b);

        // 2. 将 a 底部最后一个盘子（当前最大）移动到 c
        c.add(a.remove(a.size() - 1));

        // 3. 将 b 上的 n-1 个盘子借助 a 移动到 c
        move(n - 1, b, a, c);
    }

    /**
     * 打印目标柱子
     * @param list
     */
    public static void print(List<Integer> list){
        System.out.println(list);
    }

}

关键点解析

1. 递归分解：
   • 每次递归将问题拆解为更小规模的子问题（n-1 个盘子）
   • 通过三次递归调用实现三层移动逻辑
2. 柱子角色转换：
   • 第一步中：目标柱 C 充当辅助柱，辅助柱 B 充当目标柱
   • 第三步中：源柱 A 充当辅助柱，辅助柱 B 充当源柱
3. 栈操作：
   • 使用 list.remove(list.size()-1) 移除栈顶元素（时间复杂度 O(1)）
   • 使用 list.add() 将元素放入目标柱顶部

复杂度分析

• 时间复杂度：$O(2^n)$
  每次递归产生两个子调用，移动 n 个盘子需要 $2^n-1$ 次操作
• 空间复杂度：$O(n)$
  递归调用栈的最大深度为 n（盘子数量）

示例解析

以输入 A = [1, 0] 为例（列表尾部表示柱顶）：

1. 第一步：移动上层盘子 0 从 A 到 B
   • 操作后：A=[1], B=[0], C=[]
2. 第二步：移动底层盘子 1 从 A 到 C
   • 操作后：A=[], B=[0], C=[1]
3. 第三步：移动 B 上的 0 到 C
   • 操作后：A=[], B=[], C=[1, 0]

最终 C=[1, 0] 符合要求（1 在底部，0 在顶部）。

注意：列表中的顺序 [1, 0] 表示柱子上 1 在底部、0 在顶部，满足小盘在大盘之上的规则。该解法直接修改原列表，符合原地操作要求。