本部分主要是 CavsZhouyou 在練習(xí)《劍指 Offer》時(shí)所做的筆記，主要涉及算法相關(guān)知識(shí)和一些相關(guān)面試題時(shí)所做的筆記，分享這份總結(jié)給大家，幫助大家對(duì)算法的可以來(lái)一次全方位的檢漏和排查，感謝原作者 CavsZhouyou 的付出，原文鏈接放在文章最下方，如果出現(xiàn)錯(cuò)誤，希望大家共同指出！

1. 二維數(shù)組中的查找

題目：
在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的
一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。 

思路：

（1）第一種方式是使用兩層循環(huán)依次遍歷，判斷是否含有該整數(shù)。這一種方式最壞情況下的時(shí)間復(fù)雜度為 O(n^2)。

（2）第二種方式是利用遞增序列的特點(diǎn)，我們可以從二維數(shù)組的右上角開(kāi)始遍歷。如果當(dāng)前數(shù)值比所求的數(shù)要小，則將位置向下移動(dòng)
，再進(jìn)行判斷。如果當(dāng)前數(shù)值比所求的數(shù)要大，則將位置向左移動(dòng)，再進(jìn)行判斷。這一種方式最壞情況下的時(shí)間復(fù)雜度為 O(n)。

2. 替換空格

題目：

請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，將一個(gè)字符串中的空格替換成“%20”。例如，當(dāng)字符串為 We Are Happy.則經(jīng)過(guò)替換之后的字符串為 We%20
Are%20Happy

思路：

使用正則表達(dá)式，結(jié)合字符串的 replace 方法將空格替換為 “%20”

str.replace(/\s/g,"%20") 

3. 從尾到頭打印鏈表

 題目：
輸入一個(gè)鏈表，從尾到頭打印鏈表每個(gè)節(jié)點(diǎn)的值。

思路：

利用棧來(lái)實(shí)現(xiàn)，首先根據(jù)頭結(jié)點(diǎn)以此遍歷鏈表節(jié)點(diǎn)，將節(jié)點(diǎn)加入到棧中。當(dāng)遍歷完成后，再將棧中元素彈出并打印，以此來(lái)實(shí)現(xiàn)。棧的
實(shí)現(xiàn)可以利用 Array 的 push 和 pop 方法來(lái)模擬。 

4. 重建二叉樹(shù)

 題目：

輸入某二叉樹(shù)的前序遍歷和中序遍歷的結(jié)果，請(qǐng)重建出該二叉樹(shù)。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸
入前序遍歷序列 {1,2,4,7,3,5,6,8} 和中序遍歷序列 {4,7,2,1,5,3,8,6}，則重建二叉樹(shù)并返回。

思路：

利用遞歸的思想來(lái)求解，首先先序序列中的第一個(gè)元素一定是根元素。然后我們?nèi)ブ行虮闅v中尋找到該元素的位置，找到后該元素的左
邊部分就是根節(jié)點(diǎn)的左子樹(shù)，右邊部分就是根節(jié)點(diǎn)的右子樹(shù)。因此我們可以分別截取對(duì)應(yīng)的部分進(jìn)行子樹(shù)的遞歸構(gòu)建。使用這種方式的
時(shí)間復(fù)雜度為 O(n)，空間復(fù)雜度為 O(logn)。 

5. 用兩個(gè)棧實(shí)現(xiàn)隊(duì)列

 題目：

用兩個(gè)棧來(lái)實(shí)現(xiàn)一個(gè)隊(duì)列，完成隊(duì)列的 Push 和 Pop 操作。

思路：

隊(duì)列的一個(gè)基本特點(diǎn)是，元素先進(jìn)先出。通過(guò)兩個(gè)棧來(lái)模擬時(shí)，首先我們將兩個(gè)棧分為棧 1 和棧 2。當(dāng)執(zhí)行隊(duì)列的 push 操作時(shí)，直接
將元素 push 進(jìn)棧 1 中。當(dāng)隊(duì)列執(zhí)行 pop 操作時(shí)，首先判斷棧 2 是否為空，如果不為空則直接 pop 元素。如果棧 2 為空，則將棧 1 中
的所有元素 pop 然后 push 到棧 2 中，然后再執(zhí)行棧 2 的 pop 操作。

擴(kuò)展：

當(dāng)使用兩個(gè)長(zhǎng)度不同的棧來(lái)模擬隊(duì)列時(shí)，隊(duì)列的最大長(zhǎng)度為較短棧的長(zhǎng)度的兩倍。 

6. 旋轉(zhuǎn)數(shù)組的最小數(shù)字

題目：

把一個(gè)數(shù)組最開(kāi)始的若干個(gè)元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。 輸入一個(gè)非遞減排序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的
最小元素。 例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小值為 1。NOTE：給出的所有元素都大于 0，若數(shù)組大
小為 0，請(qǐng)返回 0。

思路：

（1）我們輸入的是一個(gè)非遞減排序的數(shù)組的一個(gè)旋轉(zhuǎn)，因此原始數(shù)組的值遞增或者有重復(fù)。旋轉(zhuǎn)之后原始數(shù)組的值一定和一個(gè)值相
鄰，并且不滿足遞增關(guān)系。因此我們就可以進(jìn)行遍歷，找到不滿足遞增關(guān)系的一對(duì)值，后一個(gè)值就是旋轉(zhuǎn)數(shù)組的最小數(shù)字。

（2）二分法 

相關(guān)資料可以參考：
《旋轉(zhuǎn)數(shù)組的最小數(shù)字》

7. 斐波那契數(shù)列

 題目：

大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個(gè)整數(shù) n，請(qǐng)你輸出斐波那契數(shù)列的第 n 項(xiàng)。n<=39

思路：

斐波那契數(shù)列的規(guī)律是，第一項(xiàng)為 0，第二項(xiàng)為 1，第三項(xiàng)以后的值都等于前面兩項(xiàng)的和，因此我們可以通過(guò)循環(huán)的方式，不斷通過(guò)疊
加來(lái)實(shí)現(xiàn)第 n 項(xiàng)值的構(gòu)建。通過(guò)循環(huán)而不是遞歸的方式來(lái)實(shí)現(xiàn)，時(shí)間復(fù)雜度降為了 O(n)，空間復(fù)雜度為 O(1)。 

8. 跳臺(tái)階

 題目：

一只青蛙一次可以跳上 1 級(jí)臺(tái)階，也可以跳上 2 級(jí)。求該青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法。

思路：

跳臺(tái)階的問(wèn)題是一個(gè)動(dòng)態(tài)規(guī)劃的問(wèn)題，由于一次只能夠跳 1 級(jí)或者 2 級(jí)，因此跳上 n 級(jí)臺(tái)階一共有兩種方案，一種是從 n-1 跳上，一
種是從 n-2 級(jí)跳上，因此 f(n) = f(n-1) + f(n-2)。

和斐波那契數(shù)列類似，不過(guò)初始兩項(xiàng)的值變?yōu)榱?nbsp;1 和 2，后面每項(xiàng)的值等于前面兩項(xiàng)的和。 

9. 變態(tài)跳臺(tái)階

題目：

一只青蛙一次可以跳上 1 級(jí)臺(tái)階，也可以跳上 2 級(jí)……它也可以跳上 n 級(jí)。求該青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法。

思路：

變態(tài)跳臺(tái)階的問(wèn)題同上一個(gè)問(wèn)題的思考方案是一樣的，我們可以得到一個(gè)結(jié)論是，每一項(xiàng)的值都等于前面所有項(xiàng)的值的和。

f(1) = 1
f(2) = f(2-1) + f(2-2) //f(2-2) 表示 2 階一次跳 2 階的次數(shù)。
f(3) = f(3-1) + f(3-2) + f(3-3)
...
f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-(n-1)) + f(n-n)

再次總結(jié)可得

 | 1 ,(n=0 )
f(n) =  | 1 ,(n=1 )
        | 2\*f(n-1),(n>=2)

10. 矩形覆蓋

題目：

我們可以用 2*1 的小矩形橫著或者豎著去覆蓋更大的矩形。請(qǐng)問(wèn)用 n 個(gè) 2*1 的小矩形無(wú)重疊地覆蓋一個(gè) 2\*n 的大矩形，總共
有多少種方法？

思路：

依舊是斐波那契數(shù)列的應(yīng)用 

11. 二進(jìn)制中 1 的個(gè)數(shù)

 題目：

輸入一個(gè)整數(shù)，輸出該數(shù)二進(jìn)制表示中 1 的個(gè)數(shù)。其中負(fù)數(shù)用補(bǔ)碼表示。

思路：

