題目描述

在經(jīng)典漢諾塔問題中，有 3 根柱子及 N 個(gè)不同大小的穿孔圓盤，盤子可以滑入任意一根柱子。
一開始，所有盤子自上而下按升序依次套在第一根柱子上(即每一個(gè)盤子只能放在更大的盤子上面)。
移動(dòng)圓盤時(shí)受到以下限制：
? (1) 每次只能移動(dòng)一個(gè)盤子;
? (2) 盤子只能從柱子頂端滑出移到下一根柱子;
? (3) 盤子只能疊在比它大的盤子上。
請(qǐng)編寫程序，用棧將所有盤子從第一根柱子移到最后一根柱子。
你需要原地修改棧。
A中盤子的數(shù)目不大于14個(gè)。

輸入：A = [2, 1, 0], B = [], C = []
輸出：C = [2, 1, 0]

輸入：A = [1, 0], B = [], C = []
輸出：C = [1, 0]

數(shù)據(jù)結(jié)構(gòu)

• 鏈表、棧

算法思維

• 遞歸

解題要點(diǎn)

• 遞歸思維的靈活運(yùn)用

關(guān)鍵知識(shí)點(diǎn)：遞歸

• 概念
  數(shù)學(xué)與計(jì)算機(jī)科學(xué)范疇，是指在函數(shù)的定義中使用函數(shù)自身的方法
  遞歸算法是一種直接或者間接調(diào)用自身函數(shù)的算法
• 本質(zhì)
  遞歸，去的過程叫"遞"，回來的過程叫"歸"
  遞是調(diào)用，歸是結(jié)束后回來
  是一種循環(huán)，而且在循環(huán)中執(zhí)行的就是調(diào)用自己
• 三要素
  結(jié)束條件
  函數(shù)主功能
  函數(shù)的等價(jià)關(guān)系式（參數(shù)、返回值、關(guān)系）
• 遞歸方法模板

public int recursion(int n) {
    //1.結(jié)束條件
    if (n == 1) {
        return 1; 
    }
    
    //2.函數(shù)主功能 do something
    System.out.println(n);

    //3.等價(jià)關(guān)系式 f(n)=n+f(n-1) 轉(zhuǎn)換為簡(jiǎn)單問題
    return n + recursion(n - 1);
}

解題步驟

一. Comprehend 理解題意

題目主干

• 通過程序解決漢諾塔問題
• 圓盤數(shù)量不固定

細(xì)節(jié)問題

• 嚴(yán)格遵守漢諾塔規(guī)則

附加限制

• 原地修改

寬松限制

• A中盤子的數(shù)目不大于14個(gè)
  
  

二. Choose 選擇數(shù)據(jù)結(jié)構(gòu)與算法

數(shù)據(jù)結(jié)構(gòu)選擇

• 輸入和輸出的參數(shù)類型已經(jīng)限定為 List
• 其中 “盤子只能從柱子頂端滑出移到下一根柱子”
• 與棧的后進(jìn)先出的特點(diǎn)一致
• 但輸入輸出參數(shù)均為 List
• 每次都在 List 尾部添加或者移除（模擬棧的方式）

算法思維選擇

美國(guó)學(xué)者提出的一種兩步操作法：
將柱子擺成品字型，擺放順序由圓盤數(shù)量奇偶性決定
? 思考1層漢諾塔、2層漢諾塔如何移動(dòng)
? ? 若n為奇數(shù)，按順時(shí)針方向依次擺放 A C B
? ? 若n為偶數(shù)，按順時(shí)針方向依次擺放 A B C

解題思路

1. 按順時(shí)針方向把圓盤1從現(xiàn)在的柱子移動(dòng)到下一根柱子
2. 把另外兩根柱子上可以移動(dòng)的圓盤移動(dòng)到新的柱子上
   ? 把非空柱子上的圓盤移動(dòng)到空柱子上
   ? 當(dāng)兩根柱子都非空時(shí)，移動(dòng)較小的圓盤
3. 反復(fù)進(jìn)行1、2兩步操作，最后就能按規(guī)定完成漢諾塔的移動(dòng)
   
   

三. Code 編碼實(shí)現(xiàn)基本解法

解題思路剖析

判斷盤子總數(shù)奇偶性，例如為偶數(shù)，則順序?yàn)?ABC
1.最小盤子移動(dòng)到下一個(gè)柱子
2.另兩個(gè)柱子較小的盤子移動(dòng)到另一個(gè)
不斷重復(fù)1、2兩步

class Solution {
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        int size = A.size();
        List<Integer>[] lists = new List[3];
        lists[0] = A;
        if (size % 2 == 0) {//若n為偶數(shù)，按順時(shí)針方向依次擺放 A B C；
            lists[1] = B;
            lists[2] = C;
        } else { // 若n為奇數(shù)，按順時(shí)針方向依次擺放 A C B
            lists[1] = C;
            lists[2] = B;
        }
        int currentIndex = 0; //記錄最小盤子所在的柱子下標(biāo)
        while (C.size() < size) {
            List<Integer> current = lists[currentIndex];
            currentIndex = (currentIndex + 1) % 3; //編號(hào)最小盤子所在柱子的下一個(gè)柱子
            List<Integer> next = lists[currentIndex];
            List<Integer> pre = lists[(currentIndex + 1) % 3]; //編號(hào)最小盤子所在柱子的上一個(gè)柱子
            int preSize = pre.size();
            int curSize = current.size();
            next.add(current.remove(--curSize)); //最小的圓盤 移動(dòng)到下一個(gè)柱子
            //另外兩根柱子上可以移動(dòng)的圓盤移動(dòng)到新的柱子上 當(dāng)兩根柱子都非空時(shí)，移動(dòng)較小的圓盤
            int plateToMove1 = preSize == 0 ? Integer.MAX_VALUE : pre.get(preSize - 1);
            int plateToMove2 = curSize == 0 ? Integer.MAX_VALUE : current.get(curSize - 1);
            if (plateToMove1 < plateToMove2) {
                current.add(pre.remove(preSize - 1));
            } else if (plateToMove2 < plateToMove1) {
                pre.add(current.remove(curSize - 1));
            }
        }
    }
}

