每日一题:LeetCode-202.面试题 08.06. 汉诺塔问题

简介: 每日一题:LeetCode-202.面试题 08.06. 汉诺塔问题

每日一题系列(day 07)

前言:

🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈

   🔎🔎如果说代码有灵魂,那么它的灵魂一定是👉👉算法👈👈,因此,想要写出💚优美的程序💚,核心算法是必不可少的,少年,你渴望力量吗😆😆,想掌握程序的灵魂吗❓❗️那么就必须踏上这样一条漫长的道路🏇🏇,我们要做的,就是斩妖除魔💥💥,打怪升级!💪💪当然切记不可😈走火入魔😈,每日打怪,日日累积,终能成圣🙏🙏!开启我们今天的斩妖之旅吧!✈️✈️


题目:

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

  • (1) 每次只能移动一个盘子;
  • (2) 盘子只能从柱子顶端滑出移到下一根柱子;
  • (3) 盘子只能叠在比它大的盘子上。
    请编写程序,用栈将所有盘子从第一根柱子移到最后一根柱子。
    你需要原地修改栈。

示例:

提示:

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

思路:

  汉诺塔问题是很多小伙伴第一次接触到的递归的题目,非常的经典,当然现在来看其实原理也很简单,我们只需要将大问题拆成子问题就可以了,这道题目的拆解还是比较简单的。

  1、我们可以先来写几个例子,当盘子只有一个的时候,我们只需要将盘子直接放到C柱子上即可。

  2、当盘子为两个的时,我们就需要将最上面的盘子先放在B柱上,再将A中剩下的那个最大的盘子放在C柱上,最后将B柱上的盘子再放到C柱上。

  3、当盘子为三个时,要先将A中最小的放到C上,再将A中第二小的放到B上,把C上的放回到B上,在把最大的A放到C上。其实这个过程中除了最大的盘子,最大盘子以上的盘子需要借助C柱来放到B柱上。

  4、以此类推,其实我们就可以把汉诺塔问题分为三个步骤,首先:我们需要将最大盘子以上的盘子全部放在B柱上,可能会借用到C盘,也可能不需要。其次:现在已经将最大的盘子空了出来,这个时候将这个最大的盘子放在C柱上。最后:我们需要将B柱上的所有盘子全部放在C盘上面。

  只有两个盘子的情况:

  n个盘子的情况:

  这里其实就是把两个以上的盘子看成两部分,一部分就是最大盘子以上,一部分就是最大盘子本身,你再细分,发现他们的工作原理都是相同的。也就是我们上面说的那三步。

  以及特殊情况:

代码实现:

class Solution {
public:
    void dfs(vector<int>& a, vector<int>& b, vector<int>& c, int n)
    {
        if(n == 1)//当n为1时,为特殊情况,直接将a中元素尾插到c,最后再pop(a)
        {
            c.push_back(a.back());
            a.pop_back();
            return;
        }
        dfs(a, c, b, n - 1);//不为1的情况,将a中最大盘子以外的盘子借助c柱全都放到b柱上
        c.push_back(a.back());//最后a柱只剩下那个最大的盘子,把这个盘子直接放在c柱上
        a.pop_back();
        dfs(b, a, c, n - 1);//最后再将之前b中的盘子借助a柱全都放在c盘上就完成了
    }
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        dfs(A, B, C, A.size());//其实这里就是一个深搜的过程,传入A数组里的大小
    }
};

  汉诺塔问题很经典,虽然不像二叉树那样直观的感受就是递归,这里就不得不说递归的本质了,其实就是将大问题拆分成小问题,在将小问题拆分成结构相同的小问题。这样就比较简单了,只需要解决好当前问题,控制好边界条件,子问题也就解决了。

相关文章
|
5月前
|
Python
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
|
5月前
|
存储 算法 索引
1124. 表现良好的最长时间段 (python) 前缀和 分类讨论 最大长度 力扣 面试题
1124. 表现良好的最长时间段 (python) 前缀和 分类讨论 最大长度 力扣 面试题
|
5月前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
6月前
|
存储 算法 数据挖掘
深入解析力扣168题:Excel表列名称(进制转换法详解及模拟面试问答)
深入解析力扣168题:Excel表列名称(进制转换法详解及模拟面试问答)
|
6月前
|
存储 算法 数据挖掘
深入解析力扣166题:分数到小数(模拟长除法与字符串操作详解及模拟面试问答)
深入解析力扣166题:分数到小数(模拟长除法与字符串操作详解及模拟面试问答)
|
6月前
|
SQL 算法 大数据
深入解析力扣176题:第二高的薪水(子查询与LIMIT详解及模拟面试问答)
深入解析力扣176题:第二高的薪水(子查询与LIMIT详解及模拟面试问答)
|
6月前
|
算法 数据挖掘 大数据
深入解析力扣172题:阶乘后的零(计算因子5的方法详解及模拟面试问答)
深入解析力扣172题:阶乘后的零(计算因子5的方法详解及模拟面试问答)
|
6月前
|
算法 数据挖掘 大数据
深入解析力扣171题:Excel表列序号(进制转换法详解及模拟面试问答)
深入解析力扣171题:Excel表列序号(进制转换法详解及模拟面试问答)
|
6月前
|
算法 数据挖掘 Java
深入解析力扣167题:两数之和 II(双指针法详解及模拟面试问答)
深入解析力扣167题:两数之和 II(双指针法详解及模拟面试问答)
|
6月前
|
存储 算法 数据挖掘
【模拟面试问答】力扣165题:比较版本号(逐个比较与双指针法详解及模拟面试问答)
【模拟面试问答】力扣165题:比较版本号(逐个比较与双指针法详解及模拟面试问答)