做題窝趣，實際寫出例子，然后分析可能遇到的情況勾给，慢慢的滩报，思路就會出來了锅知。

線性表

33. Search in Rotated Sorted Array

這道題，不同于二分查找法在于脓钾，不能確定售睹，中點一定是大于左端點的。所以可训，在進(jìn)行二分查找時昌妹，需要多一步，即握截，先判斷中點是否大于左端點飞崖。
如果中點大于左端，再去比較三個點谨胞，才可以按照二分邊界賦值固歪。
如果中點小于左端，再去比較三個點胯努，再按照二分邊界賦值牢裳。

15. 3Sum

參考2SUM/3SUM/4SUM問題
解決方法就是最外層遍歷一遍，等于選出一個數(shù)叶沛，
之后的數(shù)組中轉(zhuǎn)化為找和為target-nums[i]的2SUM問題蒲讯。

16. 3Sum closest

參考 3Sum Closest 最近三數(shù)之和

所以我們需要定義一個變量diff用來記錄差的絕對值，然后我們還是要先將數(shù)組排個序灰署，然后開始遍歷數(shù)組判帮，思路跟那道三數(shù)之和很相似，都是先確定一個數(shù)氓侧，然后用兩個指針left和right來滑動尋找另外兩個數(shù)脊另，每確定兩個數(shù)，我們求出此三數(shù)之和约巷，然后算和給定值的差的絕對值存在newDiff中偎痛，然后和diff比較并更新diff和結(jié)果closest即可，

31独郎、next_permutation

參考[算法]——全排列（Permutation）以及next_permutation

其中踩麦，舉出例子，然后一點點的去試氓癌，然后根據(jù)試出的步驟谓谦，寫代碼即可。
[6贪婉、5反粥、4、8、7才顿、5莫湘、1]

• 1，1和5替換郑气，沒有效果幅垮，那么1和7替換也沒有效果，再往前尾组，比1大的都沒有效果忙芒。
• 2，從上面也能看出讳侨，5替換的話呵萨，一直到8，也沒有效果爷耀。
• 3甘桑，4替換8有效果拍皮，但是為了找到最小的下一個全排列歹叮，所以，應(yīng)該讓4和后面的8-5中铆帽，最小的替換咆耿。
• 4、替換完事之后爹橱，發(fā)現(xiàn)變成了6558741萨螺，最后四位是降序的，不滿足條件愧驱。6551478才滿足條件慰技，于是可以將后面的反轉(zhuǎn)。
• 5组砚、一開始就是降序的話吻商，那么直接反轉(zhuǎn)即可。

但是如果一個一個比較的話比較麻煩糟红，可以看出艾帐，我們是從后面找起，找到不是降序的子數(shù)列為止盆偿。有一個方法柒爸，從后向前查找第一個相鄰元素對(i,j)，并且滿足A[i] < A[j]事扭。易知捎稚，此時從j到end必然是降序。可以用反證法證明今野。于是編程時晰奖，可以用這個，直接從第三步走起腥泥。

60匾南、Permutation Sequence

參考 Permutation Sequence 序列排序

36、有效數(shù)獨

參考Valid Sudoku

48. Rotate Image

在原地修改蛔外，是可以利用tmp等變量來進(jìn)行修改的蛆楞。

73. Set Matrix Zeroes

參考 Set Matrix Zeroes 矩陣賦零

• 1、最原始的夹厌，是用O(m*n)的時間復(fù)雜度豹爹，再建立一個新的矩陣，一個數(shù)一個數(shù)的讀矛纹，一行一行的掃進(jìn)去臂聋，遇到0 ，就把新的矩陣改行設(shè)置為0 或南。再一列一列的掃
• 2孩等、將時間降到O(m+n)，可以用兩個數(shù)組采够，一個m維數(shù)組記錄哪一行有0 肄方，一個n維數(shù)組記錄哪一列有0。（in方法判斷）最后更新
• 3蹬癌、但是要求空間復(fù)雜度為O(1)权她，不能用額外的空間。所以想到逝薪，用第一行隅要，第一列存儲。
• 4董济、但是步清，第一行第一列的數(shù)值也要保證不能變（除非改行有0）。按照下面的邏輯感局。