一個(gè)不為 0 的整數(shù)的二進(jìn)制表示，一定會(huì)有一位為 1。我們找到最右邊的一位 1，當(dāng)我們將整數(shù)減去 1 時(shí)，最右邊的一位 1 變?yōu)?nbsp;0，它后
面的所有位都取反，因此將減一后的值與原值相與，我們就會(huì)能夠消除最右邊的一位 1。因此判斷一個(gè)二進(jìn)制中 1 的個(gè)數(shù)，我們可以判
斷這個(gè)數(shù)可以經(jīng)歷多少次這樣的過(guò)程。

如：1100&1011=1000 

12. 數(shù)值的整數(shù)次方

 題目：

給定一個(gè) double 類型的浮點(diǎn)數(shù) base 和 int 類型的整數(shù) exponent。求 base 的 exponent 次方。

思路：

首先我們需要判斷 exponent 正負(fù)和零取值三種情況，根據(jù)不同的情況通過(guò)遞歸來(lái)實(shí)現(xiàn)。 

13. 調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面

 題目：

輸入一個(gè)整數(shù)數(shù)組，實(shí)現(xiàn)一個(gè)函數(shù)來(lái)調(diào)整該數(shù)組中數(shù)字的順序，使得所有的奇數(shù)位于數(shù)組的前半部分，所有的偶數(shù)位于位于數(shù)組的后半
部分，并保證奇數(shù)和奇數(shù)，偶數(shù)和偶數(shù)之間的相對(duì)位置不變。

思路：

由于需要考慮到調(diào)整之后的穩(wěn)定性，因此我們可以使用輔助數(shù)組的方式。首先對(duì)數(shù)組中的元素進(jìn)行遍歷，每遇到一個(gè)奇數(shù)就將它加入到
奇數(shù)輔助數(shù)組中，每遇到一個(gè)偶數(shù)，就將它將入到偶數(shù)輔助數(shù)組中。最后再將兩個(gè)數(shù)組合并。這一種方法的時(shí)間復(fù)雜度為 O(n)，空間
復(fù)雜度為 O(n)。 

14. 鏈表中倒數(shù)第 k 個(gè)節(jié)點(diǎn)

 題目：

輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第 k 個(gè)結(jié)點(diǎn)。

思路：

使用兩個(gè)指針，先讓第一個(gè)和第二個(gè)指針都指向頭結(jié)點(diǎn)，然后再讓第二個(gè)指針走 k-1 步，到達(dá)第 k 個(gè)節(jié)點(diǎn)。然后兩個(gè)指針同時(shí)向后
移動(dòng)，當(dāng)?shù)诙€(gè)指針到達(dá)末尾時(shí)，第一個(gè)指針指向的就是倒數(shù)第 k 個(gè)節(jié)點(diǎn)了。 

15. 反轉(zhuǎn)鏈表

 題目：

輸入一個(gè)鏈表，反轉(zhuǎn)鏈表后，輸出鏈表的所有元素。

思路：

通過(guò)設(shè)置三個(gè)變量 pre、current 和 next，分別用來(lái)保存前繼節(jié)點(diǎn)、當(dāng)前節(jié)點(diǎn)和后繼結(jié)點(diǎn)。從第一個(gè)節(jié)點(diǎn)開(kāi)始向后遍歷，首先將當(dāng)
前節(jié)點(diǎn)的后繼節(jié)點(diǎn)保存到 next 中，然后將當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)設(shè)置為 pre，然后再將 pre 設(shè)置為當(dāng)前節(jié)點(diǎn)，current 設(shè)置為 ne
xt 節(jié)點(diǎn)，實(shí)現(xiàn)下一次循環(huán)。 

16. 合并兩個(gè)排序的鏈表

 題目：

輸入兩個(gè)單調(diào)遞增的鏈表，輸出兩個(gè)鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。

思路：

通過(guò)遞歸的方式，依次將兩個(gè)鏈表的元素遞歸進(jìn)行對(duì)比。 

17. 樹(shù)的子結(jié)構(gòu)

 題目：

輸入兩棵二叉樹(shù) A、B，判斷 B 是不是 A 的子結(jié)構(gòu)。（ps：我們約定空樹(shù)不是任意一個(gè)樹(shù)的子結(jié)構(gòu)）

思路：

通過(guò)遞歸的思想來(lái)解決

第一步首先從樹(shù) A 的根節(jié)點(diǎn)開(kāi)始遍歷，在左右子樹(shù)中找到和樹(shù) B 根結(jié)點(diǎn)的值一樣的結(jié)點(diǎn) R 。
第二步兩棵樹(shù)同時(shí)從 R 節(jié)點(diǎn)和根節(jié)點(diǎn)以相同的遍歷方式進(jìn)行遍歷，依次比較對(duì)應(yīng)的值是否相同，當(dāng)樹(shù) B 遍歷結(jié)束時(shí)，結(jié)束比較。 

18. 二叉樹(shù)的鏡像

 題目：

操作給定的二叉樹(shù)，將其變換為源二叉樹(shù)的鏡像。

思路：

從根節(jié)點(diǎn)開(kāi)始遍歷，首先通過(guò)臨時(shí)變量保存左子樹(shù)的引用，然后將根節(jié)點(diǎn)的左右子樹(shù)的引用交換。然后再遞歸左右節(jié)點(diǎn)的子樹(shù)交換。 

19. 順時(shí)針打印矩陣

 題目：

輸入一個(gè)矩陣，按照從外向里以順時(shí)針的順序依次打印出每一個(gè)數(shù)字，
例如，如果輸入如下矩陣： 1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
則依次打印出數(shù)字 1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10

思路：

（1）根據(jù)左上角和右下角可以定位出一次要旋轉(zhuǎn)打印的數(shù)據(jù)。一次旋轉(zhuǎn)打印結(jié)束后，往對(duì)角分別前進(jìn)和后退一個(gè)單位，可以確定下一
次需要打印的數(shù)據(jù)范圍。

（2）使用模擬魔方逆時(shí)針解法，每打印一行，則將矩陣逆時(shí)針旋轉(zhuǎn) 90 度，打印下一行，依次重復(fù)。 

20. 定義一個(gè)棧，實(shí)現(xiàn) min 函數(shù)

 題目：

定義棧的數(shù)據(jù)結(jié)構(gòu)，請(qǐng)?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧最小元素的 min 函數(shù)。

思路：

使用一個(gè)輔助棧，每次將數(shù)據(jù)壓入數(shù)據(jù)棧時(shí)，就把當(dāng)前棧里面最小的值壓入輔助棧當(dāng)中。這樣輔助棧的棧頂數(shù)據(jù)一直是數(shù)據(jù)棧中最小
的值。 

21. 棧的壓入彈出

 題目：

輸入兩個(gè)整數(shù)序列，第一個(gè)序列表示棧的壓入順序，請(qǐng)判斷第二個(gè)序列是否為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等。例如
序列 1,2,3,4,5 是某棧的壓入順序，序列 4,5,3,2,1 是該壓棧序列對(duì)應(yīng)的一個(gè)彈出序列，但 4,3,5,1,2 就不可能是該壓棧序
列的彈出序列。（注意：這兩個(gè)序列的長(zhǎng)度是相等的）

思路：

我們可以使用一個(gè)輔助棧的方式來(lái)實(shí)現(xiàn)，首先遍歷壓棧順序，依次將元素壓入輔助棧中，每次壓入元素后我們首先判斷該元素是否與出
棧順序中的此刻位置的元素相等，如果不相等，則將元素繼續(xù)壓棧，如果相等，則將輔助棧中的棧頂元素出棧，出棧后，將出棧順序中
的位置后移一位繼續(xù)比較。當(dāng)壓棧順序遍歷完成后，如果輔助棧不為空，則說(shuō)明該出棧順序不正確。 

22. 從上往下打印二叉樹(shù)

 題目：

從上往下打印出二叉樹(shù)的每個(gè)節(jié)點(diǎn)，同層節(jié)點(diǎn)從左至右打印。

思路：

本質(zhì)上是二叉樹(shù)的層序遍歷，可以通過(guò)隊(duì)列來(lái)實(shí)現(xiàn)。首先將根節(jié)點(diǎn)入隊(duì)。然后對(duì)隊(duì)列進(jìn)行出隊(duì)操作，每次出隊(duì)時(shí)，將出隊(duì)元素的左右子
節(jié)點(diǎn)依次加入到隊(duì)列中，直到隊(duì)列長(zhǎng)度變?yōu)?nbsp;0 時(shí)，結(jié)束遍歷。 

23. 二叉搜索樹(shù)的后序遍歷

 題目：

輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹(shù)的后序遍歷的結(jié)果。如果是則輸出 Yes，否則輸出 No。假設(shè)輸入的數(shù)組的任意兩
個(gè)數(shù)字都互不相同。

思路：

對(duì)于一個(gè)合法而二叉樹(shù)的后序遍歷來(lái)說(shuō)，最末尾的元素為根元素。該元素前面的元素可以劃分為兩個(gè)部分，一部分為該元素的左子樹(shù)，
所有元素的值比根元素小，一部分為該元素的右子樹(shù)，所有的元素的值比該根元素大。并且每一部分都是一個(gè)合法的后序序列，因此我
們可以利用這些特點(diǎn)來(lái)遞歸判斷。 

