數(shù)據(jù)結(jié)構(gòu)和算法學(xué)習(xí)筆記（2）

三、算法刷題指南

首先要明確的是， 數(shù)據(jù)結(jié)構(gòu)是工具，算法是通過(guò)合適的工具解決特定問(wèn)題的方法 。也就是說(shuō)，學(xué)習(xí)算法之前，最起碼得了解那些常用的數(shù)據(jù)結(jié)構(gòu)，了解它們的特性和缺陷。

那么該如何在 LeetCode 刷題呢？之前的文章算法學(xué)習(xí)之路寫過(guò)一些，什么按標(biāo)簽刷，堅(jiān)持下去云云?，F(xiàn)在距那篇文章已經(jīng)過(guò)去將近一年了，我不想說(shuō)那些不痛不癢的話了，直接說(shuō)具體的建議：

先刷二叉樹(shù)，先刷二叉樹(shù)，先刷二叉樹(shù) ！

這是我這刷題的親身體會(huì)，下圖是我從 2018/10 到 2019/10 這一年的心路歷程：

公眾號(hào)文章的閱讀數(shù)據(jù)顯示，大部分人對(duì)數(shù)據(jù)結(jié)構(gòu)相關(guān)的算法文章不感興趣，而是更關(guān)心動(dòng)規(guī)回溯分治等等技巧。為什么要先刷二叉樹(shù)呢， 因?yàn)槎鏄?shù)是最容易培養(yǎng)框架思維的，而且大部分算法技巧，本質(zhì)上都是樹(shù)的遍歷問(wèn)題 。

刷二叉樹(shù)看到題目沒(méi)思路？根據(jù)很多讀者的問(wèn)題，其實(shí)大家不是沒(méi)思路，只是沒(méi)有理解我們說(shuō)的「框架」是什么。 不要小看這幾行破代碼，幾乎所有二叉樹(shù)的題目都是一套這個(gè)框架就出來(lái)了 。

void traverse(TreeNode root) {
    // 前序遍歷
    traverse(root.left)
    // 中序遍歷
    traverse(root.right)
    // 后序遍歷
}

比如說(shuō)我隨便拿幾道題的解法出來(lái)，不用管具體的代碼邏輯，只要看看框架在其中是如何發(fā)揮作用的就行。

LeetCode 124 題，難度 Hard，讓你求二叉樹(shù)中最大路徑和，主要代碼如下：

看出來(lái)了嗎，這就是個(gè)后序遍歷嘛。

LeetCode 105 題，難度 Medium，讓你根據(jù)前序遍歷和中序遍歷的結(jié)果還原一棵二叉樹(shù)，很經(jīng)典的問(wèn)題吧，主要代碼如下：

不要看這個(gè)函數(shù)的參數(shù)很多，只是為了控制數(shù)組索引而已，本質(zhì)上該算法也就是一個(gè)前序遍歷。

LeetCode 99 題，難度 Hard，恢復(fù)一棵 BST，主要代碼如下：

這不就是個(gè)中序遍歷嘛，對(duì)于一棵 BST 中序遍歷意味著什么，應(yīng)該不需要解釋了吧。

你看，Hard 難度的題目不過(guò)如此，而且還這么有規(guī)律可循，只要把框架寫出來(lái)，然后往相應(yīng)的位置加?xùn)|西就行了，這不就是思路嗎。

剛開(kāi)始刷二叉樹(shù)的題目，前 10 道也許有點(diǎn)難受；結(jié)合框架再做 20 道，也許你就有點(diǎn)自己的理解了；刷完整個(gè)專題，再去做什么回溯動(dòng)規(guī)分治專題，你就會(huì)發(fā)現(xiàn)只要涉及遞 歸的問(wèn)題，都是樹(shù)的問(wèn)題 。

def coinChange(coins: List[int], amount: int):

    def dp(n):
        if n == 0: return 0
        if n < 0: return -1

        res = float('INF')
        for coin in coins:
            subproblem = dp(n - coin)
            # 子問(wèn)題無(wú)解，跳過(guò)
            if subproblem == -1: continue
            res = min(res, 1 + subproblem)
        return res if res != float('INF') else -1

    return dp(amount)

