一、算法的本質(zhì)：窮舉

數(shù)學(xué)算法：用數(shù)學(xué)角度和思維設(shè)計(jì)算法。

計(jì)算機(jī)算法：用計(jì)算機(jī)角度和思維設(shè)計(jì)算法。

窮舉難點(diǎn)

1.1、無(wú)遺漏

遺漏，會(huì)直接導(dǎo)致答案出錯(cuò)

1.2、無(wú)冗余

冗余，會(huì)拖慢算法的運(yùn)行速度

1、如何窮舉？即無(wú)遺漏地窮舉所有可能解。

2、如何聰明地窮舉？即避免所有冗余的計(jì)算，消耗盡可能少的資源求出答案。

先想出解法，然后在優(yōu)化

什么算法的難點(diǎn)在「如何窮舉」呢？一般是遞歸類問題，最典型的就是動(dòng)態(tài)規(guī)劃系列問題。

什么算法的難點(diǎn)在「如何聰明地窮舉」呢？一些耳熟能詳?shù)姆沁f歸算法技巧，都可以歸在這一類。

主要時(shí)間花在想出解法上，由多余的時(shí)間采取想如何優(yōu)化。優(yōu)化的事情是大佬們干的事情。

二、數(shù)組/單鏈表系列算法

單鏈表?？嫉募记删褪请p指針

數(shù)組常用的技巧有很大一部分還是雙指針相關(guān)的技巧，說(shuō)白了是教你如何聰明地進(jìn)行窮舉

3.1、二分搜索技巧

需要數(shù)組是有序的

3.2、滑動(dòng)窗口算法技巧

明確的知道什么時(shí)候應(yīng)該擴(kuò)大窗口，什么時(shí)候該收縮窗口

3.3、回文串相關(guān)技巧

3.4、前綴和技巧

前綴和技巧預(yù)計(jì)算一個(gè) preSum 數(shù)組，就可以避免循環(huán)

3.5、差分?jǐn)?shù)組技巧

差分?jǐn)?shù)組技巧維護(hù)一個(gè) diff 數(shù)組，也可以避免循環(huán)

三、二叉樹系列算法

二叉樹模型幾乎是所有高級(jí)算法的基礎(chǔ)

二叉樹題目的遞歸解法可以分兩類思路，

第一類是遍歷一遍二叉樹得出答案：回溯算法核心框架

第二類是通過(guò)分解問題計(jì)算出答案：動(dòng)態(tài)規(guī)劃核心框架

子問題的優(yōu)化一般可以通過(guò)創(chuàng)建一個(gè)緩存或者說(shuō)備忘錄來(lái)緩存之前的數(shù)據(jù)。提高效率