24. 二叉樹(shù)中和為某一值路徑

 題目：

輸入一顆二叉樹(shù)和一個(gè)整數(shù)，打印出二叉樹(shù)中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。路徑定義為從樹(shù)的根結(jié)點(diǎn)開(kāi)始往下一直到葉結(jié)點(diǎn)所經(jīng)
過(guò)的結(jié)點(diǎn)形成一條路徑。

思路：

通過(guò)對(duì)樹(shù)進(jìn)行深度優(yōu)先遍歷，遍歷時(shí)保存當(dāng)前節(jié)點(diǎn)的值并判斷是否和期望值相等，如果遍歷到葉節(jié)點(diǎn)不符合要求則回退處理。 

25. 復(fù)雜鏈表的復(fù)制

 題目：

輸入一個(gè)復(fù)雜鏈表（每個(gè)節(jié)點(diǎn)中有節(jié)點(diǎn)值，以及兩個(gè)指針，一個(gè)指向下一個(gè)節(jié)點(diǎn)，另一個(gè)特殊指針指向任意一個(gè)節(jié)點(diǎn)），返回結(jié)果為
復(fù)制后復(fù)雜鏈表的 head。（注意，輸出結(jié)果中請(qǐng)不要返回參數(shù)中的節(jié)點(diǎn)引用，否則判題程序會(huì)直接返回空）

思路：

（1）第一種方式，首先對(duì)原有鏈表每個(gè)節(jié)點(diǎn)進(jìn)行復(fù)制，通過(guò) next 連接起來(lái)。然后當(dāng)鏈表復(fù)制完成之后，再來(lái)設(shè)置每個(gè)節(jié)點(diǎn)的 ra
ndom 指針，這個(gè)時(shí)候每個(gè)節(jié)點(diǎn)的 random 的設(shè)置都需要從頭結(jié)點(diǎn)開(kāi)始遍歷，因此時(shí)間的復(fù)雜度為 O(n^2)。

（2）第二種方式，首先對(duì)原有鏈表每個(gè)節(jié)點(diǎn)進(jìn)行復(fù)制，并且使用 Map 以鍵值對(duì)的方式將原有節(jié)點(diǎn)和復(fù)制節(jié)點(diǎn)保存下來(lái)。當(dāng)鏈表復(fù)
制完成之后，再來(lái)設(shè)置每個(gè)節(jié)點(diǎn)的 random 指針，這個(gè)時(shí)候我們通過(guò) Map 中的鍵值關(guān)系就可以獲取到對(duì)應(yīng)的復(fù)制節(jié)點(diǎn)，因此
不必再?gòu)念^結(jié)點(diǎn)遍歷，將時(shí)間的復(fù)雜度降低為了 O(n)，但是空間復(fù)雜度變?yōu)榱?O(n)。這是一種以空間換時(shí)間的做法。

（3）第三種方式，首先對(duì)原有鏈表的每個(gè)節(jié)點(diǎn)進(jìn)行復(fù)制，并將復(fù)制后的節(jié)點(diǎn)加入到原有節(jié)點(diǎn)的后面。當(dāng)鏈表復(fù)制完成之后，再進(jìn)行
random 指針的設(shè)置，由于每個(gè)節(jié)點(diǎn)后面都跟著自己的復(fù)制節(jié)點(diǎn)，因此我們可以很容易的獲取到 random 指向?qū)?yīng)的復(fù)制節(jié)點(diǎn)
。最后再將鏈表分離，通過(guò)這種方法我們也能夠?qū)r(shí)間復(fù)雜度降低為 O(n)。 

26. 二叉搜索樹(shù)與雙向鏈表

 題目：

輸入一棵二叉搜索樹(shù)，將該二叉搜索樹(shù)轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只能調(diào)整樹(shù)中結(jié)點(diǎn)指針的指向。

思路：

需要生成一個(gè)排序的雙向列表，那么我們應(yīng)該通過(guò)中序遍歷的方式來(lái)調(diào)整樹(shù)結(jié)構(gòu)，因?yàn)橹挥兄行虮闅v，返回才是一個(gè)從小到大的排序
序列。

基本的思路是我們首先從根節(jié)點(diǎn)開(kāi)始遍歷，先將左子樹(shù)調(diào)整為一個(gè)雙向鏈表，并將左子樹(shù)雙向鏈表的末尾元素的指針指向根節(jié)點(diǎn)，并
將根節(jié)點(diǎn)的左節(jié)點(diǎn)指向末尾節(jié)點(diǎn)。再將右子樹(shù)調(diào)整為一個(gè)雙向鏈表，并將右子樹(shù)雙向鏈表的首部元素的指針指向根元素，再將根節(jié)點(diǎn)
的右節(jié)點(diǎn)指向首部節(jié)點(diǎn)。通過(guò)對(duì)左右子樹(shù)遞歸調(diào)整，因此來(lái)實(shí)現(xiàn)排序的雙向鏈表的構(gòu)建。 

27. 字符串的排列

 題目：

輸入一個(gè)字符串，按字典序打印出該字符串中字符的所有排列。例如輸入字符串 abc，則打印出由字符 a,b,c 所能排列出來(lái)的所有
字符串 abc,acb,bac,bca,cab 和 cba。輸入描述：輸入一個(gè)字符串，長(zhǎng)度不超過(guò) 9（可能有字符重復(fù)），字符只包括大小寫(xiě)字母。

思路：

我們可以把一個(gè)字符串看做是兩個(gè)部分，第一部分為它的第一個(gè)字符，第二部分是它后面的所有字符。求整個(gè)字符串的一個(gè)全排列，可
以看做兩步，第一步是求所有可能出現(xiàn)在第一個(gè)位置的字符，即把第一個(gè)字符和后面的所有字符交換。第二步就是求后面所有字符的一
個(gè)全排列。因此通過(guò)這種方式，我們可以以遞歸的思路來(lái)求出當(dāng)前字符串的全排列。 

詳細(xì)資料可以參考：
《字符串的排列》

28. 數(shù)組中出現(xiàn)次數(shù)超過(guò)一半的數(shù)字

 題目：

數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過(guò)數(shù)組長(zhǎng)度的一半。請(qǐng)找出這個(gè)數(shù)字。例如輸入一個(gè)長(zhǎng)度為 9 的數(shù)組{1,2,3,2,2,2,5,4,2}。由于數(shù)
字 2 在數(shù)組中出現(xiàn)了 5 次，超過(guò)數(shù)組長(zhǎng)度的一半，因此輸出 2。如果不存在則輸出 0。

思路：

（1）對(duì)數(shù)組進(jìn)行排序，排序后的中位數(shù)就是所求數(shù)字。這種方法的時(shí)間復(fù)雜度取決于我們采用的排序方法的時(shí)間復(fù)雜度，因此最快為
O(nlogn)。

（2）由于所求數(shù)字的數(shù)量超過(guò)了數(shù)組長(zhǎng)度的一半，因此排序后的中位數(shù)就是所求數(shù)字。因此我們可以將問(wèn)題簡(jiǎn)化為求一個(gè)數(shù)組的中
位數(shù)問(wèn)題。其實(shí)數(shù)組并不需要全排序，只需要部分排序。我們通過(guò)利用快排中的 partition 函數(shù)來(lái)實(shí)現(xiàn)，我們現(xiàn)在數(shù)組中隨
機(jī)選取一個(gè)數(shù)字，而后通過(guò) partition 函數(shù)返回該數(shù)字在數(shù)組中的索引 index，如果 index 剛好等于 n/2，則這個(gè)數(shù)字
便是數(shù)組的中位數(shù)，也即是要求的數(shù)，如果 index 大于 n/2，則中位數(shù)肯定在 index 的左邊，在左邊繼續(xù)尋找即可，反之
在右邊尋找。這樣可以只在 index 的一邊尋找，而不用兩邊都排序，減少了一半排序時(shí)間，這種方法的時(shí)間復(fù)雜度為 O(n)。

（3）由于該數(shù)字的出現(xiàn)次數(shù)比所有其他數(shù)字出現(xiàn)次數(shù)的和還要多，因此可以考慮在遍歷數(shù)組時(shí)保存兩個(gè)值：一個(gè)是數(shù)組中的一個(gè)數(shù)
字，一個(gè)是次數(shù)。當(dāng)遍歷到下一個(gè)數(shù)字時(shí)，如果下一個(gè)數(shù)字與之前保存的數(shù)字相同，則次數(shù)加 1，如果不同，則次數(shù)減 1，如果
次數(shù)為 0，則需要保存下一個(gè)數(shù)字，并把次數(shù)設(shè)定為 1。由于我們要找的數(shù)字出現(xiàn)的次數(shù)比其他所有數(shù)字的出現(xiàn)次數(shù)之和還要大，
則要找的數(shù)字肯定是最后一次把次數(shù)設(shè)為 1 時(shí)對(duì)應(yīng)的數(shù)字。該方法的時(shí)間復(fù)雜度為 O(n)，空間復(fù)雜度為 O(1)。 