主要是更新順序

• 先掃描第一行第一列尼啡，如果有0，則將各自的flag設(shè)置為true（最后再更新询微。）
• 然后掃描除去第一行第一列的整個數(shù)組崖瞭，如果有0，則將對應(yīng)的第一行和第一列的數(shù)字賦0
• 再次遍歷除去第一行第一列的整個數(shù)組撑毛，如果對應(yīng)的第一行和第一列的數(shù)字有一個為0书聚，則將當(dāng)前值賦0
• 最后根據(jù)第一行第一列的flag來更新第一行第一列

136. Single Number

參考Single Number

每次一個元素進(jìn)行異或唧领，0和5異或返回5.....

86. Partition List

單鏈表

61. Rotate List

• k是可以大于n的，所以需要對n取余數(shù)
• 倒著往回數(shù)雌续，快慢指針斩个，快的先走k步，然后慢的再走

字符串

125驯杜、有效回文

一般情況下做法：建立兩個指針受啥，左右相比較

對于不是字母的字符串，用list[l].isalnum()來判斷真假鸽心，while循環(huán)跳過去就行

特殊情況滚局，字符串是[]空。

幾乎所有的題顽频，都要考慮這個情況藤肢，對于字符串是空，對于鏈表一類的可能只有一個node糯景∴胰Γ總之，考慮極端情況是對的蟀淮。

5. Longest Palindromic Substring

參考 Longest palindromic substring 最長回文子串

棧

20最住、有效括號

問題的思路分析，即能夠通過在字符間插入特定數(shù)目的豎線灭贷，使得整個字符串各個局部都對稱温学。由這句話略贮，局部對稱來引入棧甚疟，

考慮到棧中可以通過一進(jìn)一出，兩進(jìn)兩出的類似對稱逃延。所以览妖，可以用棧來解決此問題。

代碼思路：
step1：初始化棧揽祥，并入棧輸入串的第一個字符讽膏；
step2: 從輸入串的第二個字符到最后一個字符，依次與棧頂元素對比拄丰，棧不為空且棧頂元素與字符匹配則出棧府树，否則入棧該字符；
Step3: 操作完最后一個字符后料按，如果棧為空（即有進(jìn)必有出奄侠，各個局部均對稱），則輸入合法载矿；

參考valid parentheses

另外垄潮，可以用list的append和pop方法來近似的構(gòu)造出一個棧的數(shù)據(jù)結(jié)構(gòu)。

若出現(xiàn)右邊的括號類型，那么為了valid弯洗，上一個壓入棧中的一定是這個括號的左邊類型旅急。
即，如果出現(xiàn)了“）”牡整，那么棧最上面的一定是“（”才行藐吮。可以由此進(jìn)行判斷逃贝。

32炎码、最大有效括號的長度longest parenthses

此算法， 用“（”的索引來進(jìn)行壓棧秋泳，入棧操作潦闲。是因為，需要計算合法括號字符的長度迫皱，用數(shù)字運(yùn)算比較方便歉闰。

這個和有效括號有些不同，這個

• 1卓起、原則1和敬，就是，棧中只會存放左邊括號的符號“（”位置索引戏阅。這是利用了括號有效的必要條件的特性昼弟，下面會把這些情況都解釋一下。
• 2奕筐、這里的棧存放的不再是“（”舱痘，而是此符號的位置索引了。（當(dāng)然也可以用兩個棧离赫，一個存放“（”芭逝，一個存放位置索引。沒必要而已渊胸。）

接下來是代碼思路：
參考longest parenthses

