汉诺塔问题Java版【递归求解】（力扣）

汉诺塔问题

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

提示:

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

==题意：就是经典的汉诺塔问题，将盘子从A移动到C。==

==思路：看本人的这篇文章，里面详细解释了：汉诺塔问题（递归写法）==

==代码：==

class Solution { public void hanota(List A, List B, List C) { int n = A.size(); // 总共n个盘子 move(n,A,B,C); } private void move(int n, List a, List b, List c) { if(n==1){ c.add(a.remove(a.size()-1)); return; } // 最初 a是满的,所有盘子都在a上,b是空的,c是空的 //三步走战略： //第一步：把a上面的n-1个盘子从a借助c移动到b上 //第二步：把a上面的最下面的那个盘子从a移动到c //第三步：把b上面的n-1个盘子借助a移动到c上 move(n-1,a,c,b); //将a上面n-1个盘子通过c移动到b c.add(a.remove(a.size()-1)); // 将a最下面的那个盘子移动到c move(n-1,b,a,c); // 将n-1个盘子通过a从a移动到c } }

==完整代码（含测试样例）：==

package com.Keafmd.day0110; import java.util.ArrayList; import java.util.List; /** * Keafmd * * @ClassName: Hanota * @Description: 汉诺塔问题 https://leetcode-cn.com/problems/hanota-lcci/ * @author: 牛哄哄的柯南 * @date: 2021-01-10 19:15 */ public class Hanota { public static void main(String[] args) { List A = new ArrayList(); List B = new ArrayList(); List C = new ArrayList(); A.add(2); A.add(1); A.add(0); Solution solution = new Solution(); solution.hanota(A,B,C); for (int i = 0; i < C.size(); i++) { System.out.println(C.get(i)); } } } class Solution { public void hanota(List A, List B, List C) { int n = A.size(); // 总共n个盘子 move(n,A,B,C); } private void move(int n, List a, List b, List c) { if(n==1){ c.add(a.remove(a.size()-1)); return; } // 最初 a是满的,所有盘子都在a上,b是空的,c是空的 //三步走战略： //第一步：把a上面的n-1个盘子从a借助c移动到b上 //第二步：把a上面的最下面的那个盘子从a移动到c //第三步：把b上面的n-1个盘子借助a移动到c上 move(n-1,a,c,b); //将a上面n-1个盘子通过c移动到b c.add(a.remove(a.size()-1)); // 将a最下面的那个盘子移动到c move(n-1,b,a,c); // 将n-1个盘子通过a从a移动到c } }

==运行结果：==

2 1 0 Process finished with exit code 0

看完如果对你有帮助，感谢支持！

加油！

共同努力！

Keafmd

Java

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。