詳細(xì)資料可以參考：
《出現(xiàn)次數(shù)超過(guò)一半的數(shù)字》

29. 最小的 K 個(gè)數(shù)

 題目：

輸入 n 個(gè)整數(shù)，找出其中最小的 K 個(gè)數(shù)。例如輸入 4,5,1,6,2,7,3,8 這 8 個(gè)數(shù)字，則最小的 4 個(gè)數(shù)字是 1,2,3,4 。

思路：

（1）第一種思路是首先將數(shù)組排序，排序后再取最小的 k 個(gè)數(shù)。這一種方法的時(shí)間復(fù)雜度取決于我們選擇的排序算法的時(shí)間復(fù)雜
度，最好的情況下為 O(nlogn)。

（2）第二種思路是由于我們只需要獲得最小的 k 個(gè)數(shù)，這 k 個(gè)數(shù)不一定是按序排序的。因此我們可以使用快速排序中的 part
ition 函數(shù)來(lái)實(shí)現(xiàn)。每一次選擇一個(gè)樞紐值，將數(shù)組分為比樞紐值大和比樞紐值小的兩個(gè)部分，判斷樞紐值的位置，如果該樞
紐值的位置為 k-1 的話，那么樞紐值和它前面的所有數(shù)字就是最小的 k 個(gè)數(shù)。如果樞紐值的位置小于 k-1 的話，假設(shè)樞
紐值的位置為 n-1，那么我們已經(jīng)找到了前 n 小的數(shù)字了，我們就還需要到后半部分去尋找后半部分 k-n 小的值，進(jìn)行劃
分。當(dāng)該樞紐值的位置比 k-1 大時(shí)，說(shuō)明最小的 k 個(gè)值還在左半部分，我們需要繼續(xù)對(duì)左半部分進(jìn)行劃分。這一種方法的平
均時(shí)間復(fù)雜度為 O(n)。

（3）第三種方法是維護(hù)一個(gè)容量為 k 的最大堆。對(duì)數(shù)組進(jìn)行遍歷時(shí)，如果堆的容量還沒(méi)有達(dá)到 k ，則直接將元素加入到堆中，這
就相當(dāng)于我們假設(shè)前 k 個(gè)數(shù)就是最小的 k 個(gè)數(shù)。對(duì) k 以后的元素遍歷時(shí)，我們將該元素與堆的最大值進(jìn)行比較，如果比最
大值小，那么我們則將最大值與其交換，然后調(diào)整堆。如果大于等于堆的最大值，則繼續(xù)向后遍歷，直到數(shù)組遍歷完成。這一
種方法的平均時(shí)間復(fù)雜度為 O(nlogk)。 

詳細(xì)資料可以參考：
《尋找最小的 k 個(gè)數(shù)》

30. 連續(xù)子數(shù)組的最大和

 題目：

HZ 偶爾會(huì)拿些專業(yè)問(wèn)題來(lái)忽悠那些非計(jì)算機(jī)專業(yè)的同學(xué)。今天測(cè)試組開(kāi)完會(huì)后，他又發(fā)話了:在古老的一維模式識(shí)別中，常常需要計(jì)
算連續(xù)子向量的最大和,當(dāng)向量全為正數(shù)的時(shí)候，問(wèn)題很好解決。但是，如果向量中包含負(fù)數(shù)，是否應(yīng)該包含某個(gè)負(fù)數(shù)，并期望旁邊的
正數(shù)會(huì)彌補(bǔ)它呢？例如：{6,-3,-2,7,-15,1,2,2}，連續(xù)子向量的最大和為 8（從第 0 個(gè)開(kāi)始，到第 3 個(gè)為止）。你會(huì)不會(huì)被他忽悠
??？（子向量的長(zhǎng)度至少是 1）

思路：

（1）第一種思路是直接暴力求解的方式，先以第一個(gè)數(shù)字為首往后開(kāi)始疊加，疊加的過(guò)程中保存最大的值。然后再以第二個(gè)數(shù)字為首
往后開(kāi)始疊加，并與先前保存的最大的值進(jìn)行比較。這一種方法的時(shí)間復(fù)雜度為 O(n^2)。

（2）第二種思路是，首先我們觀察一個(gè)最大和的連續(xù)數(shù)組的規(guī)律，我們可以發(fā)現(xiàn)，子數(shù)組一定是以正數(shù)開(kāi)頭的，中間包含了正負(fù)數(shù)。
因此我們可以從第一個(gè)數(shù)開(kāi)始向后疊加，每次保存最大的值。疊加的值如果為負(fù)數(shù)，則將疊加值初始化為 0，因?yàn)楹竺娴臄?shù)加上負(fù)
數(shù)只會(huì)更小，因此需要尋找下一個(gè)正數(shù)開(kāi)始下一個(gè)子數(shù)組的判斷。一直往后判斷，直到這個(gè)數(shù)組遍歷完成為止，得到最大的值。
使用這一種方法的時(shí)間復(fù)雜度為 O(n)。 

詳細(xì)資料可以參考：
《連續(xù)子數(shù)組的最大和》

31. 整數(shù)中 1 出現(xiàn)的次數(shù)（待深入理解）

 題目：

求出 1~13 的整數(shù)中 1 出現(xiàn)的次數(shù)，并算出 100~1# 300 的整數(shù)中 1 出現(xiàn)的次數(shù)？為此他特別數(shù)了一下 1~13 中包含 1 的數(shù)字有 1、10、11、
12、13 因此共出現(xiàn) 6 次，但是對(duì)于后面問(wèn)題他就沒(méi)轍了。ACMer 希望你們幫幫他，并把問(wèn)題更加普遍化，可以很快的求出任意非負(fù)整
數(shù)區(qū)間中 1 出現(xiàn)的次數(shù)。

思路：

（1）第一種思路是直接遍歷每個(gè)數(shù)，然后將判斷每個(gè)數(shù)中 1 的個(gè)數(shù)，一直疊加。

（2）第二種思路是求出 1 出現(xiàn)在每位上的次數(shù)，然后進(jìn)行疊加。 

詳細(xì)資料可以參考：
《從 1 到 n 整數(shù)中 1 出現(xiàn)的次數(shù)：O(logn)算法》

32. 把數(shù)組排成最小的數(shù)

 題目：

輸入一個(gè)正整數(shù)數(shù)組，把數(shù)組里所有數(shù)字拼接起來(lái)排成一個(gè)數(shù)，打印能拼接出的所有數(shù)字中最小的一個(gè)。例如輸入數(shù)組{3，32，321
}，則打印出這三個(gè)數(shù)字能排成的最小數(shù)字為 321323。

思路：

（1）求出數(shù)組的全排列，然后對(duì)每個(gè)排列結(jié)果進(jìn)行比較。

（2）利用排序算法實(shí)現(xiàn)，但是比較時(shí)，比較的并不是兩個(gè)元素的大小，而是兩個(gè)元素正序拼接和逆序拼接的大小，如果逆序拼接的
結(jié)果更小，則交換兩個(gè)元素的位置。排序結(jié)束后，數(shù)組的順序則為最小數(shù)的排列組合順序。 

詳細(xì)資料可以參考：
《把數(shù)組排成最小的數(shù)》

33. 丑數(shù)（待深入理解）

 題目：

把只包含質(zhì)因子 2、3 和 5 的數(shù)稱作丑數(shù)。例如 6、8 都是丑數(shù)，但 14 不是，因?yàn)樗蜃?nbsp;7。 習(xí)慣上我們把 1 當(dāng)做是第一個(gè)丑數(shù)。求
按從小到大的順序的第 N 個(gè)丑數(shù)。

思路：

（1）判斷一個(gè)數(shù)是否為丑數(shù)，可以判斷該數(shù)不斷除以 2，最后余數(shù)是否為 1。判斷該數(shù)不斷除以 3，最后余數(shù)是否為 1。判斷不斷除以
5，最后余數(shù)是否為 1。在不考慮時(shí)間復(fù)雜度的情況下，可以依次遍歷找到第 N 個(gè)丑數(shù)。

（2）使用一個(gè)數(shù)組來(lái)保存已排序好的丑數(shù)，后面的丑數(shù)由前面生成。 

34. 第一個(gè)只出現(xiàn)一次的字符

 題目：

在一個(gè)字符串（1<=字符串長(zhǎng)度<=10000，全部由大寫(xiě)字母組成）中找到第一個(gè)只出現(xiàn)一次的字符，并返回它的位置。

思路：

