java 汉诺塔问题 递归_sherlock31415931的博客-程序员宅基地

技术标签: 算法  java  leetcode  leetcode算法  递归法  

题目链接

https://leetcode-cn.com/problems/hanota-lcci/

题目介绍


面试题 08.06. 汉诺塔问题

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

(1) 每次只能移动一个盘子;

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

(3) 盘子只能叠在比它大的盘子上。

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

你需要原地修改栈。

示例1:

输入:A = [2, 1, 0], B = [], C = []

输出:C = [2, 1, 0]


解题思路

其实汉诺塔问题,就是一个递归问题。

递归的思想很重要,假如把这个问题分解成一个很小的问题,我该怎么做。那么,如果小问题能解决,那么这个问题在哪个地方进行了复杂化

因为无论是大问题还是小问题,它们往往共享着同一个本质内核,而那往往也是解决问题的关键。

A:1个。你会如何做?直接拿过去,很简单!

A:2个。复杂点了,刚刚我们已经解决了一个了,那我们能不能把这个问题转换为1个呢?把A的一个拿到B上,那么问题就迎刃而解了。

A:3个。更复杂了,那我们能不能也像之前一样,把A变成1个呢?把A上面2个拿到B上,那么A不就剩下1个了。再把B上的两个拿过去不就结束了。(可以类比一下A:2个的情况,只是变成了B到C,A是过渡的柱子)

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

class Solution {
    
    public void hano(int n,List<Integer> A, List<Integer> B, List<Integer> C) {
    
        // 基例 A上只有一个
        if (n == 1) {
    
            C.add(A.remove(A.size() - 1)); // A别忘了清空
            return; //不返回值,但是会中断下面进程
        } else {
    
            hano(n-1,A,C,B);
            hano(1,A,B,C);
            hano(n-1,B,A,C);
        }
    }
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
    
        hano(A.size(),A,B,C);
    }
}

最优解

其实很多时候,想要有本质上的突破,应该回到最初的地方,换个角度思考,再一次从山脚重新出发,其实这个问题不就是让我把A里的全给C嘛!很简单!

class Solution {
    
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
    
        for (Integer i:A) {
    
            C.add(i);
        }
    }
}

拓展提升

其实很多时候学算法,但算法又是什么,算法不是凭空捏造的,若算法成了纯理论,它将不复有意义,算法是为了解决实际问题而设计的,说白了,与那些数学物理的思想有什么大的区别呢?就比如这道题,数学物理和算法的区别好比是python和java解决问题一样。

既然如此,很多时候遇到新的问题,不妨联想类比一下新的思想,我一直都相信,真正好的方法绝对共通的,只是可能表达形式不一样,正是这些基础的好方法构成了林林总总的方法论。

就拿这个递归来讲,其实不就是将问题转换为最简单,我们已知的可以解决的问题吗?

数学上当你学习新的理论的时候,数学老师总会说把这个陌生的问题转换为已知的问题去解决,然后用已知的推未知的

物理当你学变速运动,你不用记很多公式,你只需要记得加速度对时间的二阶导数是位移,其他你通过积分,转换就可以出来

算法上抛开本题,还有一类题目叫做动态规划,里面会有记事本,换了个名字,其实不就是记录下来我们已知的可以解决的问题吗?

当你学的越多,你可以思考的维度就越多,而当你把这一切联系起来的时候,一切都会不同。

Simple is the best!

大家觉得我写的好,可以关注我的Github,近期会一直更新java。
https://github.com/sherlcok314159/leetcode-java/blob/main/md/hano.md

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_50974223/article/details/114376711

智能推荐

ASO新手快速入门教程_任聪聪的博客-程序员宅基地

本篇文章主要讲解ASO的快速入门方法,主要为aso的基础知识和实践操作说明指南。适用:不了解ASO运营方法的小白或者比较对ASO感兴趣的同学。ASO应用场景:各大应用商店,小程序的搜索等。什么是ASOASO是近几年刚出现的搜索引擎优化技术,它的出现是伴随着移动互联网的到来,而aso也仅仅是APP运营领域的一种推广手段,它更多的局限于各个应用商店。与seo对比,我们会发现ASO实际上就是换了一个地方和形式的推广技术,相对于seo,他的范围更加简单和固定,我总结后大致概括为这三个部分:搜索关键词优.

iphone 6s pp助手 越狱_weixin_33797791的博客-程序员宅基地

iphone 6s pp助手 越狱 https://www.apple.com/iphone-6/合适初高中学习英语http://www.travelchinaguide.comhttp://jailbreak.25pp.com/ iphone 6 越狱教程;您好,欢迎关注PP助手!很高兴为您解答:手机安装PP助手,下载软件会比较方便。未越狱...

