漢諾塔問題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小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。