（1）第一種思路是，從前往后遍歷每一個(gè)字符。每遍歷一個(gè)字符，則將字符與后邊的所有字符依次比較，判斷是否含有相同字符。這
一種方法的時(shí)間復(fù)雜度為 O(n^2)。

（2）第二種思路是，首先對(duì)字符串進(jìn)行一次遍歷，將字符和字符出現(xiàn)的次數(shù)以鍵值對(duì)的形式存儲(chǔ)在 Map 結(jié)構(gòu)中。然后第二次遍歷時(shí)
，去 Map 中獲取對(duì)應(yīng)字符出現(xiàn)的次數(shù)，找到第一個(gè)只出現(xiàn)一次的字符。這一種方法的時(shí)間復(fù)雜度為 O(n)。 

35. 數(shù)組中的逆序?qū)?/span>

 題目：

在數(shù)組中的兩個(gè)數(shù)字，如果前面一個(gè)數(shù)字大于后面的數(shù)字，則這兩個(gè)數(shù)字組成一個(gè)逆序?qū)?。輸入一個(gè)數(shù)組，求出這個(gè)數(shù)組中的逆序?qū)?br>的總數(shù) P。

思路：

（1）第一種思路是直接求解的方式，順序掃描整個(gè)數(shù)組。每掃描到一個(gè)數(shù)字的時(shí)候，逐個(gè)比較該數(shù)字和它后面的數(shù)字的大小。如果
后面的數(shù)字比它小，則這兩個(gè)數(shù)字就組成了一個(gè)逆序?qū)?。假設(shè)數(shù)組中含有 n 個(gè)數(shù)字。由于每個(gè)數(shù)字都要和 O(n）個(gè)數(shù)字作比
較，因此這個(gè)算法的時(shí)間復(fù)雜度是 O(n^2)。

（2）第二種方式是使用歸并排序的方式，通過(guò)利用歸并排序分解后進(jìn)行合并排序時(shí)，來(lái)進(jìn)行逆序?qū)Φ慕y(tǒng)計(jì)，這一種方法的時(shí)間復(fù)雜
度為 O(nlogn)。 

詳細(xì)資料可以參考：
《數(shù)組中的逆序?qū)Α?/p>

36. 兩個(gè)鏈表的第一個(gè)公共結(jié)點(diǎn)

 題目：

輸入兩個(gè)鏈表，找出它們的第一個(gè)公共結(jié)點(diǎn)。

思路：

（1）第一種方法是在第一個(gè)鏈表上順序遍歷每個(gè)結(jié)點(diǎn)，每遍歷到一個(gè)結(jié)點(diǎn)的時(shí)候，在第二個(gè)鏈表上順序遍歷每個(gè)結(jié)點(diǎn)。如果在第二
個(gè)鏈表上有一個(gè)結(jié)點(diǎn)和第一個(gè)鏈表上的結(jié)點(diǎn)一樣，說(shuō)明兩個(gè)鏈表在這個(gè)結(jié)點(diǎn)上重合，于是就找到了它們的公共結(jié)點(diǎn)。如果第一
個(gè)鏈表的長(zhǎng)度為 m，第二個(gè)鏈表的長(zhǎng)度為 n。這一種方法的時(shí)間復(fù)雜度是 O(mn）。

（2）第二種方式是利用棧的方式，通過(guò)觀察我們可以發(fā)現(xiàn)兩個(gè)鏈表的公共節(jié)點(diǎn)，都位于鏈表的尾部，以此我們可以分別使用兩個(gè)棧
，依次將鏈表元素入棧。然后在兩個(gè)棧同時(shí)將元素出棧，比較出棧的節(jié)點(diǎn)，最后一個(gè)相同的節(jié)點(diǎn)就是我們要找的公共節(jié)點(diǎn)。這
一種方法的時(shí)間復(fù)雜度為 O(m+n)，空間復(fù)雜度為 O(m+n)。

（3）第三種方式是，首先分別遍歷兩個(gè)鏈表，得到兩個(gè)鏈表的長(zhǎng)度。然后得到較長(zhǎng)的鏈表與較短的鏈表長(zhǎng)度的差值。我們使用兩個(gè)
指針來(lái)分別對(duì)兩個(gè)鏈表進(jìn)行遍歷，首先將較長(zhǎng)鏈表的指針移動(dòng) n 步，n 為兩個(gè)鏈表長(zhǎng)度的差值，然后兩個(gè)指針再同時(shí)移動(dòng)，
判斷所指向節(jié)點(diǎn)是否為同一節(jié)點(diǎn)。這一種方法的時(shí)間復(fù)雜度為 O(m+n)，相同對(duì)于上一種方法不需要額外的空間。 

詳細(xì)資料可以參考：
《兩個(gè)鏈表的第一個(gè)公共結(jié)點(diǎn)》

37. 數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)

 題目：

統(tǒng)計(jì)一個(gè)數(shù)字：在排序數(shù)組中出現(xiàn)的次數(shù)。例如輸入排序數(shù)組｛ 1, 2, 3, 3, 3, 3, 4, 5｝和數(shù)字 3 ，由于 3 在這個(gè)數(shù)組中出
現(xiàn)了 4 次，因此輸出 4 。

思路：

（1）第一種方法是直接對(duì)數(shù)組順序遍歷的方式，通過(guò)這種方法來(lái)統(tǒng)計(jì)數(shù)字的出現(xiàn)次數(shù)。這種方法的時(shí)間復(fù)雜度為 O(n)。

（2）第二種方法是使用二分查找的方法，由于數(shù)組是排序好的數(shù)組，因此相同數(shù)字是排列在一起的。統(tǒng)計(jì)數(shù)字出現(xiàn)的次數(shù)，我們需要
去找到該段數(shù)字開(kāi)始和結(jié)束的位置，以此來(lái)確定數(shù)字出現(xiàn)的次數(shù)。因此我們可以使用二分查找的方式來(lái)確定該數(shù)字的開(kāi)始和結(jié)束
位置。如果我們第一次我們數(shù)組的中間值為 k ，如果 k 值比所求值大的話，那么我們下一次只需要判斷前面一部分就行了，如
果 k 值比所求值小的話，那么我們下一次就只需要判斷后面一部分就行了。如果 k 值等于所求值的時(shí)候，我們則需要判斷該值
是否為開(kāi)始位置或者結(jié)束位置。如果是開(kāi)始位置，那么我們下一次需要到后半部分去尋找結(jié)束位置。如果是結(jié)束位置，那么我們
下一次需要到前半部分去尋找開(kāi)始位置。如果既不是開(kāi)始位置也不是結(jié)束位置，那么我們就分別到前后兩個(gè)部分去尋找開(kāi)始和結(jié)
束位置。這一種方法的平均時(shí)間復(fù)雜度為 O(logn)。 

38. 二叉樹(shù)的深度

 題目：

輸入一棵二叉樹(shù)，求該樹(shù)的深度。從根結(jié)點(diǎn)到葉結(jié)點(diǎn)依次經(jīng)過(guò)的結(jié)點(diǎn)（含根、葉結(jié)點(diǎn)）形成樹(shù)的一條路徑，最長(zhǎng)路徑的長(zhǎng)度為樹(shù)的深
度。

思路：

根節(jié)點(diǎn)的深度等于左右深度較大值加一，因此可以通過(guò)遞歸遍歷來(lái)實(shí)現(xiàn)。 

39. 平衡二叉樹(shù)

 題目：

輸入一棵二叉樹(shù)，判斷該二叉樹(shù)是否是平衡二叉樹(shù)。

思路：

（1）在遍歷樹(shù)的每個(gè)結(jié)點(diǎn)的時(shí)候，調(diào)用函數(shù)得到它的左右子樹(shù)的深度。如果每個(gè)結(jié)點(diǎn)的左右子樹(shù)的深度相差都不超過(guò) 1 ，那么它
就是一棵平衡的二叉樹(shù)。使用這種方法時(shí)，節(jié)點(diǎn)會(huì)被多次遍歷，因此會(huì)造成效率不高的問(wèn)題。

（2）在求一個(gè)節(jié)點(diǎn)的深度時(shí)，同時(shí)判斷它是否平衡。如果不平衡則直接返回 -1，否則返回樹(shù)高度。如果一個(gè)節(jié)點(diǎn)的一個(gè)子樹(shù)的深
度為-1，那么就直接向上返回 -1 ，該樹(shù)已經(jīng)是不平衡的了。通過(guò)這種方式確保了節(jié)點(diǎn)只能夠被訪問(wèn)一遍。 

40. 數(shù)組中只出現(xiàn)一次的數(shù)字

 題目：

一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次。請(qǐng)寫(xiě)程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字。

思路：

（1）第一種方式是依次遍歷數(shù)組，記錄下數(shù)字出現(xiàn)的次數(shù)，從而找出兩個(gè)只出現(xiàn)一次的數(shù)字。