每次來了‘(’之后旬盯，無條件壓棧。

用“）”進(jìn)行消除翎猛，有這幾種情況需要考慮胖翰。
首先就是“））（）”這樣的，即切厘，碰到頭兩個右括號時萨咳，棧為空，那么一定不是合法的了迂卢，可以跳過某弦。

然后就是“（（（））（）”桐汤，此時碰到了第一個“）”時，消掉最上面的左括號靶壮，然后接下來是第二個“）”怔毛，可以再次消掉棧最上面的左括號，然后碰到“（” 腾降，直接入棧拣度，然后繼續(xù)碰到“）”，再次消掉螃壤。

直到“）”用完為止或者棧為空為止抗果。下面依次解釋這兩種情況。

• 1奸晴、“）”用完了冤馏。棧內(nèi)還有剩余的‘(’。如上例：
  此時棧里還剩一個“（”沒有消掉寄啼，而“）”已經(jīng)沒有了逮光。那么此時這個有效括號的長度就是當(dāng)前“）”的索引減去棧頂“（”的索引值。對應(yīng)到例子上就是墩划，6-0=6涕刚。
  然后再與前面已有的合法長度進(jìn)行比較。maxLength = Math.max(i - (int)stack.peek() , maxLength)

• 2乙帮、')'沒用完杜漠，棧空了
  此時需要引入一個新的變量start察净，用于表示新的合法括號字符串的起點驾茴。
  例如：對于這種情況：())()()，可以正確的得出最大值為4塞绿。
  start初始為-1沟涨，之后每次碰到‘)’且棧為空的時候更新為當(dāng)前‘)’的index。
  比如上例中异吻， start就為第二個“）”的index，表示新的合法字符串起點為3.

• 3喜庞、一直循環(huán)就是了诀浪。

此算法， 用“（”的索引來進(jìn)行壓棧延都，入棧操作雷猪。是因為，需要計算合法括號字符的長度晰房，用數(shù)字運(yùn)算比較方便求摇。

樹

144射沟、二叉樹前序遍歷

注意，樹中的node并不是一個int類型的數(shù)字与境。這個node具有屬性的验夯。分別是node.val，node.left 和 node.right摔刁。分別代表著這個node的值挥转，左子節(jié)點和右子節(jié)點。

所以共屈，壓入棧中的绑谣，也是node，而不是node.val拗引。

此題要求不能用遞歸的方法前序遍歷二叉樹借宵。
想到前序遍歷的路徑，一直讀入最左邊的葉節(jié)點矾削，然后退回父節(jié)點接著讀父節(jié)點的右子節(jié)點（注意此時父節(jié)點已經(jīng)被讀取過了）暇务，和棧有些相似。于是想到用棧來解決問題怔软。
（最好畫個圖垦细，來分析循環(huán)的步驟。）
題中已經(jīng)給出挡逼，節(jié)點具有的三個屬性括改。

root作為根節(jié)點
令棧為空

• 1、讀入節(jié)點1家坎，如果1有左子節(jié)點嘱能，就繼續(xù)遍歷入棧，一直入棧到底（此時虱疏，棧里壓入一個元素惹骂，list就append一個元素。）
• 2做瞪、彈棧对粪，彈出一個元素，就檢測該元素是否有右子節(jié)點装蓬。即root.right是否為空著拭。若不為空，就遍歷壓入棧中牍帚。
• 3. 彈出5儡遮，沒有左右子節(jié)點，繼續(xù)彈棧暗赶，1彈出后鄙币，有右子節(jié)點肃叶，于是按照上面步驟壓入棧中。
• 4十嘿、一直循環(huán)到因惭，節(jié)點為空，棧為空為止详幽。

        list_num= []
        stack = []
        while root or stack:
            if root:
                list_num.appent(root)
                stack.append(root)
                root = root.left
            else:
                stack.pop()
                root = root.right
        return list_num

逐層返回二叉樹

參考# Binary Tree Level Order Traversal 二叉樹層序遍歷

層序遍歷二叉樹是典型的廣度優(yōu)先搜索BFS的應(yīng)用筛欢，但是這里稍微復(fù)雜一點的是，我們要把各個層的數(shù)分開唇聘，存到一個二維向量里面版姑，大體思路還是基本相同的，建立一個queue迟郎，然后先把根節(jié)點放進(jìn)去剥险，這時候找根節(jié)點的左右兩個子節(jié)點，這時候去掉根節(jié)點宪肖，此時queue里的元素就是下一層的所有節(jié)點表制，用一個for循環(huán)遍歷它們，然后存到一個一維向量里控乾，遍歷完之后再把這個一維向量存到二維向量里么介，以此類推，可以完成層序遍歷蜕衡。代碼如下：