時(shí)間復(fù)雜度：O(2ⁿ)
? ? 需要多次比較盤子大小以及移動(dòng)盤子，移動(dòng)次數(shù)為 2ⁿ-1
? ? 在每次移動(dòng)前還需要進(jìn)行比較，比較次數(shù)也為 2ⁿ-1

空間復(fù)雜度：O(1)
? ? 常數(shù)級(jí)變量空間 O(1)

執(zhí)行耗時(shí)：6 ms，擊敗了 7.21% 的Java用戶
內(nèi)存消耗：37.4 MB，擊敗了 77.97% 的Java用戶

四. Consider 思考更優(yōu)解

尋找更好的算法思維 -- 遞歸

N層漢諾塔 該如何思考呢？

• 如果我們能將上面的 N-1 層移動(dòng)到B上
• 把N層移動(dòng)到C，再把B上N-1層移動(dòng)到C上就可以解決問題了
• 問題變?yōu)槿绾谓鉀QN-1層漢諾塔的移動(dòng)問題
• 繼續(xù)思考一直到N-1等于1時(shí)，我們可以直接將1層漢諾塔移動(dòng)目的位置
  
  

五. Code 編碼實(shí)現(xiàn)最優(yōu)解

解題思路剖析

• 遞歸結(jié)束條件：移動(dòng)一個(gè)盤子
• 遞歸函數(shù)主功能
  ? ? 移動(dòng) N-1 個(gè)盤子到中間柱子
  ? ? 移動(dòng)第 N 個(gè)盤子到目標(biāo)柱子
  ? ? 將 N-1 個(gè)盤子從中間柱子移動(dòng)到目標(biāo)柱子
• 函數(shù)的等價(jià)關(guān)系式
  ? ? 參數(shù)：本輪盤子數(shù)量、三個(gè)柱子（List）
  ? ? 返回值：無返回值，使用List中本地刪除的方式
  ? ? 等價(jià)關(guān)系：f(n,A,B,C) = f(n-1,A,C,B) + M(A,C) + f(n-1,B,A,C)

class Solution {
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        movePlate(A.size(), A, B, C);
    }

    /**
     * @param size      需要移動(dòng)盤子的數(shù)量
     * @param start     起始柱子
     * @param auxiliary 輔助柱子
     * @param target    目標(biāo)柱子
     */
    private void movePlate(int size, List<Integer> start, List<Integer>
            auxiliary, List<Integer> target) {
        if (size == 1) { // 只剩一個(gè)盤子時(shí)，直接從第一個(gè)柱子移動(dòng)到第三個(gè)柱子 即可
            target.add(start.remove(start.size() - 1));
            return;
        }
        // 將 n-1 個(gè)盤子，從 第一個(gè)柱子 移動(dòng)到 第二個(gè)柱子
        movePlate(size - 1, start, target, auxiliary);
        // 將第 n個(gè)盤子，從 第一個(gè)柱子 移動(dòng)到 第三個(gè)柱子
        target.add(start.remove(start.size() - 1));
        // 再將 n-1 個(gè)盤子，從 第二個(gè)柱子 移動(dòng)到 第三個(gè)柱子
        movePlate(size - 1, auxiliary, start, target);
    }
}

時(shí)間復(fù)雜度：O(2ⁿ)
使用迭代法分析
? ? 設(shè)遞歸函數(shù)的運(yùn)行時(shí)間 T(n)
? ? 每輪遞歸調(diào)用兩次遞歸函數(shù)，每調(diào)用一次問題規(guī)模減少 1，T(n) = 2×T(n - 1)
? ? 所以最終的復(fù)雜度為 O(2ⁿ)，其中比較次數(shù)為 0，省略了比較大小的步驟

空間復(fù)雜度：O(n)
? ? 函數(shù)中我們不需要主動(dòng)創(chuàng)建額外存儲(chǔ)
? ? 但遞歸調(diào)用本身需要進(jìn)行堆棧的存儲(chǔ)
? ? 空間復(fù)雜度和遞歸的深度有關(guān)系
? ? 遞歸深度為 n，所以空間復(fù)雜度為 O(n)

執(zhí)行耗時(shí)：1 ms，擊敗了 84.31% 的Java用戶
內(nèi)存消耗：37.7 MB，擊敗了 13.28% 的Java用

六. Change 變形與延伸

題目變形

• （練習(xí)）如果規(guī)則變?yōu)榇蟊P必須放在小盤上該如何實(shí)現(xiàn)？

延伸擴(kuò)展

• 遞歸是一種基本的編程思維
  ? 快速排序、歸并排序、二分查找、樹……
• 實(shí)際工作中應(yīng)用很廣泛
  ? 按照組織架構(gòu)統(tǒng)計(jì)公司某部門人數(shù)
  ? 按職級(jí)關(guān)系統(tǒng)計(jì)銷售人員提成