（2）第二種方式，根據(jù)位運(yùn)算的異或的性質(zhì)，我們可以知道兩個(gè)相同的數(shù)字異或等于 0，一個(gè)數(shù)和 0 異或還是它本身。由于數(shù)組中
的其他數(shù)字都是成對(duì)出現(xiàn)的，因此我們可以將數(shù)組中的所有數(shù)依次進(jìn)行異或運(yùn)算。如果只有一個(gè)數(shù)出現(xiàn)一次的話，那么最后剩下
的就是落單的數(shù)字。如果是兩個(gè)數(shù)只出現(xiàn)了一次的話，那么最后剩下的就是這兩個(gè)數(shù)異或的結(jié)果。這個(gè)結(jié)果中的 1 表示的是 A 和
B 不同的位。我們?nèi)‘惢蚪Y(jié)果的第一個(gè) 1 所在的位數(shù)，假如是第 3 位，接著通過(guò)比較第三位來(lái)將數(shù)組分為兩組，相同數(shù)字一定會(huì)
被分到同一組。分組完成后再按照依次異或的思路，求得剩余數(shù)字即為兩個(gè)只出現(xiàn)一次的數(shù)字。 

41. 和為 S 的連續(xù)正數(shù)序列

 題目：

小明很喜歡數(shù)學(xué)，有一天他在做數(shù)學(xué)作業(yè)時(shí)，要求計(jì)算出 9~16 的和，他馬上就寫(xiě)出了正確答案是 100。但是他并不滿足于此，他在想究
竟有多少種連續(xù)的正數(shù)序列的和為 100（至少包括兩個(gè)數(shù)）。沒(méi)多久，他就得到另一組連續(xù)正數(shù)和為 100 的序列：18,19,20,21,22。
現(xiàn)在把問(wèn)題交給你，你能不能也很快的找出所有和為 S 的連續(xù)正數(shù)序列？Good Luck!輸出描述：輸出所有和為 S 的連續(xù)正數(shù)序列。序
列內(nèi)按照從小至大的順序，序列間按照開(kāi)始數(shù)字從小到大的順序。

思路：

維護(hù)一個(gè)正數(shù)序列數(shù)組，數(shù)組中初始只含有值 1 和 2，然后從 3 依次往后遍歷，每遍歷到一個(gè)元素則將這個(gè)元素加入到序列數(shù)組中，然后
判斷此時(shí)序列數(shù)組的和。如果序列數(shù)組的和大于所求值，則將第一個(gè)元素（最小的元素彈出）。如果序列數(shù)組的和小于所求值，則繼續(xù)
往后遍歷，將元素加入到序列中繼續(xù)判斷。當(dāng)序列數(shù)組的和等于所求值時(shí)，打印出此時(shí)的正數(shù)序列，然后繼續(xù)往后遍歷，尋找下一個(gè)連
續(xù)序列，直到數(shù)組遍歷完成終止。 

詳細(xì)資料可以參考：
《和為 s 的連續(xù)正數(shù)序列》

42. 和為 S 的兩個(gè)數(shù)字

 題目：

輸入一個(gè)遞增排序的數(shù)組和一個(gè)數(shù)字 S，在數(shù)組中查找兩個(gè)數(shù)，是的他們的和正好是 S，如果有多對(duì)數(shù)字的和等于 S，輸出兩個(gè)數(shù)
的乘積最小的。輸出描述：對(duì)應(yīng)每個(gè)測(cè)試案例，輸出兩個(gè)數(shù)，小的先輸出。

思路：

首先我們通過(guò)規(guī)律可以發(fā)現(xiàn)，和相同的兩個(gè)數(shù)字，兩個(gè)數(shù)字的差值越大，乘積越小。因此我們只需要從數(shù)組的首尾開(kāi)始找到第一對(duì)和
為 s 的數(shù)字對(duì)進(jìn)行了。因此我們可以使用雙指針的方式，左指針初始指向數(shù)組的第一個(gè)元素，右指針初始指向數(shù)組的最后一個(gè)元素
。然后首先判斷兩個(gè)指針指向的數(shù)字的和是否為 s ，如果為 s ，兩個(gè)指針指向的數(shù)字就是我們需要尋找的數(shù)字對(duì)。如果兩數(shù)的和
比 s 小，則將左指針向左移動(dòng)一位后繼續(xù)判斷。如果兩數(shù)的和比 s 大，則將右指針向右移動(dòng)一位后繼續(xù)判斷。 

詳細(xì)資料可以參考：
《和為 S 的字符串》

43. 左旋轉(zhuǎn)字符串

 題目：

匯編語(yǔ)言中有一種移位指令叫做循環(huán)左移（ROL），現(xiàn)在有個(gè)簡(jiǎn)單的任務(wù)，就是用字符串模擬這個(gè)指令的運(yùn)算結(jié)果。對(duì)于一個(gè)給定的
字符序列 S，請(qǐng)你把其循環(huán)左移 K 位后的序列輸出。例如，字符序列 S=”abcXYZdef”，要求輸出循環(huán)左移 3 位后的結(jié)果，即 “X
YZdefabc”。是不是很簡(jiǎn)單？OK，搞定它！

思路：

字符串裁剪后拼接 

44. 翻轉(zhuǎn)單詞順序列

 題目：

?？妥罱鼇?lái)了一個(gè)新員工 Fish，每天早晨總是會(huì)拿著一本英文雜志，寫(xiě)些句子在本子上。同事 Cat 對(duì) Fish 寫(xiě)的內(nèi)容頗感興趣，有
一天他向 Fish 借來(lái)翻看，但卻讀不懂它的意思。例如，“student. a am I”。后來(lái)才意識(shí)到，這家伙原來(lái)把句子單詞的順序翻轉(zhuǎn)了
，正確的句子應(yīng)該是“I am a student.”。Cat 對(duì)一一的翻轉(zhuǎn)這些單詞順序可不在行，你能幫助他么？

思路：

通過(guò)空格將單詞分隔，然后將數(shù)組反序后，重新拼接為字符串。 

45. 撲克牌的順子

 題目：

LL 今天心情特別好，因?yàn)樗ベI了一副撲克牌，發(fā)現(xiàn)里面居然有 2 個(gè)大王，2 個(gè)小王（一副牌原本是 54 張^\_^）...他隨機(jī)從中抽出
了 5 張牌，想測(cè)測(cè)自己的手氣，看看能不能抽到順子，如果抽到的話，他決定去買體育彩票，嘿嘿?。　凹t心 A，黑桃 3，小王，大王
，方片 5”，“Oh My God!”不是順子..... LL 不高興了，他想了想，決定大\小王可以看成任何數(shù)字，并且 A 看作 1，J 為 11，
Q 為 12，K 為 13。上面的 5 張牌就可以變成“1,2,3,4,5”（大小王分別看作 2 和 4），“So Lucky!”。LL 決定去買體育彩票啦。
現(xiàn)在，要求你使用這幅牌模擬上面的過(guò)程，然后告訴我們 LL 的運(yùn)氣如何。為了方便起見(jiàn)，你可以認(rèn)為大小王是 0。

思路：

首先判斷 5 個(gè)數(shù)字是不是連續(xù)的，最直觀的方法是把數(shù)組排序。值得注意的是，由于 0 可以當(dāng)成任意數(shù)字，我們可以用 0 去補(bǔ)滿數(shù)
組中的空缺。如果排序之后的數(shù)組不是連續(xù)的，即相鄰的兩個(gè)數(shù)字相隔若干個(gè)數(shù)字，但只要我們有足夠的?？梢匝a(bǔ)滿這兩個(gè)數(shù)字的空
缺，這個(gè)數(shù)組實(shí)際上還是連續(xù)的。

于是我們需要做 3 件事情：首先把數(shù)組排序，再統(tǒng)計(jì)數(shù)組中 0 的個(gè)數(shù)，最后統(tǒng)計(jì)排序之后的數(shù)組中相鄰數(shù)字之間的空缺總數(shù)。如
果空缺的總數(shù)小于或者等于 0 的個(gè)數(shù)，那么這個(gè)數(shù)組就是連續(xù)的：反之則不連續(xù)。最后，我們還需要注意一點(diǎn)：如果數(shù)組中的非 0
數(shù)字重復(fù)出現(xiàn)，則該數(shù)組不是連續(xù)的。換成撲克牌的描述方式就是如果一副牌里含有對(duì)子，則不可能是順子。 

詳細(xì)資料可以參考：
《撲克牌的順子》

46. 圓圈中最后剩下的數(shù)字（約瑟夫環(huán)問(wèn)題）

 題目：

0, 1, … , n-1 這 n 個(gè)數(shù)字排成一個(gè)圈圈，從數(shù)字 0 開(kāi)始每次從圓圏里刪除第 m 個(gè)數(shù)字。求出這個(gè)圈圈里剩下的最后一個(gè)數(shù)
字。