這么多代碼看不懂咋辦？直接提取出框架，就能看出核心思路了：

# 不過(guò)是一個(gè) N 叉樹(shù)的遍歷問(wèn)題而已
def dp(n):
    for coin in coins:
        dp(n - coin)

其實(shí)很多動(dòng)態(tài)規(guī)劃問(wèn)題就是在遍歷一棵樹(shù)，你如果對(duì)樹(shù)的遍歷操作爛熟于心，起碼知道怎么把思路轉(zhuǎn)化成代碼，也知道如何提取別人解法的核心思路。

再看看回溯算法，前文回溯算法詳解干脆直接說(shuō)了，回溯算法就是個(gè) N 叉樹(shù)的前后序遍歷問(wèn)題，沒(méi)有例外。

比如 N 皇后問(wèn)題吧，主要代碼如下：

void backtrack(int[] nums, LinkedList) {
    if (track.size() == nums.length) {
        res.add(new LinkedList(track));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        if (track.contains(nums[i]))
            continue;
        track.add(nums[i]);
        // 進(jìn)入下一層決策樹(shù)
        backtrack(nums, track);
        track.removeLast();
    }

/* 提取出 N 叉樹(shù)遍歷框架 */
void backtrack(int[] nums, LinkedList) {
    for (int i = 0; i < nums.length; i++) {
        backtrack(nums, track);
}

N 叉樹(shù)的遍歷框架，找出來(lái)了吧。你說(shuō)，樹(shù)這種結(jié)構(gòu)重不重要？

綜上，對(duì)于算法無(wú)從下手的朋友來(lái)說(shuō)，可以先刷樹(shù)的相關(guān)題目，試著從框架上看問(wèn)題，而不要糾結(jié)于細(xì)節(jié)問(wèn)題 。

糾結(jié)細(xì)節(jié)問(wèn)題，就比如糾結(jié) i 到底應(yīng)該加到 n 還是加到 n - 1，這個(gè)數(shù)組的大小到底應(yīng)該開(kāi) n 還是 n + 1 ？

從框架上看問(wèn)題，就是像我們這樣基于框架進(jìn)行抽取和擴(kuò)展，既可以在看別人解法時(shí)快速理解核心邏輯，也有助于找到我們自己寫解法時(shí)的思路方向。

當(dāng)然，如果細(xì)節(jié)出錯(cuò)，你得不到正確的答案，但是只要有框架，你再錯(cuò)也錯(cuò)不到哪去，因?yàn)槟愕姆较蚴菍?duì)的。

但是，你要是心中沒(méi)有框架，那么你根本無(wú)法解題，給了你答案，你也不會(huì)發(fā)現(xiàn)這就是個(gè)樹(shù)的遍歷問(wèn)題。

這種思維是很重要的，動(dòng)態(tài)規(guī)劃詳解中總結(jié)的找狀態(tài)轉(zhuǎn)移方程的幾步流程，有時(shí)候按照流程寫出解法，說(shuō)實(shí)話我自己都不知道為啥是對(duì)的，反正它就是對(duì)了。。。

這就是框架的力量，能夠保證你在快睡著的時(shí)候，依然能寫出正確的程序； 就算你啥都不會(huì)，都能比別人高一個(gè)級(jí)別。

四、最后總結(jié)

數(shù)據(jù)結(jié)構(gòu)的基本存儲(chǔ)方式就是鏈?zhǔn)胶晚樞騼煞N，基本操作就是增刪查改，遍歷方式無(wú)非迭代和遞歸。

刷算法題建議從「樹(shù)」分類開(kāi)始刷，結(jié)合框架思維，把這幾十道題刷完，對(duì)于樹(shù)結(jié)構(gòu)的理解應(yīng)該就到位了。這時(shí)候去看回溯、動(dòng)規(guī)、分治等算法專題，對(duì)思路的理解可能會(huì)更加深刻一些。