面试题 08.06. 汉诺塔问题

在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制: (1) 每次只能移动一个盘子; (2) 盘子只能从柱子顶端滑出移到下一根柱子; (3) 盘子只能叠在比它大的盘子上。

请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。

你需要原地修改栈。

示例1:

输入：A = [2, 1, 0], B = [], C = [] 输出：C = [2, 1, 0] 示例2:

输入：A = [1, 0], B = [], C = [] 输出：C = [1, 0] 提示:

A中盘子的数目不大于14个。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/hanota-lcci 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

传说

​ 汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘

​ 僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽……

题解：

汉诺塔是递归的经典问题，而解决递归问题，递归的步骤：

  • 想清楚递归函数的作用
    • 先不要去思考代码怎么写，先搞清楚函数是干嘛用的，能完成什么功能？
  • 明确原问题和子问题的关系
    • 寻找 f(n) 和 f(n - 1) 的关系
  • 明确边界条件(递归基)
    • 递归的过程中，子问题的规模不断减小，当小到一定程度时可以直接得出他们的解
    • 寻找递归基，相当于思考：问题规模小到什么程度可以直接得出解

比如经典的汉诺塔问题

  • 只需要思考怎么把A的全部移动到C
    • 把A的上面n-1个移动道B
    • 再把A最下面的一个移动到C
    • 再把B的所有移动到C
  • 至于怎么把A的上面 n-1个 移动到B，和怎么把B的所有移动到C，不要去想，交给递归函数去解决吧。
    • 本题中 move函数，作用就是 把 N 个盘子从A移动到C
    • 所以解题步骤为：
      • 把A 除底层以外的 n-1个盘子，从A移动到B
      • 把A 最底层的 n 移动到C
      • 把B 的 n-1个盘子 移动到 C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

 public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {

        move(A.size(), A, B, C);
    }

    public void move(int n, List<Integer> A, List<Integer> B, List<Integer> C){

        if (n <= 1) {
            // 只有一个时，把A 移动到 C即可
            C.add(A.remove(A.size() - 1));
            return;
        }

        // 把 A底层以外挪动到n-1 B
        move(n-1, A, C, B);

        // 把 A的最底层n 挪动到 C
        C.add(A.remove(A.size() - 1));

        // 把 B 挪动到 C
        move(n-1, B, A, C);
    }

复杂度分析 ：

时间复杂度 : O(2 ^ N)

空间复杂度 : O(N)