思路：

（1）使用環(huán)形鏈表進(jìn)行模擬。

（2）根據(jù)規(guī)律得出（待深入理解） 

詳細(xì)資料可以參考：
《圓圈中最后剩下的數(shù)字》

47. 1+2+3+...+n

 題目：

求 1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case 等關(guān)鍵字及條件判斷語(yǔ)句（A?B:C）。

思路：

由于不能使用循環(huán)語(yǔ)句，因此我們可以通過(guò)遞歸來(lái)實(shí)現(xiàn)。并且由于不能夠使用條件判斷運(yùn)算符，我們可以利用 && 操作符的短路特
性來(lái)實(shí)現(xiàn)。 

48. 不用加減乘除做加法

 題目：

寫(xiě)一個(gè)函數(shù)，求兩個(gè)整數(shù)之和，要求在函數(shù)體內(nèi)不得使用 ＋、－、×、÷ 四則運(yùn)算符號(hào)。

思路：

通過(guò)位運(yùn)算，遞歸來(lái)實(shí)現(xiàn)。 

49. 把字符串轉(zhuǎn)換成整數(shù)。

 題目：

將一個(gè)字符串轉(zhuǎn)換成一個(gè)整數(shù)，要求不能使用字符串轉(zhuǎn)換整數(shù)的庫(kù)函數(shù)。數(shù)值為 0 或者字符串不是一個(gè)合法的數(shù)值則返回 0。輸入描
述：輸入一個(gè)字符串，包括數(shù)字字母符號(hào)，可以為空。輸出描述：如果是合法的數(shù)值表達(dá)則返回該數(shù)字，否則返回 0。

思路：

首先需要進(jìn)行符號(hào)判斷，其次我們根據(jù)字符串的每位通過(guò)減 0 運(yùn)算轉(zhuǎn)換為整數(shù)和，依次根據(jù)位數(shù)疊加。 

50. 數(shù)組中重復(fù)的數(shù)字

 題目：

在一個(gè)長(zhǎng)度為 n 的數(shù)組里的所有數(shù)字都在 0 到 n-1 的范圍內(nèi)。數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個(gè)數(shù)字重復(fù)了，也不知
道每個(gè)數(shù)字重復(fù)了幾次。請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字。

思路：

（1）首先將數(shù)組排序，排序后再進(jìn)行判斷。這一種方法的時(shí)間復(fù)雜度為 O(nlogn)。

（2）使用 Map 結(jié)構(gòu)的方式，依次記錄下每一個(gè)數(shù)字出現(xiàn)的次數(shù)，從而可以判斷是否出現(xiàn)重復(fù)數(shù)字。這一種方法的時(shí)間復(fù)雜度為 O
(n)，空間復(fù)雜度為 O(n)。

（3）從數(shù)組首部開(kāi)始遍歷，每遍歷一個(gè)數(shù)字，則將該數(shù)字和它的下標(biāo)相比較，如果數(shù)字和下標(biāo)不等，則將該數(shù)字和它對(duì)應(yīng)下標(biāo)的值
交換。如果對(duì)應(yīng)的下標(biāo)值上已經(jīng)是正確的值了，那么說(shuō)明當(dāng)前元素是一個(gè)重復(fù)數(shù)字。這一種方法相對(duì)于上一種方法來(lái)說(shuō)不需要
額外的內(nèi)存空間。 

51. 構(gòu)建乘積數(shù)組

 題目：

給定一個(gè)數(shù)組 A[0,1,...,n-1]，請(qǐng)構(gòu)建一個(gè)數(shù)組 B[0,1,...,n-1]，其中 B 中的元素 B[i]=A[0]_A[1]_...*A[i-1]*A
[i+1]*...*A[n-1]。不能使用除法。

思路：

（1）  C[i]=A[0]×A[1]×...×A[i-1]=C[i-1]×A[i-1]
      D[i]=A[i+1]×...×A[n-1]=D[i+1]×A[i+1]
      B[i]=C[i]×D[i]
       將乘積分為前后兩個(gè)部分，分別循環(huán)求出后，再進(jìn)行相乘。

（2）上面的方法需要額外的內(nèi)存空間，我們可以引入中間變量的方式，來(lái)降低空間復(fù)雜度。（待深入理解） 

詳細(xì)資料可以參考：
《構(gòu)建乘積數(shù)組》

52. 正則表達(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"均不匹配。

思路：

（1）狀態(tài)機(jī)思路（待深入理解） 

詳細(xì)資料可以參考：
《正則表達(dá)式匹配》

53. 表示數(shù)值的字符串

 題目：

請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)用來(lái)判斷字符串是否表示數(shù)值（包括整數(shù)和小數(shù)）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-
16"都表示數(shù)值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。、

思路：

利用正則表達(dá)式實(shí)現(xiàn) 

54. 字符流中第一個(gè)不重復(fù)的字符

 題目：

請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)用來(lái)找出字符流中第一個(gè)只出現(xiàn)一次的字符。例如，當(dāng)從字符流中只讀出前兩個(gè)字符 "go" 時(shí)，第一個(gè)只出現(xiàn)一次
的字符是 "g" 。當(dāng)從該字符流中讀出前六個(gè)字符 "google" 時(shí)，第一個(gè)只出現(xiàn)一次的字符是 "l"。 輸出描述：如果當(dāng)前字符流
沒(méi)有存在出現(xiàn)一次的字符，返回#字符。

思路：

同第 34 題 

55. 鏈表中環(huán)的入口結(jié)點(diǎn)

 題目：

一個(gè)鏈表中包含環(huán)，如何找出環(huán)的入口結(jié)點(diǎn)？

思路：

首先使用快慢指針的方式我們可以判斷鏈表中是否存在環(huán)，當(dāng)快慢指針相遇時(shí)，說(shuō)明鏈表中存在環(huán)。相遇點(diǎn)一定存在于環(huán)中，因此我
們可以從使用一個(gè)指針從這個(gè)點(diǎn)開(kāi)始向前移動(dòng)，每移動(dòng)一個(gè)點(diǎn)，環(huán)的長(zhǎng)度加一，當(dāng)指針再次回到這個(gè)點(diǎn)的時(shí)候，指針走了一圈，因此
通過(guò)這個(gè)方法我們可以得到鏈表中的環(huán)的長(zhǎng)度，我們將它記為 n 。

然后我們?cè)O(shè)置兩個(gè)指針，首先分別指向頭結(jié)點(diǎn)，然后將一個(gè)指針先移動(dòng) n 步，然后兩個(gè)指針再同時(shí)移動(dòng)，當(dāng)兩個(gè)指針相遇時(shí)，相遇
點(diǎn)就是環(huán)的入口節(jié)點(diǎn)。 

詳細(xì)資料可以參考：
《鏈表中環(huán)的入口結(jié)點(diǎn)》
《《劍指 offer》——鏈表中環(huán)的入口結(jié)點(diǎn)》

56. 刪除鏈表中重復(fù)的結(jié)點(diǎn)

 題目：

在一個(gè)排序的鏈表中，存在重復(fù)的結(jié)點(diǎn)，請(qǐng)刪除該鏈表中重復(fù)的結(jié)點(diǎn)，重復(fù)的結(jié)點(diǎn)不保留，返回鏈表頭指針。例如，鏈表 1->2->3-

> 3->4->4->5 處理后為 1->2->5

思路：

解決這個(gè)問(wèn)題的第一步是確定刪除的參數(shù)。當(dāng)然這個(gè)函數(shù)需要輸入待刪除鏈表的頭結(jié)點(diǎn)。頭結(jié)點(diǎn)可能與后面的結(jié)點(diǎn)重復(fù)，也就是說(shuō)頭
結(jié)點(diǎn)也可能被刪除，所以在鏈表頭額外添加一個(gè)結(jié)點(diǎn)。

接下來(lái)我們從頭遍歷整個(gè)鏈表。如果當(dāng)前結(jié)點(diǎn)的值與下一個(gè)結(jié)點(diǎn)的值相同，那么它們就是重復(fù)的結(jié)點(diǎn)，都可以被刪除。為了保證刪除
之后的鏈表仍然是相連的而沒(méi)有中間斷開(kāi)，我們要把當(dāng)前的前一個(gè)結(jié)點(diǎn)和后面值比當(dāng)前結(jié)點(diǎn)的值要大的結(jié)點(diǎn)相連。我們要確保 prev
要始終與下一個(gè)沒(méi)有重復(fù)的結(jié)點(diǎn)連接在一起。 

57. 二叉樹(shù)的下一個(gè)結(jié)點(diǎn)

題目：

給定一棵二叉樹(shù)和其中的一個(gè)結(jié)點(diǎn)，如何找出中序遍歷順序的下一個(gè)結(jié)點(diǎn)？樹(shù)中的結(jié)點(diǎn)除了有兩個(gè)分別指向左右子結(jié)點(diǎn)的指針以外，
還有一個(gè)指向父節(jié)點(diǎn)的指針。

