10、動(dòng)態(tài)規(guī)劃系列
10.1 斐波那契數(shù)列??馬上解題
題目描述
求斐波那契數(shù)列的第 n 項(xiàng)，n <= 39。
解題思路
（1）使用遞歸求解，會(huì)重復(fù)計(jì)算一些子問(wèn)題。例如，計(jì)算 f(4) 需要計(jì)算 f(3) 和 f(2)，計(jì)算 f(3) 需要計(jì)算 f(2) 和 f(1)，可以看到 f(2) 被重復(fù)計(jì)算了。
（2）使用動(dòng)態(tài)規(guī)劃，遞歸是將一個(gè)問(wèn)題劃分成多個(gè)子問(wèn)題求解，動(dòng)態(tài)規(guī)劃也是如此，但是動(dòng)態(tài)規(guī)劃會(huì)把子問(wèn)題的解緩存起來(lái)，從而避免重復(fù)求解子問(wèn)題。
代碼
（1）遞歸解題略
（2）動(dòng)態(tài)規(guī)劃解題
由于當(dāng)前項(xiàng)的值只和前兩項(xiàng)有關(guān)，所以只需要保存前兩項(xiàng)的值即可，這樣就把空間復(fù)雜度由O(N)控制在O(1)。
10.2 矩形覆蓋??馬上解題
題目描述
我們可以用 2*1 的小矩形橫著或者豎著去覆蓋更大的矩形。請(qǐng)問(wèn)用 n 個(gè) 2*1 的小矩形無(wú)重疊地覆蓋一個(gè) 2*n 的大矩形，總共有多少種方法？
解題思路
當(dāng) n 為 1 時(shí)，只有一種覆蓋方法：
當(dāng) n 為 2 時(shí)，有兩種覆蓋方法：
要覆蓋 2*n 的大矩形，可以先覆蓋 2*1 的矩形，再覆蓋 2*(n-1) 的矩形；或者先覆蓋 2*2 的矩形，再覆蓋 2*(n-2) 的矩形。而覆蓋 2*(n-1) 和 2*(n-2) 的矩形可以看成子問(wèn)題。該問(wèn)題的遞推公式如下：
代碼：
10.3 跳臺(tái)階??馬上解題
題目描述
一只青蛙一次可以跳上 1 級(jí)臺(tái)階，也可以跳上 2 級(jí)。求該青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法。
解題思路
當(dāng) n = 1 時(shí)，只有一種跳法：
當(dāng) n = 2 時(shí)，有兩種跳法：
跳 n 階臺(tái)階，可以先跳 1 階臺(tái)階，再跳 n-1 階臺(tái)階；或者先跳 2 階臺(tái)階，再跳 n-2 階臺(tái)階。而 n-1 和 n-2 階臺(tái)階的跳法可以看成子問(wèn)題，該問(wèn)題的遞推公式為：
代碼
10.4 變態(tài)跳臺(tái)階??馬上解題
題目描述
一只青蛙一次可以跳上 1 級(jí)臺(tái)階，也可以跳上 2 級(jí)... 它也可以跳上 n 級(jí)。求該青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法。
解題思路
跳上 n-1 級(jí)臺(tái)階，可以從 n-2 級(jí)跳 1 級(jí)上去，也可以從 n-3 級(jí)跳 2 級(jí)上去...，那么
f(n-1) = f(n-2) + f(n-3) + ... + f(0)
同樣，跳上 n 級(jí)臺(tái)階，可以從 n-1 級(jí)跳 1 級(jí)上去，也可以從 n-2 級(jí)跳 2 級(jí)上去... ，那么
f(n) = f(n-1) + f(n-2) + ... + f(0)
代碼
11. 旋轉(zhuǎn)數(shù)組的最小數(shù)字??馬上解題
題目描述
把一個(gè)數(shù)組最開(kāi)始的若干個(gè)元素搬到數(shù)組的末尾，我們稱(chēng)之為數(shù)組的旋轉(zhuǎn)。輸入一個(gè)非遞減排序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。
解題思路
（1）對(duì)數(shù)組排序，但是時(shí)間復(fù)雜度至少為O(logN)，而且需要另外的空間O(N)。
（2）遍歷數(shù)組，時(shí)間復(fù)雜度為O(N)。
（3）將旋轉(zhuǎn)數(shù)組對(duì)半分可以得到一個(gè)包含最小元素的新旋轉(zhuǎn)數(shù)組，以及一個(gè)非遞減排序的數(shù)組。新的旋轉(zhuǎn)數(shù)組的數(shù)組元素是原數(shù)組的一半，從而將問(wèn)題規(guī)模減少了一半，這種折半性質(zhì)的算法的時(shí)間復(fù)雜度為 O(logN)（為了方便，這里將 log2N 寫(xiě)為 logN）。
通過(guò)修改二分查找算法進(jìn)行求解（l 代表 low，m 代表 mid，h 代表 high）：當(dāng) nums[m] <= nums[h] 時(shí)，表示 [m, h] 區(qū)間內(nèi)的數(shù)組是非遞減數(shù)組，[l, m] 區(qū)間內(nèi)的數(shù)組是旋轉(zhuǎn)數(shù)組，此時(shí)令 h = m；否則 [m + 1, h] 區(qū)間內(nèi)的數(shù)組是旋轉(zhuǎn)數(shù)組，令 l = m + 1。
代碼
（1）（2）省略
（3）二分法
12、矩陣中的路徑??馬上解題
題目描述
判斷在一個(gè)矩陣中是否存在一條包含某字符串所有字符的路徑。路徑可以從矩陣中的任意一個(gè)格子開(kāi)始，每一步可以在矩陣中向上下左右移動(dòng)一個(gè)格子。如果一條路徑經(jīng)過(guò)了矩陣中的某一個(gè)格子，則該路徑不能再進(jìn)入該格子。
例如下面的矩陣包含了一條 bfce 路徑。
解題思路
使用回溯法（backtracking）進(jìn)行求解，它是一種暴力搜索方法，通過(guò)搜索所有可能的結(jié)果來(lái)求解問(wèn)題?；厮莘ㄔ谝淮嗡阉鹘Y(jié)束時(shí)需要進(jìn)行回溯（回退），將這一次搜索過(guò)程中設(shè)置的狀態(tài)進(jìn)行清除，從而開(kāi)始一次新的搜索過(guò)程。例如下圖示例中，從 f 開(kāi)始，下一步有 4 種搜索可能，如果先搜索 b，需要將 b 標(biāo)記為已經(jīng)使用，防止重復(fù)使用。在這一次搜索結(jié)束之后，需要將 b 的已經(jīng)使用狀態(tài)清除，并搜索 c。
本題的輸入是數(shù)組而不是矩陣（二維數(shù)組），因此需要先將數(shù)組轉(zhuǎn)換成矩陣。
14、剪繩子
題目描述
把一根繩子剪成多段，并且使得每段的長(zhǎng)度乘積最大。
n = 2
return 1 (2 = 1 + 1)
n = 10
return 36 (10 = 3 + 3 + 4)
解題思路
（1）貪心
盡可能多剪長(zhǎng)度為 3 的繩子，并且不允許有長(zhǎng)度為 1 的繩子出現(xiàn)。如果出現(xiàn)了，就從已經(jīng)切好長(zhǎng)度為 3 的繩子中拿出一段與長(zhǎng)度為 1 的繩子重新組合，把它們切成兩段長(zhǎng)度為 2 的繩子。
證明：當(dāng) n >= 5 時(shí)，3(n - 3) - n = 2n - 9 > 0，且 2(n - 2) - n = n - 4 > 0。因此在 n >= 5 的情況下，將繩子剪成一段為 2 或者 3，得到的乘積會(huì)更大。又因?yàn)?3(n - 3) - 2(n - 2) = n - 5 >= 0，所以剪成一段長(zhǎng)度為 3 比長(zhǎng)度為 2 得到的乘積更大。
（2）動(dòng)態(tài)規(guī)劃
先從最低處開(kāi)始計(jì)算乘積并將每個(gè)數(shù)可以剪切后得到的成績(jī)最大值進(jìn)行存儲(chǔ)。當(dāng)計(jì)算后面的值的時(shí)候利用已經(jīng)存儲(chǔ)好的最大值，計(jì)算所有可能的結(jié)果并保留最大的。時(shí)間復(fù)雜度O（n*n）空間復(fù)雜度O（n）。
代碼
（1）貪心-數(shù)學(xué)總結(jié)
（2）動(dòng)態(tài)規(guī)劃
15、二進(jìn)制中1的個(gè)數(shù)? 馬上解題
題目描述
輸入一個(gè)整數(shù)，輸出該數(shù)二進(jìn)制表示中 1 的個(gè)數(shù)。
解題思路
n&(n-1)
該位運(yùn)算去除 n 的位級(jí)表示中最低的那一位。
n? ? ? : 10110100
n-1? ? : 10110011
n&(n-1) : 10110000
時(shí)間復(fù)雜度：O(M)，其中 M 表示 1 的個(gè)數(shù)。
代碼
當(dāng)n為正數(shù)的時(shí)候，但是當(dāng)n為負(fù)數(shù)時(shí)，最終數(shù)字會(huì)變成0xFFFFFFFF，而進(jìn)入死循環(huán)
所以有變種算法，為了避免陷入死循環(huán)，可以不移動(dòng)數(shù)字n，改為移動(dòng)數(shù)字1，跟n進(jìn)行比較。
還有一個(gè)就是解題思路中的辦法：
16、數(shù)字的整數(shù)次方? 馬上解題
題目描述
給定一個(gè) double 類(lèi)型的浮點(diǎn)數(shù) base 和 int 類(lèi)型的整數(shù) exponent，求 base 的 exponent 次方。
解題思路
下面的討論中 x 代表 base，n 代表 exponent。
因?yàn)?(x*x)n/2?可以通過(guò)遞歸求解，并且每次遞歸 n 都減小一半，因此整個(gè)算法的時(shí)間復(fù)雜度為 O(logN)。
代碼
17、打印從 1 到最大的 n 位數(shù)
題目描述
輸入數(shù)字 n，按順序打印出從 1 到最大的 n 位十進(jìn)制數(shù)。比如輸入 3，則打印出 1、2、3 一直到最大的 3 位數(shù)即 999。
解題思路
由于 n 可能會(huì)非常大，因此不能直接用 int 表示數(shù)字，而是用 char 數(shù)組進(jìn)行存儲(chǔ)。
使用回溯法得到所有的數(shù)。
代碼
18.1 在 O(1) 時(shí)間內(nèi)刪除鏈表節(jié)點(diǎn)
解題思路
① 如果該節(jié)點(diǎn)不是尾節(jié)點(diǎn)，那么可以直接將下一個(gè)節(jié)點(diǎn)的值賦給該節(jié)點(diǎn)，然后令該節(jié)點(diǎn)指向下下個(gè)節(jié)點(diǎn)，再刪除下一個(gè)節(jié)點(diǎn)，時(shí)間復(fù)雜度為 O(1)。
② 否則，就需要先遍歷鏈表，找到節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，然后讓前一個(gè)節(jié)點(diǎn)指向 null，時(shí)間復(fù)雜度為 O(N)。
綜上，如果進(jìn)行 N 次操作，那么大約需要操作節(jié)點(diǎn)的次數(shù)為 N-1+N=2N-1，其中 N-1 表示 N-1 個(gè)不是尾節(jié)點(diǎn)的每個(gè)節(jié)點(diǎn)以 O(1) 的時(shí)間復(fù)雜度操作節(jié)點(diǎn)的總次數(shù)，N 表示 1 個(gè)尾節(jié)點(diǎn)以 O(N) 的時(shí)間復(fù)雜度操作節(jié)點(diǎn)的總次數(shù)。(2N-1)/N ~ 2，因此該算法的平均時(shí)間復(fù)雜度為 O(1)。
18.2 刪除鏈表中重復(fù)的結(jié)點(diǎn)? 馬上解題
題目描述
代碼
19 正則表達(dá)式匹配? 馬上解題
題目描述
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)用來(lái)匹配包括 '.' 和 '*' 的正則表達(dá)式。模式中的字符 '.' 表示任意一個(gè)字符，而 '*' 表示它前面的字符可以出現(xiàn)任意次（包含 0 次）。
在本題中，匹配是指字符串的所有字符匹配整個(gè)模式。例如，字符串 "aaa" 與模式 "a.a" 和 "ab*ac*a" 匹配，但是與 "aa.a" 和 "ab*a" 均不匹配。
解題思路
應(yīng)該注意到，'.' 是用來(lái)當(dāng)做一個(gè)任意字符，而 '*' 是用來(lái)重復(fù)前面的字符。這兩個(gè)的作用不同，不能把 '.' 的作用和 '*' 進(jìn)行類(lèi)比，從而把它當(dāng)成重復(fù)前面字符一次。
代碼
