在经典汉诺塔问题中，有 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 } }
完整代码（含测试样例）：
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 } }
运行结果：
2 1 0 Process finished with exit code 0
