* Always remember to check the quality/availability of the input array/number/anything.
1. Two sum
The complexity of my solution is O(n^2). It's very simple and a little stupid.
There are two others' solution:
which complexity is O(n)
以上這兩種方法用的都是hash或dictionary。還有一種方法是夾逼法，先對數組進行排序，然后用兩個pointer分別指向數組的第一個和最后一個數字，檢查這兩個數字相加是否等于target，若等于，則返回這兩個數字。否則就比較這兩個數字相加后和target的大小，若大于target，便把right pointer向左移一個數字（right --）， 若比target小，則 left＋＋。但是這種方法最終返回的是數字，不是index。若需要返回index，則要另外構造一個數字結構，存儲最初的數字和index，再依次進行查找。
66. Plus one
Use a variable "carry" to denote whether to carry on this digit. It's very skillful, and need to be often reviewed.
88. Merged sorted array
num1 is long enough to contain both num1 and num2. So compare element in num1 and in num2 one by one, put the biggest in num1[m+n-1]. If the num1 is empty, just copy num2 into num1.
118. Pascal's Triangle
The main principle of Pascal Triangle is:
通過觀察楊輝三角可知，下一行的每一個元素都依次由本行中每兩個相鄰元素之和得到，這個方法可以用一個技巧實現，即：將本行l(wèi)ist拷貝出兩個副本，將兩個副本錯1位，然后加在一起。由于錯位后，前后各多了一個元素，所以要在錯位后的兩個list的前后各加一個[0]來補齊（其實，這個0是理所當然的，是楊輝三角的一部分）。
同一行中前后相鄰兩個元素相加（這是楊輝三角的構成規(guī)則），就相當于兩個本行元素錯位相加。而zip方法，就是從這兩行中分別取出第i個位置的元素組成元組（這也是添“0”的原因）。sum()函數正好求出它們的和，進而求出了下一行。然后又yield函數把這一行“塞入”generator--也就是本例中的triangles()。
217. Contains Duplicate
Given an unsorted array, most times it's better to sort it first, then do what you want. In this question, if I didn't sort it first, I need to compare the 'temp' variable to every element in the array, which takes O(n^2). But after sorted the array, we only need to compare 'nums[i]' with 'nums[i-1]' which obviously takes O(n).
219. Contains Duplicates 2
模仿大牛的代碼還是挺有用的。
1. set(): 去除重復對象
2. zip的用法：zip可被用來計算相鄰兩元素兩兩相減---m=[j-i for i, j in zip(p[:-1], p[1:])]
3. enumerate()
4. 切片
切片操作符中的第一個數（冒號之前）表示切片開始的位置，第二個數（冒號之后）表示切片到哪里結束，第三個數（冒號之后）表示切片間隔數。如果不指定第一個數，Python就從序列首開始。如果沒有指定第二個數，則Python會停止在序列尾。注意，返回的序列從開始位置開始，剛好在結束位置之前結束。即開始位置是包含在序列切片中的，而結束位置被排斥在切片外。
這樣，shoplist[1:3]返回從位置1開始，包括位置2，但是停止在位置3的一個序列切片，因此返回一個含有兩個項目的切片。類似地，shoplist[:]返回整個序列的拷貝。shoplist[::3]返回位置3，位置6，位置9…的序列切片。
你可以用負數做切片。負數用在從序列尾開始計算的位置。例如，shoplist[:-1]會返回除了最后一個項目外包含所有項目的序列切片，shoplist[::-1]會返回倒序序列切片。
121. Best time to buy and sell stock 動態(tài)規(guī)劃
this question can be seen as dynamic programming. ? Using one local max profit and one global max profit to find the best time to buy and sell stock. ?Compare the local max profit with 0, cause sometime the stock profit may be negative. then compare the local max profit with the global max profit, which aims to update the global max profit.
local = 0; global = 0;
local = max(local+ prices[i+1]-prices[i], 0)
global = max(local, global)
* do not forget to add the former local max profit
268. Missing Number
To find the element in list1 but not in list2:
list3 = list(set(list1) - set(list2))
list3 = [i for i in list1 if i not in list2]
list3 = list(set(list1).difference(set(list2)))
54. Spiral Matrix
When traverse left and up, we need to add the additional judgement condition, "if rowbegin <= rowend" and "if colbegin <= colend". Aims to avoid traverse back when there is only one row or one column in matrix.
55. Jump Game. 53 Maximum subarray動態(tài)規(guī)劃
396. Rotate Function
變換公式，找出數學規(guī)律
238. Product of Array Except Self
Use a middle variable to compute the product.
First, initialise the list as: 1, n_0, n_0*n_1, n_0*n_1*n_2. Then start from the end of the list, times the middle variable P. ?P start from 1, to n_3, n_3*n_2, n_3*n_2*n_1
15. 3 Sum
在三個數中，固定一個數nums[i] ，將第二個數和第三個數分別從i+1和最后一個數開始。判斷三個數相加是否為0，若為0，則將這三個數添加到結果中，然后向右移動left（需要保證left < right），若移動后的數字和移動前的數字一樣，則繼續(xù)移動。 若三個數相加大于0， 則向左移動right（需要保證left < right），若移動后的數字和移動前的數字一樣，則繼續(xù)移動。若三個數相加小于0，繼續(xù)上邊的操作。
記住每次更換固定的數字時，都要重新初始化left和right。并且要保證left < right。
時間復雜度為n^2
39. Combination Sum
運用Backtracking和DFS的思想，因為相加等于target的組合有多個，所以我們維護一個path list，每次向其中添加來自candidates中的一個元素，然后將target減去這個元素得到新的target，繼續(xù)調用backtracking函數，此時傳進去的參數是新的path和新的target。在每次backtracking執(zhí)行過程中，要注意檢查以下幾點：
1. 如果target<0: 則返回。 因為backtracking 函數沒有返回值，所以返回的是上一次調用這個函數之前的地方。即for循環(huán)那里，此時for循環(huán)向后移動，程序繼續(xù)
2.如果target=0：則說明此時的path便是我們想要的結果之一，便將path append到result中，然后返回。
3.如果target>0：便開始for循環(huán)，調用backtracking函數，此時的調用應該注意更新參數（path, target）。 ＊＊ 在調用函數之前，通過增加判斷 if target < c（break）來節(jié)省時間。并通過 if path and target<path[-1] ?(continue) 來去掉結果中的重復組合。這個判斷使得結果中的組合都是有序的，因此就去掉了重復項。
40. Combination Sum II
這道題跟第39題的區(qū)別就是，這道題不允許重復使用數字，比如candidates中如果有兩個1，那結果集中的每個path，也最多只能有兩個1。代碼需要改變的地方就是for循環(huán)中的判斷條件。上一題中，由于允許出現重復數字，因此可能會出現（2，2，3），（2，3，2），（3，2，2）這種情況，因此需要對每個path進行排序，來消除重復的path。這一題中，由于每個數字只允許使用一次，所以 1.每次調用backtracking函數，是從i＋1開始的：
self.backtracking(path + [self.cand[i]], i+1, target - self.cand[i])
2. 不需要對path進行排序，但是要跳過candidates中的重復項，避免得到重復的path。
if i > index and self.cand[i] == self.cand[i-1]: （continue）
＊＊注意這里是 i>index 而不是 i>0，因為for循環(huán)的起始點是 index， index每次都會進行更新。
94. Binary Tree Inorder Traversal
二叉樹的中序遍歷，可背
中序 inorder：左節(jié)點－>根節(jié)點－>右節(jié)點
前序 pre-order：根節(jié)點－左節(jié)點－右節(jié)點
后序 post-order: 左節(jié)點－右節(jié)點－根節(jié)點
注意：因為每次pop出來的是最后一個元素，所以push時應該按相反的順序來push
inorder:?
nodelist.append((node.right, False))
nodelist.append((node, True))
nodelist.append((node.left, False))
pre-order:
nodelist.append((node.right, False))
nodelist.append((node.left, False))
nodelist.append((node, True))
post-order:
nodelist.append((node, True))
nodelist.append((node.right, False))
nodelist.append((node.left, False))
206. Reverse Linked List
維護三個pointer: ?pre, head, next。 pre永遠是第一個，初始值應為none，因為第一個node反轉后指向的為空。head.next指向pre，pre后移到head, head后移到next. ?next指向的永遠是head.next。
92. Reverse Linked List II
先找到m之前的一個node，標記為mpre，然后m的位置就是mp ＝ mpre.next. ?使用一個計數器從0開始，花費 m-1>count 步驟找到mpre。 此時count已經有一定的值，再此count基礎上，再花費n-1>count步驟進行reverse。reverse的三個變量分別是: mpre, mp, temp(next). ?temp為mp的下一個node， 讓mp.next指向temp.next， 再將temp指向mp, 即temp.next = mpre.next, ?最后將mpre指向temp, 即mpre.next = temp.
61. Rotate List
given 1-2-3-4-5, k=2 ? ?return: 4-5-1-2-3
尋找尾節(jié)點的同時計算鏈表長度。
記鏈表長度為n，則實際移位次數為k=k%n。記len=n-k。
也就是說鏈表的后k個節(jié)點成為新鏈表的前半部分，鏈表的前l(fā)en個節(jié)點為新鏈表的后半部分。
因此head往右第len的節(jié)點為新鏈表的尾，第len+1為新鏈表的頭
兩端相連即可，尾部下一個設為NULL即可。
注意： 當 k % len == 0 時，直接返回原list
(a+b)>>1 == (a+b)/2
147. Insertion Sort List
針對linkedlist的插入排序， 先生成虛擬節(jié)點指向head。將head.next 設為空，以head作為最初的sorted list, 逐個加入后邊list中的每個元素。因為插入排序是從后向前掃描的，所以永遠維護sorted list中的最后一個元素作為pre, ? unsorted list中的第一個元素作為cur， 標記cur.next為next, 當當前cur被加入到sorted list中時，next 變成為新的cur。
每次比較pre和cur的值，如果pre的值小于等于cur的值，則直接將cur鏈接在pre之后即可。如果pre大于cur的值，則需要另一個變量prepre, ?使prepre從dummy開始，判斷prepre.next的值與cur值的大小關系，當prepre.next.val>cur.val時便停止。這時prepre所處的位置的下一個元素應指向cur。但在指向cur之前，應先標記prepre.next為prnext，因為插入cur之后，要將cur.next指向之前的prepre.next。
86. Partition List
昨天想了半天，今天看了一下discuss， 原來只要把original list拆成兩個list， 第一個list全是比x小的node， 第二個list全是大于等于x的node。再將第一個list指向第二個list，不要忘了將第二個list的最后一個node的next指向none。
148. Sort List
1. merge and sort。 ?
while fast and fast.next: ? slow = head, ? ? fast = head.next
循環(huán)停止時，slow正好停在上半段最后一個元素，fast停在下半段最后一個元素。
half2 = slow.next 作為下半段的開頭。迭代對兩個list進行sort，直到最后每一個node構成一個list，再對所有的list進行排序。
需要注意的就是，while停止時，要將slow.next先賦給half2, 然后將它指向空。fast是從head.next開始的，不是從head開始。
當fast從head開始時，需要另一個指針pre，指向前半段的最后一個元素。while中加上pre = slow。 while停止時，pre.next = none。 此時slow指向后半段第一個元素。
binary search
二分查找中mid=(l+r)/2 和 mid=l+(r-l)/2 是一樣的，二分查找復雜度為log(n)
34. Search for a Range
這題需要注意的問題不多，主要是更新l 和r時不能單純的將 l=mid, r=mid， 而應該是l = mid+1, r=mid-1。 循環(huán)判斷條件也應該是l<=r。 具體什么時候可以直接用mid，什么時候要mid+-1，我還沒有完全搞清楚
35. Search Insert Position
這個要注意的也不多, 找不到元素時返回r+1就好了
69. Sqrt(x)
用二分查找找出mid， 如果x介于mid*mid和(mid+1)*(mid+1)之間，那mid就是sqrt(x)。所以判斷條件就是：mid*mid <= x and x < (mid+1)*(mid+1) ?否則的話就相應的更新r或者l
74. Search a 2D Matrix
這題的重點在于，可以把這個每行都有序，且行與行之間也都有序的matrix看為一個一維數組來處理，l=0, r=m*n-1.? mid = (l+r)/2。知道了總的index，怎樣確定它在哪一行哪一列呢？
num = matrix[mid/n][mid % n]。 行：mid/n, ?列：mid%n。 n 為列數。
240. Search a 2D Matrix II
與上一題不同的地方在于，這個矩陣不僅每行升序排列，每列也都升序排列。idea就在于:
這里更新的不是l和r， 而是row 和 col。判斷條件也變?yōu)?while row < m and col >= 0。
不再是二分查找，時間復雜度為o(n)， 因為每次都和最右上方的元素比較，一共有n個最右上方的元素，最多比較n次。
29. Divide Two Integers
for example, if we want to calc (17/2)
ret = 0;
17-2 ,ret+=1; left=15
15-4 ,ret+=2; left=11
11-8 ,ret+=4; left=3
3-2 ,ret+=1; left=1
ret=8;
程序如下：
正負號和數字越界這里處理的比較巧妙。
50. Pow(x, n)
有5種不同解法，至少應該理解兩種，包括binary search的
https://discuss.leetcode.com/topic/21837/5-different-choices-when-talk-with-interviewers
81. Search in Rotated Sorted Array II
是33的follow up， 存在重復數字的情況，尚不明白
https://discuss.leetcode.com/topic/20593/python-easy-to-understand-solution-with-comments
209. Minimum Size Subarray Sum
https://discuss.leetcode.com/topic/13759/python-3-different-ac-solutions
不理解 binary search的
167. Two Sum II - Input array is sorted
15. 3Sum
16. 3Sum Closest
18. 4Sum
https://discuss.leetcode.com/topic/22705/python-140ms-beats-100-and-works-for-n-sum-n-2
python for N-sum
13. Roman to Integer
https://discuss.leetcode.com/topic/17110/my-straightforward-python-solution
http://blog.csdn.net/wzy_1988/article/details/17057929
43. Multiply Strings
150. Evaluate Reverse Polish Notation
1. 中綴轉換到reverse polish notation：（幫助理解解題思路）
? 第一步：按照運算符的優(yōu)先級對所有的運算單位加括號~
? 式子變成拉：((a+(b*c))-(d+e))
? 第二步：轉換中綴與后綴表達式
? 后綴：把運算符號移動到對應的括號后面
? 則變成拉：((a(bc)*)+(de)+)-
? 把括號去掉：abc*+de+-后綴式子出現
2. ?需要注意的地方有：
a. 將數字append到stack中時，應該把數字轉換為int型
?b. ?注意計算順序。第一個pop出來的元素在運算符右邊，第二個pop出來的元素在運算符左邊?。。。?/p>
c. ?除法需注意： python中1/-22= -1，但leetcode要求 1/-22＝0，所以除法運算應寫為：
stack.append(int(float(num2)/float(num1))) ? 或者
#stack.append(int(num2*1.0/num1))
d. 判斷運算符時注意使用elif
139. Word Break ----- 動態(tài)規(guī)劃
維護一個數組dp， dp[i]=true 意味著 s[:i+1]在worddict中， dp[0]應該被初始為true?
dp初始化：dp = [False] * (len(s)+1) ? 注意長度應為s的長度再加1
雙層for循環(huán)，每次的判斷條件為dp[i]==true and s[i:j+1] in worddict， then dp[j+1]== true
最后返回結果為dp的最后一個元素dp［－1］
136.Single Number
利用每個元素出現兩次，以及位操作異或的性質來解決這個問題。因為兩個相同的元素異或結果是0，利用這個特點我們可以對所有數組元素進行異或，如果出現兩次的元素就會自行抵消，而最終剩下的元素則是出現一次的元素。這個方法只需要一次掃描，即O(n)的時間復雜度，而空間上也不需要任何額外變量
137. Single Number II
I like to think about the number in 32 bits and just count how many 1s are there in each bit, and "sum %= 3" will clear it once it reaches 3. After running for all the numbers for each bit, if we have a 1, then that 1 belongs to the single number, we can simply move it back to its spot by doing "ans |= sum << i" ;
This has complexity of O(32n), which is essentially O(n) and very easy to think and implement. Plus, you get a general solution for any times of occurrence. Say all the numbers have 5 times, just do "sum %= 5".
** 當把剩余的一個1 還原為十進制整數時，在python中需要注意負號的情況。
if i == 31: ? ?res -= 1<<31
For a 32 bit number, if i == 31, we are on the bit telling us whether the number is negative or not. if we are on the bit that tells us the sign, and the number that appears not three times has a 1 here", then take the largest 32 bit integer and subtract it from our res. If the number that we are looking for is negative, this will give the correct answer.
134. Gas Station
思路沒有問題，就是一直疊加balance += gas[i] - cost[i]。 需要注意的是，當balance小于0時，要對balance 和 start 進行更新：balance = 0; ?start = i + 1。意思就是從下一個station繼續(xù)出發(fā)。這是題目沒有說清楚的地方，即油不夠時，可以挪到下一個station重新開始。。
133. Clone Graph------圖問題
BFS用queue， DFS用stack。 用queue時是popleft()，從左邊取第一個。用stack是pop()，取最后一個。
125. Valid Palindrome
＊＊注意python中的字符串可以直接以數組的形式訪問，無需再改寫成數組。
＊＊ s[l].isalnum() 檢測字符串／字符 是否由字母或數字組成。not s[l].isalnum() 意思就是不是字母或數字
＊＊ 當字符串為空時，也算回文序列
129. Sum Root to Leaf Numbers
1. 注意邊緣情況：當樹為空時，返回 0??！ 跟257題思路相同，但邊緣情況返回值不同
120. Triangle－－－動態(tài)規(guī)劃
給定一個三角形，輸出最短路徑和。每一個元素只能向下一層與它相鄰的兩個元素移動。Each step you may move to adjacent numbers on the row below.
這道題比較適合從下往上遍歷，可以不用處理頭尾特殊情況。
先初始化一個數組用來存放當前行和下一行相鄰元素相加的最小和，注意?? 數組大小應該是triangle最后一行大小再加1. ?加1是因為要考慮最后一行的最后一個數組，參考動態(tài)規(guī)劃的遞歸式來理解：
rowmin[i] = row[i] + min(rowmin[i], rowmin[i+1])
這個遞歸式的含義是，對每一行的每一個元素，保存這個元素與下一行相鄰兩個元素中最小的那個的和。rowmin要初始化為0.
雙層循環(huán)結束后，rowmin的第一個元素就是minimum path，因為第一層只有一個元素。
時間復雜度為：把每個元素遍歷一次，需要 n^2
空間復雜度為：O(n)
116. Populating Next Right Pointers in Each Node
又是樹的題目。理解題意時有很重要的一點就是，因為已經初始化了所有的node的next指針為null，所以每一行最后邊那個node是不用管的，它的next已經指向了null。
使用一個pre指針，讓它總是指向root
while循環(huán)的判斷條件為while root.left，因為我們在當前行就可以執(zhí)行完下一行的任務，所以無需將root循環(huán)到最后一行。
if 循環(huán)的判斷語句為if root.next，意思是檢查當前root的next是指向空，還是已經指向了某個node，如果它不指向空，我們就root.right.next = root.next.left， 并把root.next作為新的root
如果它指向空，root = pre.left ; ?pre = root； ?我們就把pre.left作為新的root, 即向右移動了一個node。