思路：

這個(gè)問(wèn)題我們可以分為三種情況來(lái)討論。

第一種情況，當(dāng)前節(jié)點(diǎn)含有右子樹(shù)，這種情況下，中序遍歷的下一個(gè)節(jié)點(diǎn)為該節(jié)點(diǎn)右子樹(shù)的最左子節(jié)點(diǎn)。因此我們只要從右子節(jié)點(diǎn)
出發(fā)，一直沿著左子節(jié)點(diǎn)的指針，就能找到下一個(gè)節(jié)點(diǎn)。

第二種情況是，當(dāng)前節(jié)點(diǎn)不含有右子樹(shù)，并且當(dāng)前節(jié)點(diǎn)為父節(jié)點(diǎn)的左子節(jié)點(diǎn)，這種情況下中序遍歷的下一個(gè)節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)的父節(jié)
點(diǎn)。

第三種情況是，當(dāng)前節(jié)點(diǎn)不含有右子樹(shù)，并且當(dāng)前節(jié)點(diǎn)為父節(jié)點(diǎn)的右子節(jié)點(diǎn)，這種情況下我們沿著父節(jié)點(diǎn)一直向上查找，直到找到
一個(gè)節(jié)點(diǎn)，該節(jié)點(diǎn)為父節(jié)點(diǎn)的左子節(jié)點(diǎn)。這個(gè)左子節(jié)點(diǎn)的父節(jié)點(diǎn)就是中序遍歷的下一個(gè)節(jié)點(diǎn)。

58. 對(duì)稱二叉樹(shù)

題目：

請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)來(lái)判斷一棵二叉樹(shù)是不是對(duì)稱的。如果一棵二叉樹(shù)和它的鏡像一樣，那么它是對(duì)稱的。

思路：

我們對(duì)一顆二叉樹(shù)進(jìn)行前序遍歷的時(shí)候，是先訪問(wèn)左子節(jié)點(diǎn)，然后再訪問(wèn)右子節(jié)點(diǎn)。因此我們可以定義一種對(duì)稱的前序遍歷的方式
，就是先訪問(wèn)右子節(jié)點(diǎn)，然后再訪問(wèn)左子節(jié)點(diǎn)。通過(guò)比較兩種遍歷方式最后的結(jié)果是否相同，以此來(lái)判斷該二叉樹(shù)是否為對(duì)稱二叉
樹(shù)。

59. 按之字形順序打印二叉樹(shù)（待深入理解）

題目：

請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)按照之字形順序打印二叉樹(shù)，即第一行按照從左到右的順序打印，第二層按照從右到左的順序打印，即第一行按照
從左到右的順序打印，第二層按照從右到左順序打印，第三行再按照從左到右的順序打印，其他以此類推。

思路：

按之字形順序打印二叉樹(shù)需要兩個(gè)棧。我們?cè)诖蛴∧骋恍薪Y(jié)點(diǎn)時(shí)，把下一層的子結(jié)點(diǎn)保存到相應(yīng)的棧里。如果當(dāng)前打印的是奇數(shù)層
，則先保存左子結(jié)點(diǎn)再保存右子結(jié)點(diǎn)到一個(gè)棧里；如果當(dāng)前打印的是偶數(shù)層，則先保存右子結(jié)點(diǎn)再保存左子結(jié)點(diǎn)到第二個(gè)棧里。每
一個(gè)棧遍歷完成后進(jìn)入下一層循環(huán)。

詳細(xì)資料可以參考：
《按之字形順序打印二叉樹(shù)》

60. 從上到下按層打印二叉樹(shù)，同一層結(jié)點(diǎn)從左至右輸出。每一層輸出一行。

題目：

從上到下按層打印二叉樹(shù)，同一層的結(jié)點(diǎn)按從左到右的順序打印，每一層打印一行。

思路：

用一個(gè)隊(duì)列來(lái)保存將要打印的結(jié)點(diǎn)。為了把二叉樹(shù)的每一行單獨(dú)打印到一行里，我們需要兩個(gè)變量：一個(gè)變量表示在當(dāng)前的層中還
沒(méi)有打印的結(jié)點(diǎn)數(shù)，另一個(gè)變量表示下一次結(jié)點(diǎn)的數(shù)目。

61. 序列化二叉樹(shù)（帶深入理解）

題目：

請(qǐng)實(shí)現(xiàn)兩個(gè)函數(shù)，分別用來(lái)序列化和反序列化二叉樹(shù)。

思路：

數(shù)組模擬

62. 二叉搜索樹(shù)的第 K 個(gè)節(jié)點(diǎn)

題目：

給定一顆二叉搜索樹(shù)，請(qǐng)找出其中的第 k 小的結(jié)點(diǎn)。

思路：

對(duì)一顆樹(shù)首先進(jìn)行中序遍歷，在遍歷的同時(shí)記錄已經(jīng)遍歷的節(jié)點(diǎn)數(shù)，當(dāng)遍歷到第 k 個(gè)節(jié)點(diǎn)時(shí)，這個(gè)節(jié)點(diǎn)即為第 k 大的節(jié)點(diǎn)。

63. 數(shù)據(jù)流中的中位數(shù)（待深入理解）

題目：

如何得到一個(gè)數(shù)據(jù)流中的中位數(shù)？如果從數(shù)據(jù)流中讀出奇數(shù)個(gè)數(shù)值，那么中位數(shù)就是所有值排序之后位于中間的數(shù)值。如果數(shù)據(jù)
流中讀出偶數(shù)個(gè)數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后中間兩個(gè)數(shù)的平均值。

64. 滑動(dòng)窗口中的最大值（待深入理解）

題目：

給定一個(gè)數(shù)組和滑動(dòng)窗口的大小，找出所有滑動(dòng)窗口里數(shù)值的最大值。例如，如果輸入數(shù)組{2,3,4,2,6,2,5,1}及滑動(dòng)窗口的
大小 3，那么一共存在 6 個(gè)滑動(dòng)窗口，他們的最大值分別為{4,4,6,6,6,5}； 針對(duì)數(shù)組{2,3,4,2,6,2,5,1}的滑動(dòng)窗口有以下
6 個(gè)： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2
,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

思路：

使用隊(duì)列的方式模擬 

65. 矩陣中的路徑（待深入理解）

題目：

請(qǐng)?jiān)O(shè)計(jì)一個(gè)函數(shù)，用來(lái)判斷在一個(gè)矩陣中是否存在一條包含某字符串所有字符的路徑。路徑可以從矩陣中的任意一個(gè)格子開(kāi)始，每
一步可以在矩陣中向左，向右，向上，向下移動(dòng)一個(gè)格子。如果一條路徑經(jīng)過(guò)了矩陣中的某一個(gè)格子，則該路徑不能再進(jìn)入該格子
。例如 a b c e s f c s a d e e 矩陣中包含一條字符串"bcced"的路徑，但是矩陣中不包含"abcb"路徑，因?yàn)樽址?br>第一個(gè)字符 b 占據(jù)了矩陣中的第一行第二個(gè)格子之后，路徑不能再次進(jìn)入該格子。

66. 機(jī)器人的運(yùn)動(dòng)范圍（待深入理解）

題目：

地上有一個(gè) m 行和 n 列的方格。一個(gè)機(jī)器人從坐標(biāo) 0,0 的格子開(kāi)始移動(dòng)，每一次只能向左，右，上，下四個(gè)方向移動(dòng)一格，但是不能
進(jìn)入行坐標(biāo)和列坐標(biāo)的數(shù)位之和大于 k 的格子。 例如，當(dāng) k 為 18 時(shí)，機(jī)器人能夠進(jìn)入方格（35,37），因?yàn)?nbsp;3+5+3+7 = 18。但是
，它不能進(jìn)入方格（35,38），因?yàn)?nbsp;3+5+3+8 = 19。請(qǐng)問(wèn)該機(jī)器人能夠達(dá)到多少個(gè)格子？

劍指 offer 相關(guān)資料可以參考：

• 《劍指 offer 題目練習(xí)及思路分析》
• 《JS 版劍指 offer》
• 《劍指 Offer 學(xué)習(xí)心得》

推薦

筆者再次墻裂推薦收藏這篇原文，收錄于 CavsZhouyou - ?? 前端面試復(fù)習(xí)筆記，這個(gè)倉(cāng)庫(kù)是原作者校招時(shí)的前端復(fù)習(xí)筆記，主要總結(jié)一些比較重要的知識(shí)點(diǎn)和前端面試問(wèn)題，希望對(duì)大家有所幫助。

最后如果文章和筆記能帶您一絲幫助或者啟發(fā)，請(qǐng)不要吝嗇你的贊和收藏，你的肯定是我前進(jìn)的最大動(dòng)力 ??