递归-面试题08.06.汉诺塔问题-力扣(LeetCode)

白天的黑夜

发布于 2025-10-22 17:33:05

1530

文章被收录于专栏：leetcode题目解析和知识分享leetcode题目解析和知识分享

个人主页

专栏：力扣刷题录_1白天的黑夜1的博客-CSDN博客、企鹅程序员：Linux 系统与网络编程_1白天的黑夜1的博客-CSDN博客

一、题目解析

1、每次只能移动一个盘子

2、盘子只能从柱子顶端滑出移到下一根柱子

3、盘子只能叠在比它大的盘子上

4、不能额外开空间，也就是空间复杂要求O(1)

二、算法原理

解法：递归

我们通过分析可以发现，在解决大问题的过程中，我们发现了相同类型的子问题，在解决子问题的过程中，我们又发现了相同类型的子问题

如何编写递归代码？

1、通过重复的子问题，我们可以设置递归函数的函数头

2、在解决问题的过程中，我们只关心每一个子问题在做什么，这样来设计我们递归函数的函数

3、函数的出口

如果感觉还是有点懵懵的，可以去跟着画一画挪动的过程图，体会一下是否有相似的子问题，题目链接放在下面了

三、代码示例

四、递归展开图

看到最后，如果对您有所帮助，还请点赞、收藏和关注一键三连，在未来还会继续带来优秀的内容，感谢观看，我们下期再见！

一、题目解析

1、每次只能移动一个盘子

2、盘子只能从柱子顶端滑出移到下一根柱子

3、盘子只能叠在比它大的盘子上

4、不能额外开空间，也就是空间复杂要求O(1)

二、算法原理

解法：递归

相信大多数小伙伴对于递归，都是又爱又恨的，爱在只需短短几行代码，通过自己调用自己就能把问题解决了；恨的是对于递归是怎么写出来，对于递归的过程是一脸懵的。所以本个递归专题系列，旨在通过一篇篇博客，打消读者们对递归的恐惧、害怕等负面情绪，话不多说我们正式开始进入正题。

就此题我们来分析一下，盘子挪动的过程

当A柱子上只有一个盘子的时候，我们只需要将其直接放到C柱子上，就完成了题目的要求，我们接着往下看，当A上有两个盘子会怎么样呢？

可以看到，我们的目的是把最下面的那个大的盘子先放到C柱上，借助B柱子，我们可以轻松将盘子转移到C柱上，然后再将B柱子上的盘子拿过来，也是完成题目的要求，当A上有三个盘子该怎么操作呢？

仔细观察，我们能发现几个重要的关键点，1、在两个盘子和三个盘子的演示中，都有一个相同的动作，就是借助B柱子，把A柱子上最大的盘子先移动到C柱子上；2、当C柱子上最大的盘子移动到位了之后，此时需要第二大的盘子盖在C柱的盘子上，所以通过借助已空闲的A柱子，把B柱子上的最下面个盘子，移动到C上。为了验证我们发现是否正确，接下来用N个盘子演示一下

我们用...代替A柱上的除最下面盘子之外的所有盘子，我们的目的是把那个最大的盘子，移动到C柱子上，我们通过C柱子将n-1个盘子转移到B柱子上，此时把盘子从A柱子上，移动到C柱子上，我们的第一个目的达成了。对于B柱子上剩余的盘子，我们采取同样的操作，借助A柱子将剩余的n-1个盘子移动到A柱子上。所以可以看到我们在整个移动盘子的过程中会有三个重复的动作：1、将A柱子上的n-1个盘子，借助C柱子移动到B柱子上；2、将柱子上剩余的一个盘子移动到C柱子上；3、将B柱子上的n-1个盘子通过A住子，全部放到C柱子上

我们来总结一下，在分析时的发现：

我们通过分析可以发现，在解决大问题的过程中，我们发现了相同类型的子问题，在解决子问题的过程中，我们又发现了相同类型的子问题

这个重复的子问题将成为我们解决递归问题的关键

如何编写递归代码？

1、通过重复的子问题，我们可以设置递归函数的函数头

例如将A柱上的n-1个盘子借助C柱子，移动到B柱子上。我们需要一个返回类型为void的函数，需要四个参数，分别是A、B、C柱子和移动盘子的数量n，参考这段伪代码void f(A,B,C,int n)

2、在解决问题的过程中，我们只关心每一个子问题在做什么，这样来设计我们递归函数的函数

例如上面三个重复的动作：1、将A柱子上的n-1个盘子，借助C柱子移动到B柱子上；2、将柱子上剩余的一个盘子移动到C柱子上；3、将B柱子上的n-1个盘子通过A住子，全部放到C柱子上

先f(A,C,B,n-1)

再C.push_back(A.back()),A.pop()

最后f(B,A,C,n-1)

3、函数的出口

在移动盘子的过程中，当盘子为1个的时候，直接移动到C柱子上就可以了，所以当盘子的数目为1的时候直接将盘子从A柱子移动到C柱子上，返回即可

if(n == 1) ...

如果感觉还是有点懵懵的，可以去跟着画一画挪动的过程图，体会一下是否有相似的子问题，题目链接放在下面了

面试题 08.06. 汉诺塔问题 - 力扣（LeetCode）

三、代码示例

class Solution {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        hnt(A,B,C,A.size());
    }
    void hnt(vector<int>& A, vector<int>& B, vector<int>& C,int n)
    {
        //设置出口
        if(n == 1)
        {
            C.push_back(A.back());
            A.pop_back();
            return;
        }
        //将a柱子上的n-1个盘子，借助c柱，挪到b柱上
        hnt(A,C,B,n-1);
        //将a柱上剩余的最后一个盘子放到c柱上
        C.push_back(A.back());
        A.pop_back();
        //将b柱上的n-1个盘子，借助a柱放到c柱上
        hnt(B,A,C,n-1);
    }
};