第二版本：

形壤短，不同之處在于一行是從左到右遍歷，下一行是從右往左遍歷慨仿，交叉往返的之字形的層序遍歷久脯。根據(jù)其特點我們用到棧的后進(jìn)先出的特點，這道題我們維護(hù)兩個棧镰吆，相鄰兩行分別存到兩個棧中帘撰，進(jìn)棧的順序也不相同，一個棧是先進(jìn)左子結(jié)點然后右子節(jié)點万皿，另一個棧是先進(jìn)右子節(jié)點然后左子結(jié)點摧找，這樣出棧的順序就是我們想要的之字形了，代碼如下：

101 對稱樹

  class Solution:
    # @param root, a tree node
    # @return a boolean
    def isSymmetric(self, root):
        # a new recursive function to check if two tree are symetric
        def isMirror(root1,root2):
                # they all could be Null to be symetric
            if not root1 and not root2:
                return True
                # if they are not Null, they must carry the same value
            elif (root1 and root2) and root1.val==root2.val:
                # recursively call itself
                return isMirror(root1.left,root2.right) and isMirror(root1.right, root2.left)
            else:
                return False
        if not root:
            return True
        return isMirror(root.left, root.right)

114. Flatten Binary Tree to Linked List

參考 Flatten Binary Tree to Linked List 將二叉樹展開成鏈表

這道題要求把二叉樹展開成鏈表相寇，根據(jù)展開后形成的鏈表的順序分析出是使用先序遍歷慰于，那么只要是數(shù)的遍歷就有遞歸和非遞歸的兩種方法來求解，這里我們也用兩種方法來求解唤衫。首先來看遞歸版本的，思路是先利用DFS的思路找到最左子節(jié)點绵脯，然后回到其父節(jié)點佳励，把其父節(jié)點和右子節(jié)點斷開休里，將原左子結(jié)點連上父節(jié)點的右子節(jié)點上，然后再把原右子節(jié)點連到新右子節(jié)點的右子節(jié)點上赃承，然后再回到上一父節(jié)點做相同操作妙黍。代碼如下：

112 path sum

遞歸：1 終止條件 2 每次都要變化的

• 首先，如果輸入的是一個空節(jié)點瞧剖，則直接返回false拭嫁，如果如果輸入的只有一個根節(jié)點，則比較當(dāng)前根節(jié)點的值和參數(shù)sum值是否相同抓于，若相同做粤，返回true，否則false捉撮。 這個條件也是遞歸的終止條件怕品。
• 下面我們就要開始遞歸了，由于函數(shù)的返回值是Ture/False巾遭，我們可以同時兩個方向一起遞歸肉康，中間用或||連接，只要有一個是True灼舍，整個結(jié)果就是True吼和。
• 遞歸左右節(jié)點時，這時候的sum值應(yīng)該是原sum值減去當(dāng)前節(jié)點的值骑素。代碼如下：

129. Sum Root to Leaf Numbers

···
class Solution {
public:
int sumNumbers(TreeNode *root) {
return sumNumbersDFS(root, 0);
}
int sumNumbersDFS(TreeNode *root, int sum) {
if (!root) return 0;
sum = sum * 10 + root->val;
if (!root->left && !root->right) return sum;
return sumNumbersDFS(root->left, sum) + sumNumbersDFS(root->right, sum);
}
};
···

105炫乓、利用前序遍歷和中序遍歷構(gòu)建二叉樹

參考idiot-maker
實際上，就是利用這兩個遍歷的特性砂豌，確定遍歷的邊界厢岂。