Spark基础篇(一) - 概述&&源码编译_Spark on yarn的博客-程序员宅基地

第一章:MapReduce的局限性–&gt;Spark的产生1.1 各个框架单独为战&amp;&amp;使用Spark框架做对比第二章:Spark概述及特点2.1 四大特性(Speed、Ease Of Use、Generality、Runs Everywhere)2.2 Spark各个版本介绍第三章:自定义编译Spark3.1 Spark目录解读3.2 在Spark客户端上完成一个wordcount第一章:MapReduce的局限性–&gt;Spark的产生繁杂,不管是开发

Java——静态方法只能通过类名调用吗?_奔跑的狮子a的博客-程序员宅基地_静态方法只能使用类名调用

静态方法调用的三种方式:1、new xx().静态(); //使用对象调用,不推荐2、xx.静态(); //类名调用,正规调用方法,推荐3、静态(); //本类的静态方法在本类调用,直接调用欢迎各位在评论区留言探讨...

Mac应用程序无法打开或文件损坏的处理方法_一粒沙-的博客-程序员宅基地

很多用户在安装Mac软件的时候,经常会遇到提示“xxx.app已损坏,打不开。您应该将它移到废纸篓“或”打不开的xxx.app,因为它来自身份不明的开发者”,如下图的样子:真的损坏了么?是不是真的要移动到废纸篓呢?遇到这样的情况,通常是打开任何来源即可轻松解决,下面Macdown小编就为您带来Mac应用程序无法打开或文件损坏的处理方法,解答Mac没有任何来源选项怎么开启?的问...

xampp虚拟机配置_ljd914040633的博客-程序员宅基地

&amp;lt;VirtualHost *:80&amp;gt; DocumentRoot &quot;D:/stack/chubu&quot; ServerName www.mysql.com &amp;lt;Directory &quot;D:/stack/chubu&quot;&amp;gt; Options Indexes FollowSymLinks Includes ExecCGI AllowOverr...

随便推点

Starling框架帮助手册中文版(PDF下载)_weixin_33966365的博客-程序员宅基地

什么是Statling?Starling 是一个基于Stage3D(这是Flash Player11及Adobe AIR 3中新增的为3D加速功能所提供的API)所开发的一个能够使用GPU来加速的2D Flash应用程序的ActionScript3框架。Starling主要是为游戏开发而设计的, 但是它的用途不仅限于此。Starling最大的好处在于你可以很快地写出使用GPU加速的应用程序而不必接...

Hadoop-No.10之列簇_dcy22899的博客-程序员宅基地

HBase中包含列簇(column family)的概念.列簇本质上是列的存储容器.一张表可以有一个或多个列簇.每个列簇都有自己的HFile结婚,而且在执行合并操作时,同一个表的其他列簇不受影响在很多实用案例中,一张表不需要多个列簇.如果一张标中国的一部分列操作完成,或者变化频率与其他列存在显著不同,则可以使用一个以上的列簇.比如,...

Vue脚手架项目流程_越墨的博客-程序员宅基地

Vue脚手架项目流程一、Vue脚手架的安装1、node.js安装2、npm3、vue-cli安装二、初始化一个vue项目三、项目目录结构1、主要目录2、核心文件3、关系图四、vue-router1、基本写法及传参的使用2、路由嵌套五、引入ElementUi一、Vue脚手架的安装1、node.js安装Vue CLI 需要 Node.js 8.9 或更高版本 (推荐 8.11.0+)。你可以使用 nvm 或 nvm-windows在同一台电脑中管理多个 Node 版本。nvm工具的下载和安装:1、ht

POJ Blue Jeans [枚举+KMP]_weixin_33937913的博客-程序员宅基地

传送门F -Blue JeansTime Limit:1000MSMemory Limit:65536KB64bit IO Format:%I64d &amp; %I64uSubmitStatusDescriptionThe Genographic Project is a research partnership between I...

Python 之UnicodeEncodeError 错误_leader_ww的博客-程序员宅基地_python unicodeencodeerror

Python 之UnicodeEncodeError 错误在测试 “用Python进行诗歌接龙” 的Python 文件时,遇到UnicodeEncodeError: 'gbk' codec can't encode character '\xa0' in position 26: illegal multibyte sequence 错误,见下图:查,是打开文件时,Windows 操...

javascript继承系列详解_weixin_33910434的博客-程序员宅基地

参考文章:http://www.cnblogs.com/sanshi/archive/2009/07/08/1519036.html新建一个Asp.net项目,在Script下添加两个*.js文件,如下图: (1)JavaScriptDemo.js文件代码://原型(prototype),我们可以简单的把prototype看做是一个模版,新创建的自定义对象都是这个模版(prot...

推荐文章

热门文章

相关标签