汉诺塔问题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<Integer> A, List<Integer> B, List<Integer> C) { int n = A.size(); // 总共n个盘子 move(n,A,B,C); } private void move(int n, List<Integer> a, List<Integer> b, List<Integer> 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 }
}

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
 

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

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<Integer> A = new ArrayList<Integer>(); List<Integer> B = new ArrayList<Integer>(); List<Integer> C = new ArrayList<Integer>(); 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<Integer> A, List<Integer> B, List<Integer> C) { int n = A.size(); // 总共n个盘子 move(n,A,B,C); } private void move(int n, List<Integer> a, List<Integer> b, List<Integer> 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 }
}
  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
 

运行结果：

2
1
0

Process finished with exit code 0

  
 

  
1
  
2
  
3
  
4
  
5
 

看完如果对你有帮助，感谢点赞支持！
如果你是电脑端，看到右下角的 “一键三连” 了吗，没错点它[哈哈]

加油！

共同努力！

Keafmd

文章来源: keafmd.blog.csdn.net，作者：牛哄哄的柯南，版权归原作者所有，如需转载，请联系作者。

原文链接：keafmd.blog.csdn.net/article/details/112439561