要解決這道題目，就要分別利用preorder和inorder遍歷的兩個性質(zhì)阳距。preoder的第一個元素確定為根節(jié)點塔粒，然后再在inorder里，它左側(cè)的就是左子樹的全部節(jié)點筐摘，右側(cè)的就是右子樹的全部節(jié)點卒茬。然后再對左子樹這些節(jié)點，遞歸調(diào)用上面的方法咖熟。

比如

• preorder圃酵，7是根節(jié)點
• inorder，7左邊的是左子樹全部節(jié)點馍管，長度為4郭赐，7右邊的是右子樹全部節(jié)點，長度為3.
• preorder确沸，7后邊4個數(shù)捌锭，全是左子樹的val俘陷。第5個數(shù)開始，全是右子樹的val观谦±埽可由此確定，左子樹的根節(jié)點是10豁状，右子樹的根節(jié)點是2
• inorder,左子樹的根節(jié)點10捉偏，左邊的都是左子樹的左子樹長度為1，右邊的都是左子樹的右子樹長度為2泻红。
• preorder夭禽，10后邊1個數(shù)，全是左子樹的val承桥。第2個數(shù)開始驻粟，全是右子樹的val⌒滓欤可由此確定蜀撑，左子樹的根節(jié)點是4，右子樹的根節(jié)點是3.

就這樣遞歸下去剩彬。

對應(yīng)成代碼酷麦，就是

def buildTree(self, preorder, inorder):
        if not preorder or not inorder:#遞歸的終止條件，當(dāng)此樹的遍歷列表為空時喉恋，說明為葉節(jié)點沃饶。
            return None

        rootValue = preorder[0]#確定根節(jié)點的值
        root = TreeNode(rootValue)#用TreeNode構(gòu)造根節(jié)點
        inorderIndex = inorder.index(rootValue)#確定根節(jié)點在中序遍歷中的index
        
        #root的左子樹的長度，就是根節(jié)點在inorder中左邊的部分的長度轻黑，
        #那么可以知道糊肤，樹的左子樹的前序遍歷就是preorder列表中[1:inorderIndex+1]的部分
        #左子樹的中序遍歷就是inorder中的[:inorderIndex]部分。
        root.left = buildTree(preorder[1:inorderIndex+1], inorder[:inorderIndex])

        root.right = buildTree(preorder[inorderIndex+1:], inorder[inorderIndex+1:])
        
        return root

98氓鄙、Validate Binary Search Tree驗證二分查找樹是有效的

參考Validate Binary Search Tree
用遞歸的話馆揉，時間復(fù)雜度是O(n2)。

需要注意的是抖拦，左子樹的所有節(jié)點都要比根節(jié)點小升酣，而非只是其左孩子比其小，右子樹同樣态罪。這是很容易出錯的一點是噩茄，很多人往往只考慮了每個根節(jié)點比其左孩子大比其右孩子小。如下面非二分查找樹复颈，如果只比較節(jié)點和其左右孩子的關(guān)系大小绩聘，它是滿足的。

通過這個思路進(jìn)行判斷。
二分查找樹的中序遍歷結(jié)果是一個遞增序列君纫。
所以驯遇，可以先對二分查找樹進(jìn)行中序遍歷（遞歸）芹彬，再判斷此序列是不是一個遞增序列蓄髓。

108、 Convert Sorted Array to Binary Search Tree

參考 Convert Sorted Array to Binary Search Tree

• 1舒帮、二叉搜索樹的特性：始終滿足左<根<右

• 2会喝、一個二叉搜索樹的中序遍歷就是一個遞增序列。

于是玩郊，反過來肢执，我們可以認(rèn)為，根節(jié)點就是有序列表的中間點译红，從中間點分開為左右兩個有序數(shù)組预茄，在分別找出其中間點作為原中間點的左右兩個子節(jié)點。遞歸進(jìn)行下去就行侦厚。（這也是二分查找法的核心思想）

代碼也與二分查找的代碼類似耻陕。遞歸

111、Minimum Depth of Binary Tree

參考 Minimum Depth of Binary Tree

