Leetcode刷题详解——汉诺塔问题

这篇具有很好参考价值的文章主要介绍了Leetcode刷题详解——汉诺塔问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. 题目链接:面试题 08.06. 汉诺塔问题

2. 题目描述:

在经典汉诺塔问题中,有 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]

提示:

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

3. 解法(递归)

3.1 算法思路:

  1. 假设 n=1,只有一个盘子,直接把它从A拿出来,移动到C上

Leetcode刷题详解——汉诺塔问题,leetcode,深度优先,算法

  1. 如果n=2呢?这时候我们就要借助B了,因为小盘子必须时刻都在大盘子上面,共需要3步(为了方便叙述,记A中盘子从上到下为1号、2号:

Leetcode刷题详解——汉诺塔问题,leetcode,深度优先,算法

  1. 如果n>2呢?这是我们需要用到n=2时的策略,将A上面的两个盘子挪到B上,再将最大的盘子挪到C上,最后将B上的小盘子挪到C上就完成了所有的的步骤。例如n=3如下图:

Leetcode刷题详解——汉诺塔问题,leetcode,深度优先,算法

因为A中最后处理的是最大的盘子,所以在移动的过程中不存在大盘子在小盘子上面的情况

本题的操作:

  1. 对于规模为n的问题,我们需要将A柱上的n个盘子移动到C柱上

  2. 规模为n的问题可以被拆分成规模为n-1的子问题:

    1. 将A柱上的上面n-1个盘子移动到B柱上
    2. 将A柱上的最大盘子移动到C柱上,然后B柱上的n-1个盘子移动到C柱上
  3. 当问题的规模变为n=1时,即只有一个盘子时,我们可以直接将其从A柱移动到C柱

3.2 算法流程:

递归函数设计: void dfs(vector<int>& a, vector<int>& b, vector<int>& c,int n)

  1. 返回值:无

  2. 参数:三个柱子上的盘子,当前需要处理的盘子个数(当前问题规模)

  3. 函数作用:将A中的上面n个盘子挪到C中

递归函数流程:文章来源地址https://www.toymoban.com/news/detail-741318.html

  1. 当前问题规模为n=1时,直接将A中最上面盘子挪到C中并返回
  2. 递归将A中最上面的n-1个盘子挪到B中
  3. 将A中最上面的一个盘子挪到C中
  4. 将B中上面n-1个盘子挪到C中

3.3 C++算法代码:

class Solution {
public:
    void hanota(vector<int>& a, vector<int>& b, vector<int>& c) {
        dfs(a,b,c,a.size());

    }
    void dfs(vector<int>& a, vector<int>& b, vector<int>& c,int n)
    {
        //如果n为1时,将a放到c上
        if(n==1)
        {
            c.push_back(a.back());
            a.pop_back();
            return;
        }
        //将a的最上面的n-1个盘子放到b上
        dfs(a,c,b,n-1);
        //将a的最后一个盘子放到c上
        c.push_back(a.back());
        a.pop_back();
        //将b的最上面的n-1个盘子放到c上
        dfs(b,a,c,n-1);
    }
   
};

到了这里,关于Leetcode刷题详解——汉诺塔问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【完全二叉树节点数!】【深度优先】【广度优先】Leetcode 222 完全二叉树的节点个数

    ---------------🎈🎈题目链接🎈🎈------------------- 完全二叉树只有两种情况: 情况一:就是满二叉树, 情况二:最后一层叶子节点没有满。 对于情况一,可以直接用 2 ^ 树深度 - 1 来计算,注意这里根节点深度为1。 对于情况二,分别递归左孩子,和右孩子,递归到某一深度一

    2024年02月19日
    浏览(35)
  • LeetCode-1483. 树节点的第 K 个祖先【树 深度优先搜索 广度优先搜索 设计 二分查找 动态规划】

    给你一棵树,树上有 n 个节点,按从 0 到 n-1 编号。树以父节点数组的形式给出,其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。 树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。 实现 TreeAncestor 类: TreeAncestor(int n, int[] parent) 对树和父

    2024年04月16日
    浏览(39)
  • 剑指 Offer 12. 矩阵中的路径 / LeetCode 79. 单词搜索(深度优先搜索)

    链接:剑指 Offer 12. 矩阵中的路径;LeetCode 79. 单词搜索 难度:中等 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相

    2024年02月02日
    浏览(42)
  • Leetcode刷题详解——按摩师

    一个有名的按摩师会收到源源不断的预约请求,每个预约都可以选择接或不接。在每次预约服务之间要有休息时间,因此她不能接受相邻的预约。给定一个预约请求序列,替按摩师找到最优的预约集合(总预约时间最长),返回总的分钟数。 **注意:**本题相对原题稍作改动

    2024年02月08日
    浏览(42)
  • Leetcode刷题详解——下降路径最小和

    给你一个 n x n 的 方形 整数数组 matrix ,请你找出并返回通过 matrix 的 下降路径 的 最小和 。 下降路径 可以从第一行中的任何元素开始,并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列(即位于正下方或者沿对角线向左或者向右的第一个元素

    2024年02月08日
    浏览(42)
  • leetcode刷题之背包问题(01背包)

    01 背包 概念:有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是 w e i g h t [ i ] weight[i] w e i g h t [ i ] ,得到的价值是 v a l u e [ i ] value[i] v a l u e [ i ] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。 方法1:暴力回溯法 方法2:动态规划 三个

    2024年02月02日
    浏览(50)
  • Leetcode刷题详解——长度最小的子数组

    给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度**。**如果不存在符合条件的子数组,返回 0 。 示例 1: 示例 2: 示例 3: 提示: 1 = target = 109 1 = nums.length

    2024年02月07日
    浏览(49)
  • 每天一道leetcode:剑指 Offer 34. 二叉树中和为某一值的路径(中等&图论&深度优先遍历&递归)

    给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 树中节点总数在范围 [0, 5000] 内 -1000 = Node.val = 1000 -1000 = targetSum = 1000 使用递归深度优先遍历,使用前序遍历,在遍历途

    2024年02月12日
    浏览(49)
  • 剑指 Offer 34. 二叉树中和为某一值的路径 / LeetCode 113. 路径总和 II(深度优先搜索)

    链接:剑指 Offer 34. 二叉树中和为某一值的路径;LeetCode 113. 路径总和 II 难度:中等 给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 示例 1: 输入:root = [5,4,8,11,null,1

    2024年02月03日
    浏览(42)
  • leetcode&lintcode分类刷题:图论(三、多源最小距离问题)

    1、本次总结的题目通常是多个源头节点分别求解到达目标节点的最小距离,目标节点可能为多个,也可能为一个;要采用 广度优先搜索 的方法,但先提前入队的不是源头节点了,而是目标节点,由目标节点为基准一圈一圈的更新能够达到的“新目标”位置,每一圈更新能够

    2024年02月07日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包