描述

题目描述

我们有由底至上为从大到小放置的 n 个圆盘，和三个柱子（分别为左/中/右即left/mid/right），开始时所有圆盘都放在左边的柱子上，按照汉诺塔游戏的要求我们要把所有的圆盘都移到右边的柱子上，要求一次只能移动一个圆盘，而且大的圆盘不可以放到小的上面。 请实现一个函数打印最优移动轨迹。

给定一个 int n ，表示有 n 个圆盘。请返回一个 string 数组，其中的元素依次为每次移动的描述。描述格式为： move from [left/mid/right] to [left/mid/right]。

要求：时间复杂度 O(3^n)， 空间复杂度 O(3^n)

示例
输入：2
返回值：
["move from left to mid","move from left to right","move from mid to right"]

知识点：递归，汉诺塔 难度：⭐⭐⭐

题解

方法一：递归

解题思路：

image-20211013092843391

可以通过定义函数：Hanoi(int n, String left, String mid, String right, List<String> res)，其递归功能为：圆盘从left到right，打印其move过程，即通过在递归过程中不断修改 left 和 right 参数，满足移动的规则

算法流程：

  • 定义并明确递归函数功能：圆盘从left到right，打印其move过程

  • 递归终止条件：递归到 left 最下面的圆盘，不进行处理，结束递归

  • 1、对于第2个到第n个圆盘，先借助right，在满足规则的情况下，将圆盘移动到mid

  • 2、对于left最下面圆盘，直接从left到right

  • 3、对于第2个到第n个圆盘，借助mid，将圆盘根据规则移动到right

Java 版本代码如下：
import java.util.*;

public class Solution {
    public ArrayList<String> getSolution(int n) {
        // write code here
        ArrayList<String> res = new ArrayList<>();
        Hanoi(n, "left", "mid", "right", res);
        return res;
    }

     // 递归函数功能：圆盘从left到right，打印其move过程
    public void Hanoi(int n, String left, String mid, String right, List<String> res) {
        // 递归终止条件: 递归到left最下面的圆盘，不进行处理，结束递归
        if(n == 0) {
            return;
        }
        // 1、对于第2个到第n个圆盘，先借助right，在满足规则的情况下，将圆盘移动到mid
        Hanoi(n - 1, left, right, mid, res);
        // 2、对于left最下面圆盘，直接从left到right
        // 根据设定的参数进行打印
        res.add("move from " + left + " to " + right);
        // 3、对于第2个到第n个圆盘，借助mid，将圆盘根据规则移动到right
        Hanoi(n - 1, mid, left, right, res);
    }
}
复杂度分析：

时间复杂度 O(2n)O(2^n)：递归次数为2^n, 递归计算时间为O(1)，总的为O(2^n)，n为圆盘个数

空间复杂度 O(n)O(n)：栈需要的递归深度

总结：

一定要明确递归函数功能并且不怀疑其功能

方法二：非递归

解题思路：

1、以 n = 3 为例，从当前柱子A开始，从 A 将顶部的最小盘子移动到顺时针下一个柱子C

image-20211025104745641

2、将当前柱子A与另一根柱子B比较圆盘长度，如果柱子 B 没有圆盘或B的顶部圆盘大于A的顶部圆盘，则将A的顶部圆盘移动到B，随后顺时针地将当前指针指向下一个柱子，即柱子B

image-20211025104759646

3、同样地，当前柱子C与顺时针下一个柱子进行圆盘比较，满足汉诺塔规则，将圆盘移动到柱子B，再与另一根柱子A比较，因为每次都要移动，而柱子C没有圆盘，则将柱子A的圆盘移动到柱子C，随后cur指针顺时针指向柱子B，如图:

image-20211025105205382

4、同样地，柱子B与柱子A和C分别进行比较，移动后如图，随后指针顺时针旋转到柱子A

image-20211025105356929

5、最后，柱子A顺时针比较柱子C，满足汉诺塔规则，移动到柱子C，此时发现有柱子C满了，则直接返回结果

image-20211025105554828

C++ 版本代码如下：

class Solution {
    public:
    vector<string> solution;
    typedef struct
    {
        string name;
        vector<int> stack;
    }stack;

    void initStack(stack &a, stack &b, stack &c, int n)
    {
        for (int i = n; i >= 1; -- i){
            a.stack.push_back(i);
        }
        a.name = "left";
        // 当n为奇数时，顺时针的柱子顺序为left,mid,right
        if (n % 2 == 1){
            b.name = "right";
            c.name = "mid";
        }
        // 当n为偶数时，顺时针的柱子顺序为left,right,mid
        else{
            b.name = "mid";
            c.name = "right";
        }
    }

    void move(stack &a, stack &b)
    {
        // 将a中的栈顶元素移入b中
        solution.push_back("move from " + a.name + " to "+b.name);
        b.stack.push_back(a.stack.back());
        a.stack.pop_back();
    }

    // 算法的第二步就是对于输入的两个栈，将其中一个栈的栈顶元素移到另一个栈中
    void moveOneToOne(stack &a, stack &b)
    {
        // 哪个柱子没有圆盘，则直接移动圆盘
        if (a.stack.empty()){
            move(b, a);
        }else if (b.stack.empty()){
            move(a, b);
        }
        // 实现汉诺塔规则
        // a的栈顶元素如果大于b的，自然只能把b的元素移到a中，否则a的圆盘移动到B的圆盘
        else if (a.stack.back() > b.stack.back()){
            move(b, a);
        }
        else{
            move(a, b);
        }
    }

    // 若有一根柱子满了，则循环结束
    bool isEnd(stack &b, stack &c, int n)
    {
        if (b.stack.size() == n || c.stack.size() == n){
            return true;
        }
        else{
            return false;
        }
    }

    void hanoi(int n, stack &A, stack &B, stack &C)
    {
        // 实现指针顺时针旋转指向
        for (int i = 0;!isEnd(B, C, n); ++ i){
            if (i % 3 == 0){
                move(A, B);
                if (isEnd(B, C, n)){
                    break;
                }
                moveOneToOne(A, C);
            }
            else if (i % 3 == 1)
            {
                move(B, C);
                if (isEnd(B, C, n)){
                    break;
                }
                moveOneToOne(B, A);
            }
            else{
                move(C, A);
                if (isEnd(B, C, n)){
                    break;
                }
                moveOneToOne(C, B);
            }
        }
    }


    vector<string> getSolution(int n) {
        stack A,B,C;
        // 初始化
        initStack(A, B, C, n);
        hanoi(n, A, B, C);
        return solution;
    }
};
复杂度分析：

时间复杂度 O(2N)O(2^N)：总的圆盘移动次数的时间复杂度为 O(2^N)

空间复杂度 O(N)O(N)：需要借助长度为N的栈