也是遞歸刨沦，關(guān)于minipath長度怎么疊加诗宣，
可以采用，在遞歸函數(shù)中想诅，當(dāng)當(dāng)前節(jié)點是葉節(jié)點時召庞，返回0.
如果當(dāng)前節(jié)點有子節(jié)點，那么就返回min(left_path()来破，right_path()) +1篮灼。即當(dāng)前子節(jié)點下面路徑的最小值再加1。

那么得到的效果就是徘禁，從上往下诅诱，每次下沉，都會加1晌坤。一直加到 最終葉節(jié)點逢艘，得到 minipath為0。然后再一次返回到根節(jié)點骤菠，得到路徑長度它改。

對參考的程序的解讀。

• 1商乎、如果左右子節(jié)點都為空央拖，那么就返回1。（因為此時只有一層節(jié)點，路徑也只能是1）

• 2鲜戒、如果专控，左子節(jié)點為空，那么就返回右子節(jié)點的遞歸+1遏餐。
  左子節(jié)點為空伦腐，說明右子節(jié)點不為空。要是畫出圖來失都，那么此路徑就會經(jīng)過父節(jié)點必須向右子節(jié)點過去柏蘑。此時的路徑長度就是返回右子節(jié)點的遞歸調(diào)用加1了。
  注意粹庞！并不是說咳焚，左子節(jié)點為空，那么父節(jié)點就不往下走了庞溜，最短路徑就已經(jīng)求得了革半，而是說，左子節(jié)點為空流码，那么父節(jié)點又官，也得往下走，一直走到葉節(jié)點為止旅掂。

• 3赏胚、如果，右子節(jié)點為空商虐，那么就返回左子節(jié)點的遞歸+1觉阅。

• 4、如果是其余情況（都不為空）秘车，就返回左右子節(jié)點 二者遞歸調(diào)用的最小值典勇。

排序

88. Merge Sorted Array

參考LeetCode_Merge Sorted Array

這里需要注意的是，num1和nums2都是數(shù)組叮趴，每次從nums2中挑出一個元素插入nums1中割笙，都是需要改變數(shù)組的index的。

如果單純得考慮從小到大地將兩個數(shù)組進(jìn)行合并的話眯亦，每次在num1中插入一個數(shù)的話伤溉，需要將后面的元素都向后移動一位，這樣妻率，整個處理過程的時間復(fù)雜度為O(m*n)乱顾。

題目已經(jīng)給出，nums1可以認(rèn)為長度是m+n宫静。那么就可以先把nums2中的最大值和nums中的最大值進(jìn)行比較走净，放到nums1中的最后一位（index=m+n-1）券时。
然后比較得到次最大值，將次最大值放在m+n-2位置伏伯，依次類推橘洞，這樣在將元素放置到合適位置的時候，就不需要移動元素说搅，這個方法的時間復(fù)雜度為O(m+n)炸枣。

每次循環(huán)中，如果nums2的元素被插入到了最大值中蜓堕，那么n=n-1抛虏。下次可以用nums2[n-1]來對nums2中的次最大值進(jìn)行索引。

21. Merge Two Sorted Lists

參考Merge Two Sorted Lists

鏈表有序合并也是數(shù)據(jù)結(jié)構(gòu)里邊的經(jīng)典題目了套才。

• 1、分別掃描兩個鏈表慕淡，比較兩個節(jié)點的大小值背伴，把較小的節(jié)點值尾插到結(jié)果鏈表屁股后邊，
• 2峰髓、然后再次掃描兩個鏈表傻寂，直到其中某一個鏈表或者兩條鏈表同時結(jié)束。
• 3携兵、如果是某條鏈表提前結(jié)束則應(yīng)將另一條鏈表的其余節(jié)點都接到結(jié)果鏈表上白胀。

75哲嘲、sort colors

• 定義red指針指向開頭位置，blue指針指向末尾位置

• 從頭開始遍歷原數(shù)組，如果遇到0叉信，則交換該值和red指針指向的值，并將red指針后移一位逐哈。若遇到2吗冤，則交換該值和blue指針指向的值，并將blue指針前移一位嘲碧。若遇到1，則繼續(xù)遍歷。