Remove time complexity: remove from a set is O(1), remove from a list is O(n)

deque.popleft() is faster than list.pop(0), because the deque has been optimized to do popleft() approximately in O(1), while list.pop(0) takes O(n)

Remove all items:?clear()

Remove an item by index and get its value:?pop()

Remove an item by value:?remove()

Remove items by index or slice:?del

一個具有n個節(jié)點的完全二叉樹,其葉子節(jié)點的個數(shù)n0為: n/2 向上取整，或者(n+1)/2 向下取整

key = ''.join(sorted(string))? ?sorted函數(shù)返回時一個list，不是string瓶殃，要特別注意

iterator next()作用在dictionary上返回的是key

float('-inf') -不能寫在‘’外面

& 用于兩個set的話鞠呈，可以得到intersection

collections.defaultdict(lambda: 1) 因為如果寫成int椎椰，默認值將是0哺呜，這樣寫是為了得到一個匿名函數(shù)

stack經(jīng)常只用來存儲index

迭代器的優(yōu)勢：在構建迭代器的時候宦棺，不是將所有的元素一次性加載瓣距，而是等調用next方法時返回元素，所以不用考慮內存的問題

迭代器的使用場景：數(shù)列的數(shù)據(jù)規(guī)模巨大代咸；數(shù)列有規(guī)律蹈丸，但是不能使用列表推導式描述

The join() method is a string method and returns a string in which the elements of sequence have been joined by str separator.

split返回list

判斷條件時，if 0 not in set呐芥，沒有那個is

random.randint(a,?b)逻杖，?Return a random integer?N?such that?a?<=?N?<=?b

most_common時間復雜度是O(nlogn)

sorted作用于dictionary后，返回的是排序好的keys

sorted之后返回的是list

sort只適用于list思瘟，sorted可以對任何interable變量進行sort

-1在計算機中表示：1的碼是0000....1弧腥，反碼是111111....0，因為負數(shù)的表示是正數(shù)的反碼加1潮太，所以-1是111111...1管搪，左移31就是10000000，代表計算機能表示的最小數(shù)

string.lowercase包含26個英文小寫字母

sys.maxsize: reports the platform's pointer size, and that limits the size of Python's data structures such as strings and lists.

計算機里面都是存的補碼铡买，是一個圈更鲁，最大數(shù)是127(01111111)，最小數(shù)是-128(10000000), 所以127+1后會出現(xiàn)溢出奇钞，然后就等于-128了

對于有符號位(最高位是1)澡为，補碼等于反碼加1

~x = -x-1 因為~x+1就是反碼加1，~x+1=-x

dictionary的setdefault和get是一樣的景埃，如果key不在dictionary中時媒至，dict.setdefault(key, default=None)會給一個默認的key和value

segment tree

binary indexed tree

backtracking一般和dfs一起用

一是只要遇到字符串的子序列或配準問題首先考慮動態(tài)規(guī)劃DP顶别，二是只要遇到需要求出所有可能情況首先考慮用遞歸

ord函數(shù)返回ASCII碼值，比如ord('a')等于97

strip() 方法用于移除字符串頭尾指定的字符（默認為空格或換行符）或字符序列拒啰。

http://www.runoob.com/python/att-string-strip.html

itertools.combinations_with_replacement()

這里replacement的意思是驯绎，取出來后又會放回去，所以有AA谋旦，BB剩失， CC， DD這種情況

heap的nlargest和nsmallest函數(shù)册着，返回的是一個數(shù)組

Minimax (sometimes MinMax or MM[1]) is a decision rule used in artificial intelligence, decision theory, game theory, statistics and philosophy for minimizing the possible loss for a worst case (maximum loss) scenario.

https://univasity.iteye.com/blog/1170216

heapreplace函數(shù)彈出最小元素將另一個元素加入堆：

heapq.heapify復雜度是O(n)拴孤，in-place的。heapq.heappop時間復雜度是O(logn)

max heap頂端是最大的

Quickselect Algorithm：

https://www.geeksforgeeks.org/quickselect-algorithm/

ljust()?方法返回一個原字符串左對齊,并使用空格填充至指定長度的新字符串甲捏。如果指定的長度小于原字符串的長度則返回原字符串演熟。str.ljust(width[, fillchar])? fillchar -- 填充字符，默認為空格司顿。

異或或者與都可以直接對integer進行操作

^位異或芒粹，&位與

The bin() method returns the binary string equivalent to the given integer.

bin(5) = '0b101'

external sort:?

In principle, we want minimize the number of disk access during the run-time.

set和set可以用&求得它們的交集

https://www.w3schools.com/python/python_lambda.asp

對于回文問題，使用Manacher's algorithm可以答到O(n)時間

遇到一個數(shù)組免猾，如果是想求其最大是辕，最小囤热，最長猎提，最短值，而并不需要知道具體解的題旁蔼，可以考慮使用動態(tài)規(guī)劃

Subsequences don't allow you to move characters around, only either keep them or remove them. Substrings don't allow you to remove anything and so must be contiguous.?

dict.items(): Return a?copy?of the dictionary’s list of (key, value) pairs.?

dict.iteritems(): Return an?iterator?over the dictionary’s (key, value) pairs.

takes more space and time initially, but accessing each element is fast, whereas the second takes less space and time initially, but a bit more time in generating each element.

dictionary是有iteritems()函數(shù)的锨苏，得到一個迭代器，迭代器有next()功能

Boyer-Moore Majority Vote algorithm

https://leetcode.com/problems/majority-element-ii/discuss/63520/Boyer-Moore-Majority-Vote-algorithm-and-my-elaboration

摩爾投票升級版棺聊，超過n/3的數(shù)最多只能有兩個伞租；

建立hashtable的時候，key一定要是unique的限佩，比如對一個字符串的index和value建立hashtable的時候葵诈，index是不同的，value是可以一樣的祟同，所以key必須是index

stack.pop()和queue.pop()不一樣作喘，stack是pop最上面的，queue是pop最右邊的

a tree is an undirected graph in which any two vertices are connected by?exactly?one path. In other words, any connected graph without simple cycles is a tree.

拓撲排序中可以用到DFS和BFS晕城，但是BFS是主流

set("HelloWorld") 得到結果是{'e', 'H', 'r', 'W', 'o', 'd', 'l'}

items和iteritems?

https://www.cnblogs.com/life-need-high-power-laser-gun/p/7518803.html

入度：

常用的topological sort有兩種：O(n)時間排序

Kahn's Algorithm：BFS based, start from vertices with 0 incoming edge, insert them into list S, at the same time, we remove all outgoing edges, after that find new vertices with 0 incoming edges and so on

Tarjan's Algorithm: DFS based, loop through each node of the graph in an arbitrary order,?initiating a depth-first search that terminates when it hits any node that has already been visited since the beginning of the topological sort or the node has no outgoing edges

拓撲排序：將有向無環(huán)圖的所有頂點排成一個線性序列泞坦，使得對圖中的任意兩個頂點u，v砖顷，如果存在邊u->v贰锁，那么在序列中u一定在v的前面赃梧，這個序列又叫拓撲序列。

有向無環(huán)圖：如果一個有向圖的任何頂點都無法通過一些有向邊回到自己豌熄，那么這個有向圖叫有向無環(huán)圖(DAG: directed acyclic graph)

使用sqrt的時候授嘀，要加一個math.sqrt()

BFS 二叉樹的時候，注意如果在while循環(huán)里面使用了pop房轿，則queue里面就沒有這個node啦粤攒，后面如果還想用就會出錯；下圖中后面想用的時候就是空了

這樣判斷是不是square數(shù)不行囱持，要么就加一個int(num**0.5)==num

DFS有時候從大數(shù)開始可以更快的得到結果

長方形是rectangle夯接，正方形是square

求距離場BFS是不二之選

想要得到最小步數(shù)等問題，可以使用heap

要返回True和False的話纷妆，初始化dp數(shù)組的時候盔几，就初始化成True或者False，不能寫成0或者1掩幢，在python里是不一樣的

dic.get(key)可以防止返回key錯誤

python中get()逊拍，如果鍵不存在，則會返回None际邻，所以在計數(shù)的時候芯丧，不要當做返回0來處理

DFS應用在matrix的時候，一定要注意visited情況世曾，如果visit過的再visit的話缨恒，很容易出現(xiàn)超時的情況，可以用設置visited為一個set轮听，將visited過的加到set中去

from在python中是一個關鍵字骗露，定義變量時不要用它

pop還有刪除的功能，所以在需要取出和刪除操作時血巍，就直接用pop

在寫上面的code時萧锉，我經(jīng)常會犯錯誤，就是把dfs(newStart)和if對其述寡，這是不對的柿隙，因為newStart是依賴上面一行得到的結果的

string.startswith(word) 應該是string的一個常用函數(shù)，要學會利用起來

list不能當做hashtable的key

如果一個數(shù)是ugly number鲫凶，則它乘以2 or 3 or 5也是ugly number

Ugly numbers are?positive numbers?whose prime factors only include?2, 3, 5.?

1?is typically treated as an ugly number.

還是要多在本子上話禀崖，這樣容易得到思路一些

遇到不懂的code，一句一句弄懂掀序，打印出來看帆焕，在本子上畫

dic[x].pop(0)直接省去remove的操作了

Eulerian Path 歐拉回路

undirected graph: len(edges)就是node的個數(shù)

更新rank的時候，如果兩個rank不一樣的話，把小的merge到大的，這樣都不用更新rank，但如果兩個rank一樣的話久锥，需要更新rank值

union find的思想是每個個體先初始化成不同的群主乙漓，然后遍歷有關聯(lián)的兩個個體，如果發(fā)現(xiàn)find的值不同，則手動將二者加入到一個群主，然后總群主數(shù)減1

union find的時候，是把rank小的合并到rank大的那個上谦炒，因為這樣可以少一些path compression的操作

x = parent[x] = i, j? 代表(i, j)做為一個tuple賦值給x和parent[x]

union find用來解決network connectivity問題

cmat = copy.deepcopy(mat) 如果直接傳mat，會修改mat的值风喇，因為python里面matrix宁改，list屬于object，傳參數(shù)的時候傳的是inference也就是指針魂莫。像variable這種就沒關系

str object doesn't support item assignment

string 才能join还蹲，int不能join

list(N) N是整數(shù)，這是錯誤的耙考，整數(shù)不能被list

MSB：most significant bit

greedy算法

divide and conquer：把一個問題分成等價的子問題谜喊，分別進行解答，最后再把結果合并

第一步：把每個結點的根節(jié)點指向它自己倦始，這樣就有n個cluster斗遏，rank都初始化成0。find的過程把當前結點和它的父母結點都指向root結點鞋邑；在find中诵次，當這個結點不是根節(jié)點時，

union by rank：rank的話可以看成是平均長度炫狱，把low rank的cluster merge到high rank的cluster藻懒，這樣可以 減少做path compression的次數(shù)

path compression：每次尋找某個結點的root時剔猿，就把此node的所有父母結點指向root视译，這樣相當于flat了整個cluster，下一次查找的時候就直接是O(1)時間了

union find: 有find和union归敬，find的話就是找某個node的root或者叫cluster id酷含。總的node數(shù)是n汪茧。union是merge兩個cluster椅亚。查找兩個node是否在同一個cluster中，就是看它們的root是不是同一個舱污，查找時間是O(1)

無向連通圖：undirected graph.

alphanumeric 代表數(shù)字字母兩種呀舔；s[l].isalnum()判斷是否是字母和數(shù)字

collections.Counter()也是一個hash table

enumerate也可用在string上

sliding window+substring template: the question is always that given a string, and need to find a substring which satisfy some restrictions. A general way is to use a hashmap with two pointers.?https://leetcode.com/problems/minimum-window-substring/discuss/26808/Here-is-a-10-line-template-that-can-solve-most-'substring'-problems

1 check whether the substring is valid; 2 two pointers: one to tail and one head; 3 get the length of substring; 4 initialize the hash map; 5 while loop:?

動態(tài)規(guī)劃，當前狀態(tài)需要依賴前一狀態(tài)的值

subarray必須是連續(xù)的

binary search：中間值下標的計算扩灯，如果寫成(l+h)/2媚赖，l+h有可能會溢出霜瘪，從而導致數(shù)組訪問出錯；改進的方法是l+((h-l)>>1)

sliding window: standard template：記錄左指針惧磺，右指針颖对，每個循環(huán)更新左指針，右指針是當前index磨隘；外循環(huán)遍歷整個數(shù)組缤底，內部一個while循環(huán)遵循題意要求；一個全局變量更新題意要求

binary search: while l<r番捂，這里什么時候是小于號个唧，什么時候是小于等于號

求極值的問題，會用到dp

sum(list)直接就可以得到和设预。不需要sum(n for n in list)

dic=collections.defaultdict()? sorted(dic, key=lambda k: dic[k]) 得到的是

str()是把integer轉換成string

*也可用作解包坑鱼，func(*args)函數(shù)時，相當于把一個元組args拆開絮缅，當成參數(shù)傳進函數(shù)中鲁沥。

*代表該位置可以接受任意多個非關鍵字參數(shù)，在函數(shù)中將其轉化成元組

200 itertools.product(A,B)耕魄，依次取出A中的一個元素和B中的一個元素組成一個元組画恰，然后將所有的元組形成一個列表返回。比如itertools.product([1,2,3],[100,200])吸奴，返回[(1, 100), (1, 200),(2, 100),(2, 200),(3, 100),(3, 200)]

199 tuple一旦初始化就不能修改了

198 hash tables: hash set和hash map

197 -first, indf = heapq.heappop(heap)允扇，不能這么寫，前面不能加負號

196 全局變量要加self则奥，比如self.global

195 string中找到所有字母''.join(re.split(r'[A-z]',licensePlate))

194 re中[A-z] 等于[A-Za-z]表示匹配所有大小寫字母

193 動態(tài)規(guī)劃解決0-1背包問題步驟：（1）選擇一個給定物品i考润，需要比較選擇i形成的子問題最優(yōu)解和不選擇i的子問題最優(yōu)解，再對兩個子問題進行比較读处，選擇最優(yōu)的糊治。https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/

192 部分背包問題：總是選擇每一磅價值（Vi/Wi）最大的物品添加到背包中。解決過程：對每磅價值進行排序罚舱，依次從大到小選擇添加進背包中

191 0/1背包問題：在選擇是否把一個物品加到背包中井辜，需要對把這個物品加到背包的子問題和不加到背包的子問題進行比較。這種方式形成的問題導致了很多重疊子問題管闷，滿足動態(tài)規(guī)劃的特征

190 0/1背包粥脚，動態(tài)規(guī)劃；部分背包包个，貪心法

189 0/1背包問題：0/1 knapsack problem刷允，for each number, we can pick it or not。https://blog.csdn.net/crayondeng/article/details/15784093

188 除以2，可以>>1树灶，向右移動一位

187 判斷是奇數(shù)偶數(shù)搀菩，還可以和1按位與，如果與的結果是0破托，則為偶數(shù)肪跋，否則為奇數(shù)

186 put n items to k buckets

185 求取約束條件下最小路徑的題，用dynamic programming

184 extend()用于在隊列末尾一次性追加另一個序列中的多個值

183 hash table and trie 時間和空間復雜度比較https://leetcode.com/explore/learn/card/trie/147/basic-operations/1048/

182 python中get()土砂，如果鍵不存在州既，則會返回None

181 Binary search: search for a specific value in an ordered collection

180?ret = [None]*k可以得到[[],[],[]];?ret = [1]*k 得到[1,1,1]

179 linked list，如果之后要斷掉某個連接萝映，但之后還得用到這個連接吴叶，那就先保護好這個連接

178 怎么建立一個cyclic linked list

177?when you delete a node, you will delete its left child and its right child before you delete the node itself.

176 cur = cur.next的前提是cur.next已經(jīng)是一個linked list node了

175 對于鏈表，只要node.next變了序臂，之前的連接就是斷了的; 指針并不是node

174?return [hashmap[i] for i in sorted(hashmap)] 可以直接對hashmap進行sort

173 iterative方法中蚌卤，在中間只要不滿足條件的，就返回False奥秆，直到最后所有條件都滿足時逊彭，才返回True；

172 BFS和queue的時候构订，在while queue循環(huán)的時候侮叮，queue = [kid for q in queue for kid in (q.left, q.right) if kid]省memory

172?collections.deque(maxlen=size)可以設置一個最長len，這樣如果queue滿了悼瘾，append進來的數(shù)也會擠掉前面的數(shù)囊榜，不用再pop了

171 deque: 建立一個deque，d=collections.deque(); 加入元素是d.append(); 從左邊加入元素是d.appendleft(); 從左邊刪除元素是d.popleft(); 寫成d=collections.deque()了亥宿，就不需要import deque了

;170?collections.defaultdict(lambda: defaultvalue) lambda在這里的作用是代表設置的默認值

169?defaultdict()為字典提供默認值卸勺，防止出現(xiàn)keyerror異常

168 "/".join(stack) 如果stack中只有一個element，則/不作用在此element上烫扼，比如stack中是home曙求，運行這個code后，還是變成home

167 建立一個heap材蛛，直接heap = []就行圆到，之后再進行heapq.heappush(heap, k)等操作

166 在計算機中怎抛，32bit最大能表示成2**31-1卑吭，因為最高位是符號位

165 str.split()要里面真有space才行，比如“12”马绝，split后還是‘12’豆赏，并不會得到‘1’和‘2‘

164 遇到circle的，就可以把list復制兩份連在一起

163 set require its items are hashable: such as immutable types, string, tuple and number

162 list is mutable and can't be used as a key for dict

161 unhashable type: 'list'

160 deque的定義要么是：from collections import deque;另外一種更簡單的方法是直接定義：d=collections.deque

159?union find:研究動態(tài)連通性

158 ".join()和‘ ’.join()中間有無空格時不一樣的

157 find返回子字符串開始的位置

156 for BST, inorder traverse is an ascending sequence

155 random.randint(a,b)生成一個指定范圍內的整數(shù)，即生成的整數(shù)n滿足：a<=n<=b

154?heapq.heapify(self.heap)是in-place的掷邦，不要寫成self.heap =?heapq.heapify(self.heap)

153 heap[0]是最上面那個數(shù)白胀，stack[-1]是最上面那個數(shù)

152 如果是import heapq的話，調用任何heap相關函數(shù)抚岗，前面都要加heapq.

151 max heap就是min heap的invert

150 使用heapq的時候或杠，直接import heapq就可以了

149 self只在類的方法中才有，在獨立的函數(shù)中是沒有必要帶的宣蔚，self在定義類的方法時必須有向抢，在調用的時候會自動傳入；self就是指類實例對象本身

148 query疑問胚委，質問

147 dic.pop('key', None)刪除字典中的key挟鸠，如果key不存在，返回None亩冬，因為不會產(chǎn)生keyerror

146 decimal小數(shù)的

145 str.isalpha()只是字符艘希，像[這種特殊字符，并不能用這個來判斷

144?[::-1] the the best and the fastest way to reverse a list.

143 list.pop()默認是pop最后的那個元素硅急，所以我們如果想pop最開始的元素覆享，需要把參數(shù)設置成0

142 list.index(element)返回element的index，time complexity是O(n)

141 注意注意注意：push到heap中营袜，是按照push進去的第一個緯度來衡量最小值的Ｑ驼妗！连茧！比如計算最小步數(shù)核蘸，一定要把steps放在最前面哇

140?type start: List[int]?

139 總是忘記把heap寫進heapq.heappop(heap)中去

138?float('inf') 里面是有‘’的

137 re.findall(pattern, string)，返回string中與pattern相匹配的所有字串啸驯，返回形式為list

136 c.items()返回的就是list客扎，比如

135 lookup的時候，set比list快

134 s.lower(), s.upper()不要記混淆成s.lowercase()

133 正則表達式的split: re.split(“\W+”,paragraph)

132?\w：用于匹配字母罚斗，數(shù)字或下劃線字符徙鱼； \W：用于匹配所有與\w不匹配的字符；

131 string.split()返回list

130 string.split()會改變string本身嗎针姿？還是會產(chǎn)生一個copy袱吆。貌似不改變本身

129?heappushpop() 將值插入到堆中同時彈出堆中的最小值。?heapq.heappushpop(heap, item)?????#首先判斷添加元素值與堆的第一個元素值對比距淫，如果大于則刪除最小元素绞绒，然后添加新的元素值，否則不更改堆

128 maxheap

127 heapify()以線性時間將一個列表轉換成堆

126 刪除并返回heap中最小的元素榕暇，使用heapify()和heappop()來實現(xiàn)

125?set.remove(item)

124 denomination面值

123 從0變成1蓬衡，從1變成0喻杈，可以用1-matrix[i][j]來實現(xiàn)

122 初始化一個矩陣，dp = [[1]*n for i in range(m)]是先弄一整行狰晚，然后再traverse行數(shù)

121 寫新的內部函數(shù)的時候筒饰，一定要放在最前面，方便調用

120 寫程序時寫完一句就檢查一下壁晒，養(yǎng)成一遍寫好所有程序的習慣

119 看到別人的好建議瓷们，就馬上執(zhí)行

118?Btw, it's extremely useful to write down your thought/demo in comments before you actually start to write the code, especially during interview.?Even if you do not solve the problem finally, the interviewer at least get to know what you're thinking.?And if you don't get the problem right, he/she will have a chance to correct you.

117?Divide And Conquer(分治法)：

116 只寫return，代表的就是return None秒咐，只是在這省略了None换棚；

115?consonant 輔音字母

114?for i in range(len(rooms)):? 老是忘記寫range

113 局部函數(shù)一般寫在前面

112 yield是一個類似return的關鍵字，只是這個函數(shù)返回的是一個生成器

111 generator可以有效節(jié)約系統(tǒng)資源反镇，避免不必要的系統(tǒng)占用

110 帶有yield的函數(shù)在python中稱為generator固蚤；這個函數(shù)和普通函數(shù)不一樣，看起來像函數(shù)調用歹茶，但不會執(zhí)行任何代碼夕玩，直到對其調用next()才開始執(zhí)行，在for循環(huán)中自動調用next()惊豺。每執(zhí)行到一個yield語句就會中斷燎孟，并返回一個迭代值，下次執(zhí)行從yield的下一個語句開始執(zhí)行

109 兩個矩陣相乘尸昧，第一個矩陣的列數(shù)要和第二個矩陣的行數(shù)相等揩页，最后的出來的矩陣行數(shù)是第一個矩陣的行數(shù)。列數(shù)是第二個矩陣的列數(shù)

108?forty 四十

107 bin函數(shù)返回的就是string

106 int(a, 2)代表以2為base烹俗，即把string a按照base為2轉換爆侣，比如int('11',2)=3, 如果是int('11')=11，默認base是10

105 不管是Counter還是hashmap幢妄，都有values這個成員函數(shù)兔仰，collections.Counter(tasks).values()

104 python的數(shù)據(jù)類型分為mutable和immutable兩種類型，mutable: list和dict蕉鸳，immutable：int,string, float, tuple

102 python中逗號

101 線性時間就是O(n)

100?sorted(L, key = len) 按len來排序

99 for循環(huán)本質上是通過不斷調用next()函數(shù)實現(xiàn)的

98 iterator甚至可以表示一個無限大的數(shù)據(jù)流乎赴，比如全體自然數(shù)，但使用list是不可能存儲所有自然數(shù)的

97 可以把這個數(shù)據(jù)流看成是一個有序數(shù)列潮尝，但我們不能提前知道這個有序數(shù)列的長度榕吼，只能不斷通過next()函數(shù)實現(xiàn)按需計算下一個數(shù)據(jù)。所以iterator的計算是惰性的勉失，只有在需要下一個數(shù)據(jù)的時候羹蚣，它才會計算

96 可以被next()函數(shù)不斷調用并返回下一個值的對象稱為iterator；可以作用于for循環(huán)的對象稱為iterable戴质，比如list度宦，tuple踢匣，str告匠，dict戈抄，set，generator后专；list划鸽，str，dict是iterable戚哎，但不是iterator裸诽；iter()函數(shù)可以把list，str型凳，dict等iterable轉成iterator丈冬；iterator對象表示的是一個數(shù)據(jù)流，可以被next()函數(shù)不斷調用返回下一個值甘畅，直到?jīng)]有數(shù)據(jù)埂蕊。

95 escape character轉義字符；\n換行疏唾，\t橫向制表符?ASCII Horizontal Tab (TAB)

94 DFA：deterministic finite automaton蓄氧，是一個含有5個元素的tuple（S，q0槐脏，T,? F喉童，），S：狀態(tài)的集合顿天，q0：初始化狀態(tài)堂氯，T：transition function, F: 結束狀態(tài)的集合，??是全部的字母表牌废。

93 str.isalpha()全部是字母就返回True祖灰，否則返回False

92 index超出范圍，總是出這樣的錯畔规，一定要細心啊; 一定要從最簡單的開始考慮

91 在紙上寫testcase

90 二分查找法時間復雜度：O(logn)

89 list和string都有count函數(shù)

88 創(chuàng)建一個圖局扶，首先也得創(chuàng)建一個root

87 union find，并查集叁扫，是解決動態(tài)連通性的一種很高效的數(shù)據(jù)結構三妈。

86 queue因為是list，所以添加元素的時候莫绣，可以用queue+= i

85 any() 和 all()的區(qū)別畴蒲。any()判斷對象是否為空對象，如果都是空对室，0模燥，false咖祭，返回false，如果不都返回空蔫骂，0么翰，false，返回True辽旋；all()浩嫌，如果里面所有元素不為0，空补胚，false码耐，則返回True，但是all(x)如果x是個空對象溶其，則返回True

84 從現(xiàn)在開始骚腥，看到一道題，就模擬是在面試瓶逃，認真讀題束铭，積極思考，用英語說

83 id, type也是關鍵字

82 在最開始時除了要初始化好需要用的stack什么的金闽，也要注意初始化一個返回array纯露，或者返回value

81 deque是雙端隊列，可以從兩端append數(shù)據(jù)代芜；如果想實現(xiàn)隨機訪問埠褪，用list好些；queue是隊列挤庇，先進先出

80 二分圖：指頂點可以分成兩個不相交的集钞速，同一個集內的頂點不相鄰，即沒有共同邊

79? 圖的遍歷既可以用BFS嫡秕，也可以用DFS

78 undirected graph: 無向圖渴语，邊沒有方向；G=<V,E> V是頂點集昆咽，E是邊集驾凶，是由V中元素構成的無序二元組

77?temp, i = divisor, 1 寫成兩行就TLE了？

76 看找到思路了掷酗，再去看別人的答案调违，思路都不知道，就去看答案泻轰，肯定看不懂技肩，就會浪費很多時間

77 DFS中是一定會存在遞歸調用的，在dfs循環(huán)體中值需要考慮當前節(jié)點就行浮声，下面的直接遞歸調用

76 if not i這樣的判斷語句代表如果i為False虚婿，就可以執(zhí)行if下面的語句

75 python中is和==的比較：==是對比兩個對象的內容是不是一樣的旋奢，即內存地址可以不一樣，只要內容一樣就行然痊；is是判斷兩個對象的內存地址是不是一樣至朗，是不是同一個對象

74?dividend：被除數(shù)，divisor：除數(shù)

73 通常用于求解某種具有最優(yōu)性質的問題玷过，一般用于多階段決策問題爽丹。

72 貪心算法筑煮，greedy algorithm辛蚊，只是局部最優(yōu)解，沒有從整體最優(yōu)上加以考慮

71 鏈表的node真仲，是包含值和指針的袋马，指針就是指向的地址，所以當我們把head node放置在隊伍中去的時候秸应，因為有指針虑凛，所以就可以找到它后面的node

70 建立dummy head和head一樣，建好后一般會設置一個curr指針來幫助建立后面的node

69 heap和stack區(qū)別：heap像一堆金字塔型泥沙软啼，stack像一個直立垃圾桶桑谍；heap也是priority queue，按照元素的優(yōu)先級取出元素祸挪；heap性質：任意節(jié)點小于或大于它的所有后裔，最小元或者最大元在堆的根上；heap總是一顆完全樹婚脱，即除了最底層嘱吗，其它層的節(jié)點都被元素填滿，且最底層盡可能地從左到右填入整以；heap實現(xiàn)：主要是插入和刪除最小元素胧辽，元素值本身是優(yōu)先級鍵值，小元素享有最高優(yōu)先級公黑；插入或者刪除之后邑商，heap還是要保持為一顆完全樹，即完全二叉樹和每個節(jié)點值都小于或者等于它的子節(jié)點

68 Queue類凡蚜，F(xiàn)IFO人断；Queue.PriorityQueue, lowest valued entry retrieved first.

67 復制鏈表的方法：創(chuàng)建一個hashmap，舊節(jié)點是key番刊，新節(jié)點是value

66 next()返回迭代器的下一個項目

65 items函數(shù)含鳞，將一個字典以列表的形式返回，因為字典是無序的芹务，所以返回的列表也是無序的蝉绷，比如a = {‘a(chǎn)’:1, 'b':2}, a.items(), 輸出的結果是a = [('a',1), ('b', 3)]; iteritems()返回的是一個迭代器鸭廷，b=a.iteritems(), list(b)=[('a',1), ('b', 2)],?字典.iteritems()方法在需要迭代結果的時候使用最合適，而且工作效率很高

64 map查找時間是O(logn)熔吗，hashmap查找時間是O(1)

63 單鏈表插入刪除的時間復雜度為O(n)辆床，雙鏈表為O(1)

62 del用于list列表操作，刪除一個或者連續(xù)幾個元素桅狠，比如a=[1,2,3,4], del a[0], 則a=[2,3,4]

61 collections模塊中有一個子類OrderedDict讼载，可以對字典對象中的元素進行排序，會根據(jù)輸入的順序放置

60 建立字典樹Trie需要先建立一個TrieNode, init函數(shù)里有self.children中跌； 建立binary tree也需要建立一個TreeNode的class咨堤，init函數(shù)里是當前節(jié)點的self.val=x, self.left=None, self.right=None; Linked list有ListNode， init函數(shù)里特有屬性self.val=x, self.next=None

59 trie也叫prefix tree

58 DFS就像走迷宮漩符，一條路走到頭了再返回走另外一條路一喘。比如下面一張圖，從1開始搜索嗜暴，找到了2凸克，2又找到3，3找到4闷沥，4找到5萎战，然后無路可走（因為5周圍的走過了），返回到4舆逃，從4到6

BFS的話蚂维，就是從1開始，2和5找到了颖侄，然后從2開始找鸟雏，3找到了，再從5找览祖，4找到了孝鹊，接著走3，沒有路可走展蒂，再從4開始又活，6找到了；BFS的話就是要找到與該節(jié)點相鄰的所有節(jié)點

57 初始化一個矩陣code：[[1,2,3,4,5],? [1,2,3,4,5] ]锰悼，每一行和每一行之間用‘柳骄，’連接，每一行所有元素間用[]包括箕般，每個元素間用‘耐薯，’連接；所以如果要全部初始化為0，則code為：[[0 for i in range(0,n)] for j in range(0,n)]

56 極值的問題考慮使用動態(tài)規(guī)劃

55 已知三角形兩邊a和b曲初，以及夾角C体谒，則三角形面積是1/2*absinC

54 operator.mul()

53 reduce函數(shù)會對參數(shù)序列中的元素進行累積；reduce(function, iterable)臼婆，如果fucntion中有兩個參數(shù)抒痒，比如lambda函數(shù)，則將集合中的第一第二個元素進行操作颁褂，再和之后的元素進行依次操作

52 list+list=list故响，比如[1, 2, 3]+[4, 5 ,6]=[1, 2, 3, 4, 5, 6]

51 遇到排列組合，可以結合stack做颁独，因為stack返回的就是list彩届，表示成[]，返回到res中就是一個一個[]奖唯，最后是[[]]

50 一直讓loop循環(huán)惨缆，知道滿足條件再跳出循環(huán)糜值，可以用while True

49 combinations是backtracking的一個application

48 從大到小遍歷丰捷，要用range(max, min, -1)，此處的-1不能省掉

47 列出所有結果的題用recursive

46 backtracking: ORT原則寂汇，options, restraints, termination

45?[::-1]是reverse的意思病往，time complexity is O(n), [:-1]才是去掉最后一個字符的意思

44 list也是個關鍵字

43 還是沒有徹底弄清楚DFS和BFS

42 ord()將character轉換成unicode integer 或ASCii碼值；‘a(chǎn)’的ASCii值是97骄瓣，‘A’的ASCii碼值是65

42 range(1, n+1)我老是喜歡寫成range(1:n+1)

41 遇到困惑就要去解決停巷，比如知道刷了的題還是會忘記，那就在第二天榕栏，第四天畔勤，第八天。扒磁。庆揪。花很短的時間去復習下

40?memorization存儲調用函數(shù)的結果妨托，當相同的參數(shù)傳進來的時候缸榛，直接返回值就行了。在遞歸函數(shù)中用得比較多

39 memorization技術：就是把每次函數(shù)執(zhí)行的結果存儲在鍵值對中兰伤，在接下來的執(zhí)行中内颗，現(xiàn)在鍵值對中查找是否有相應執(zhí)行過的值，如果有敦腔，直接返回該值均澳，沒有的話才真正執(zhí)行函數(shù)體的求值部分。在鍵值中找值比去執(zhí)行函數(shù)快多了。

38 2的3次方找前，2 to the power of 3

37 遇到Parenthesis的題筒捺，就可以用count來做

36 backtracking回溯法，是一種搜索嘗試過程纸厉，當發(fā)現(xiàn)不滿足條件時系吭，就退回來尋找新的路徑，退回來這個過程就是回溯颗品。是一種系統(tǒng)搜索問題解的方法肯尺。使用DFS的方法。適用于求解組合數(shù)較大的問題躯枢≡蛞鳎回溯問題遞歸函數(shù)模板：

1 ）最開始寫好跳出條件，滿足條件才加到總結果中

2） 已經(jīng)拿過的數(shù)不再拿

3）遍歷過當前節(jié)點后锄蹂，為了回溯到上一步氓仲，需要去掉已經(jīng)加入到list中的當前節(jié)點

35 open parenthesis 是左括號的意思

34 deque.popleft獲取最左邊的元素并刪除

33 對于stack來說，最上面的元素可以通過stack[-1]來得到

32 設計一個class得糜，class的成員函數(shù)間是可以調用的敬扛，我經(jīng)常忘記調用其他的函數(shù)

31 queue.peek()只是看這個值，并沒有刪除這個值的意思

30 Manhattan distance: 曼哈頓距離朝抖，兩點之間南北方向和東西方向的距離之和

29 迷宮問題：maze problem

28?perfect binary tree：all leaf nodes at the same level, and all internal node has degree 2; full binary tree: each node has zero or two children;?

27 DFS遞歸需要棧啥箭，所以空間復雜度是O(logn)；BFS也需要用隊列治宣，也需要extra space

26?self.sums = [[0 for j in range(c+1)] for i in range(r+1)] 因為對于matrix來說急侥，是list[list[int]]，所以初始化的時候要兩對[]侮邀，其中里面那對先按照column遍歷坏怪，因為其存儲的就是一行，然后外面一層才是按row遍歷

25 在草稿紙上多寫幾個例子找規(guī)律

24 for b in zip(*xmap) 在這句code中绊茧，zip中是unpacked的individual字符串铝宵，每一個individual字符串是32長度的num轉換來的，這樣在每一次for循環(huán)中按傅，b先取每個字符串的第一位捉超，這樣b的長度就是32的tuple，然后調用tuple.count()

23 總是忘記使用string.count()這個函數(shù)唯绍，比如想統(tǒng)計string中‘a(chǎn)’的個數(shù)拼岳，可以寫成string.count('a')

22 python中*的作用是unpack list to individual arguments，比如zip(*['0100','1110','0010'])等于zip('0100','1110','0010')

21?'{:032b}'.format的作用是將輸入?yún)?shù)轉換成32位無符號數(shù)字符串

22 set()和{}都可以用來創(chuàng)建集合况芒，但要創(chuàng)建一個空集合的話惜纸，只能用set()叶撒，因為{}是創(chuàng)建字典的。創(chuàng)建過程是{‘a(chǎn)’, 'o', 'e', 'i', 'u'}, set('aoeiu')耐版，set('aoeiu')運行后為set([‘a(chǎn)’, 'o', 'e', 'i', 'u'])祠够。原來set中也是一個list，無序不重復結合

21 set的in operation比string的in operation要快些粪牲，所以在做lookup的時候古瓤，盡量用set

20 map(f, list)將f函數(shù)作用在list的每一個元素上，一個一個mapping腺阳，所以叫map函數(shù)

19 str.format()落君，可以接受很多個參數(shù)，可以在format函數(shù)里面對應賦值亭引，也可以在format()函數(shù)里面給變量賦值

18 一定要避免使用兩個for loop绎速，一般都會time limited

17 每刷一題，分析時間復雜度和空間復雜度

16 sum是python關鍵字焙蚓，可以用sums

15 二叉搜索是纹冤，每個節(jié)點的值比它左子樹的任意節(jié)點值大，比它右子樹的任意節(jié)點值小

14 先要把題意弄明白购公，然后想明白該怎么做萌京，最后再寫code

13 二叉查找樹的中序遍歷是遞增序列

12 set(['John','Jane','Jack','Janice'])中存字符串是這樣存的，set([1, 2, 3]) 存number

11 trie的兩個應用君丁，詞頻統(tǒng)計枫夺，也可以用hash和堆來做，可是沒有trie節(jié)省空間绘闷，因為字符的公共前綴是用同一個節(jié)點來存的

10 trie的insert和search time complexity都是O(k)，k是key的長度较坛，trie的缺點是space complexity高印蔗；

9 由于trie可以最大限度地減少字符串比較，所以可用于詞頻統(tǒng)計和大量字符串排序丑勤；優(yōu)點是最壞情況時間復雜度此hashtable好华嘹。也有key到value的映射，但這里的key是字符串

8 trie中的key通常是字符串法竞，根節(jié)點不包含字符耙厚，除根節(jié)點以外的所有節(jié)點都包含一個字符，從根節(jié)點到某一個節(jié)點岔霸，所有的字符連接起來薛躬，就是該節(jié)點的字符；每個節(jié)點的所有子節(jié)點包含的字符串不相同呆细。

7 set.add() list.append()

6 普通dict和collections.defaultdict()的區(qū)別型宝，普通dict添加和查找元素都可以用dict[key]=value來實現(xiàn)，但是在查找的時候，如果key不在字典中趴酣，則會出現(xiàn)keyError梨树；但是 collections.defaultdict()就能解決這個問題，當key不存在時岖寞，可以返回default factory function的默認值抡四，這里factory function可以是set, list, str，int仗谆，set的默認值是set()床嫌，list默認值是[]，str默認是是空字符串胸私，int默認值是0

1 collection是python中的一個集合模塊厌处，里面包含很多集合類，和隊列相關的集合類是deque

2 初始化一個queue岁疼，collections.deque(maxlen=size)這里需要初始化queue的長度

3 hashMap和hashSet的區(qū)別：hashMap實現(xiàn)了map接口阔涉，hashSet實現(xiàn)了set接口；hashMap調用put添加元素捷绒，hashSet調用add添加元素瑰排；hashMap是鍵值對，hashSet只有值暖侨；hashMap相對于hashSet來說快些椭住，因為是使用唯一的鍵值獲取對象；hashMap使用鍵值獲得hashcode字逗，hashSet使用對象得到hashcode

https://www.cnblogs.com/codercui/p/6841730.html

4 bisect模塊京郑，在使用這個模塊前，要確保array是排好序了的葫掉；bisect模塊的幾個函數(shù)些举，第一個是bisect.bisect_left(L, x)查找x在L中的位置，如果x在L中俭厚，則返回x左側的位置户魏，如果不在L中，則返回插入的位置挪挤；bisect_right(L,x)叼丑，如果x在L中，返回x右側的位置扛门，如果不在L中鸠信，返回應該插入的位置；bisect.insort()就是插入元素之后還是保持array是排序的; 調用bisect.bisect的時候尖飞，其實是在調用bisect.bisect_right; 調用bisect.insort的時候症副，其實是在調用bisect.insort_right

5 因為bisect_left和bisect_right是為了查找需要插入的位置店雅，所以bisect_left就返回插入數(shù)在最左邊的位置就好了，因為插入進去也是會插入到這個位置贞铣；但是bisect_right是會返回當前位置加1的闹啦，因為插入的話會插到當前位置加1上；bisect.insort_left的話是真正把這個元素插進去了辕坝，返回插入后的序列窍奋，left的話就插在左邊，right的話就插在右邊

201 bisect.insort()是插入后再排序酱畅，時間復雜度是O(n)

200 在python里面琳袄，/做除法的時候，如果想得到小數(shù)部分纺酸，floating point的結果窖逗，可以把除數(shù)寫成float的形式

199 sum vector is O(n) time

198 想建立一個固定長度的array，比如一個固定長度的sliding window餐蔬，可以是[0]*size碎紊，我之前是self.window = [:size]，這樣是不行的

197?collections.defaultdict(list)和dict.setdefault()等價樊诺，但是collections.defaultdict()比dict.setdefault()更快

196 dic.get(key, value) 尋找key對應的值仗考，如果key不在dic中，則返回默認值

195 dic.setdefault(key, value)和get()方法類似词爬，都是得到相應鍵對應的值秃嗜，所不同的是，對于dic.setdefault(key, value)顿膨，如果key不在字典中锅锨，則添加進去，默認值為value虽惭，如果沒有默認值橡类，則設置為None

194 string中數(shù)字的處理一定要注意，要用int轉換成數(shù)字

193 string不能被賦值芽唇，只能轉換成list才能賦值

192 string.startswith(j)代表這個string是以j開頭的

191 s.split()返回的是一個list，里面的element是一個string

190 得到某個元素在list中的index取劫，可以是list.index(value)

190 list.pop(index)默認是-1匆笤，也可以指定index

189 list.insert(index, object)在list的指定位置插入一個元素

188 stack.pop()和stack.top()的區(qū)別是，stack.pop()會刪除頂端這個元素谱邪，stack.top()只是讀頂端這個元素

187 類是抽象的模板炮捧，會把必須綁定的屬性放在init函數(shù)里邊

186 寫類的function的時候，function的第一個參數(shù)都是self惦银。self是指類實例本身

185 _init_是初始化一個類咆课，是在類實例創(chuàng)建之后調用末誓，對當前實例的一些初始化

184 要注意看note

183 string.split('@') split的字符是在括號里面的

182 python和python3一個最重要的區(qū)別是：在python里面，1/2是0书蚪，在python3里面喇澡，1/2是0.5；在python3里面殊校。//取代了/操作

181 if s[i] in "+-*/" 是沒有is的

180 list.sort()平均時間復雜度是O(nlog(n))晴玖，最快時間復雜度是O(n)，用的是Timsort

179 多在紙上畫

178 three-way-partition 方法把數(shù)組分為< = >三部分为流，只需要一次掃描

177 quick sort中經(jīng)常用到Lomuto partition algorithm呕屎；quick sort中用partition將數(shù)組分成兩組，對每組再遞歸調用quick sort方法敬察；有一排小球秀睛，有紅黃綠三種顏色，需要將三種顏色的球排好莲祸，相同顏色的球球相鄰排著蹂安，這是經(jīng)典的Dutch national flag problem

176 merge sort每次都是比較最開頭的元素，然后調用遞歸

175 *是該變量可以接收多個參數(shù)虫给，并將參數(shù)轉化成元組藤抡；**是該變量可以接收多個參數(shù)，但是將參數(shù)轉化成字典[key:value, key:value]

174 quick sort在最壞情況下時間復雜度是O(n^2)

173 為什么merge sort到鏈表的時候空間復雜度從O(n)變到O(1)了抹估，這是因為對于鏈表來說缠黍，只需要改變指針就可以了，不需要額外的空間

172 merge sort對于鏈表來說是in-place的sort药蜻，不需要額外的空間瓷式，而且merge sort穩(wěn)定，所以sort list的時候用merge sort

171 L.next = head 可以理解成L節(jié)點的next指針指向head節(jié)點

170 dummy =? ListNode(None) 是建立一個listNode语泽，其中None是傳入到init的參數(shù)贸典，也就是dummy.val

169 dummy head就是在head前面再加一個節(jié)點，這樣就可以把head和后面的節(jié)點一起處理了踱卵，不用單獨再考慮head節(jié)點廊驼，返回時返回dummy->head就行了

168 快速排序是選擇一個鍵值，一般選第一個惋砂，將所有比它小的放在左邊妒挎，所有比它大的放在右邊，然后再遞歸調用

167 將鏈表一分為二的時候西饵，比如找到了中間節(jié)點酝掩，需要將中間節(jié)點指向NULL，這樣才代表真正將鏈表一分為二了

166 merge sort (歸并排序)和quick sort一樣眷柔，時間復雜度都是O(nlogn)期虾，都是將array分成兩部分原朝，對每一部分再遞歸調用，但是merge sort需要額外的O(n)存儲空間镶苞，從這一點上沒有quick sort有優(yōu)勢喳坠，但是相對于quick sort，merge sort更加穩(wěn)定宾尚。merge sort是將數(shù)組分成兩部分丙笋，對每一部分進行排序，最后進行合并煌贴。merge sort更適合于linked list sort御板，quick sort更適合于數(shù)組排序

165 bucket sort algorithm: 是最快的也最耗空間的一種排序，比quick sort還快牛郑；bucket sort algorithm用于數(shù)字是在固定區(qū)間怠肋，比如學生的分數(shù)是在[0,100]間：先將original array中的元素分別放在buckets中，再對每個bucket進行排序淹朋，最后再gather所有的元素

164 dic[key]是放在中括號中的笙各，不是小括號

163 在字典中，key必須不一樣

162 函數(shù)沒有返回值的時候础芍，默認返回的是None杈抢；return后沒有值也是返回None

161 dic.get(key, specified value) 好處是當key不存在時，就會返回specified value仑性， 如果沒有這個默認值的話惶楼，就會返回None

160 命名一個dictionary就叫dic好了，簡潔明了诊杆，也不會和關鍵字dict重合

159 想要得到dictionary中某個鍵對應的值歼捐，可以有兩種方法，第一種是dictt[鍵]晨汹，但這種方法不優(yōu)雅豹储，容易觸發(fā)keyError的問題；第二種方法是用成員函數(shù)get淘这，dictt.get(鍵)剥扣，這種方法不會觸發(fā)keyError，如果輸入key不存在，則返回None，同時也可以接受兩個key岳颇，第一個key不存在颅崩，就返回第二個key對應的值

158 dictionary中鍵與值之間用冒號隔開，每一對用逗號隔開吃引，整體放在花括號中筹陵。所以初始化一個dictionary的時候刽锤，可以這樣：hashmap{0:1}

157 設置變量的時候要注意，要避免關鍵字朦佩，比如sum就是關鍵字并思，不能用來當變量

156 若想要得到一個array中出現(xiàn)頻率最多的次數(shù)：可以使用下面兩句code，task = collections.Counter(tasks).values()? ? ?M=max(task)

155 需要無限循環(huán)的時候语稠，就用while True

154 string.replace(old, new)宋彼，會建立一個新的copy

153 filter(function, iterable)，過濾掉不符合條件的元素仙畦，后面輸入是一個list输涕，其中的每一個element會送到function中進行驗證，返回的是過濾后的list慨畸；此處的function是判斷函數(shù)莱坎，整個filter函數(shù)返回判斷函數(shù)得到為True的iterable

152 枚舉enumerate(('Thousand', 'Million', 'Billion'), 1)，第一個參數(shù)要用括號括起來

151 enumerate(iterable, start) start默認為0寸士，即從0開始count檐什，如果設置成1，則從1開始

150 string.split()將一個string split弱卡，將返回一個list

149 string也有自帶的count成員函數(shù)乃正，s.count('A'); 還可以判斷某些字符串是不是在S中，比如‘LLL’是否在s中婶博，則if ‘LLL’ not in s

148?if A==B and len(set(A))<len(A): return True

147 string是不能賦值的瓮具，只能轉換成list后再賦值

146 定義雙指針的時候，可以使用while循環(huán)

145 map函數(shù)就是返回一個list凡蜻，使用的時候不需要額外加[]

144 python中有dict函數(shù)搭综，輸入兩組數(shù)，就可以建立一個dictionary

143?[traverse(row+ x,col+ y)for(x, y)in((0,1), (1,0), (0, -1), (-1,0))] 雖然里面是個函數(shù)划栓，但因為有很多種情況兑巾，所以也需要用[]裝起來

142?什么時候定義局部函數(shù)？如果局部函數(shù)需要用到上一級函數(shù)的參數(shù)忠荞，可以定義成局部函數(shù)蒋歌；如果有很多其他函數(shù)調用這個函數(shù)，可以寫成全局函數(shù)

141 stack.append(root)和stack.pop()操作對象都是node委煤，不是node.val

140 iterative, binary tree, BFS 用queue堂油，DFS用stack

139 二叉樹遍歷右兩種方法，一種是遞歸碧绞，時間復雜度是O(n)府框，空間復雜度是O(logn) （遞歸棧的原因）；還有種方法是iterative（迭代）讥邻，用棧來實現(xiàn)迫靖，時間復雜度也是O(n)院峡，空間復雜度是O(logn) 。

138 inorder traversal: 中序遍歷系宜。先中序遍歷左子樹照激，根節(jié)點，再中序遍歷右子樹盹牧；preorder traversal: 前序遍歷俩垃。先遍歷根節(jié)點，再前序遍歷左子樹汰寓，再前序遍歷右子樹口柳，每次遍歷子樹的時候，依舊采取前序遍歷踩寇。postorder traversal：后序遍歷啄清，先后序遍歷左子樹，再后序遍歷右子樹俺孙，再訪問根節(jié)點辣卒。

137 馬拉車算法：首先在每一個字符的前后加#，整個字符串的首尾也加#睛榄，這樣不管原始字符串的長度是奇數(shù)還是偶數(shù)荣茫，加上#后長度都變成奇數(shù)了，因為是2*n+1场靴；需要用一個數(shù)組來存儲以T[i]為中心的回文長度啡莉，返回數(shù)組中最大的那個數(shù)就行了

136 map(None, )可以用作transpose matrix，在空缺的地方補None旨剥，https://leetcode.com/problems/valid-word-square/discuss/91126/1-liner-Python

135 *代表拆開list中的元素

134 python中的星號*（*list）代表的意思是把list中的元素都當做位置參數(shù)傳進去咧欣；**是接受字典key和value

133 map(f, list), 使得list中每個元素都經(jīng)過函數(shù)f，然后返回一個新的list

132 字符也可以直接比大泄熘摹魄咕？比如‘c’>'a'

131 如果是一個sorted的array，而且需要在此array中尋找某個target蚌父，為了減少時間復雜度哮兰，可以使用binary search

130 字符串是不可變對象（tuple也是），不能通過下標的方式進行賦值苟弛，比如S[8]='g'是不允許的

129 str.sort()不能對string片段進行排序喝滞，需使用sorted函數(shù)產(chǎn)生一個copy再賦值回去

128 nums[::-1]不是in-place的，是有一個copy的

127? list[list]不能用set函數(shù)來除去duplicate膏秫，如果想要除掉duplicate右遭，可以先把list[list]中的list先轉化成tuple，然后再使用set

126 初始化一個list，list中element是字符串的狸演，初始化為['']

125 str.lower() str.upper()

124 判斷一個string是否是字母言蛇，可以用str.isalpha()，不分大小寫的

123 可以使用str.isnumeric()函數(shù)來監(jiān)測str是不是數(shù)字

122 遇到比對兩個字符串的時候宵距，可以試著使用雙指針

121 backtracking

120 十進制轉換成其他進制的方法，比如八進制吨拗，用十進制數(shù)除以8得到商1余數(shù)1满哪，再用商1除以8得到商2余數(shù)2.。劝篷。哨鸭。。一直到商為0余數(shù)n娇妓，則最后八進制為（余數(shù)n像鸡，余數(shù)n-1,。哈恰。只估。，余數(shù)2着绷，余數(shù)1）

119 dummy node的作用是保護head不會在刪除操作中丟失蛔钙，一般用在single list沒有前向指針的問題；一般遇到head節(jié)點會變的時候荠医，就會引入dummy node

118 linked list中的node是有value和指針的

117 linked list序號是從1開始的吁脱，linked list中的元素為空時，可以這樣判斷：if fast==None彬向，因為python中沒有null兼贡，只有None

116 可以通過遍歷一次鏈表得到鏈表的長度

115 one pass表示在linked list中，只能traverse一次

114 遇到兩個新知識點：backtracking和memorization

113 bool函數(shù)將參數(shù)轉換成bool型娃胆，bool()參數(shù)為空的情況下遍希，返回False；bool(0)返回False

112 preorder traversal 先序遍歷

111 list.reverse()和reversed(list)區(qū)別缕棵，list.reverse()會改變原有l(wèi)ist孵班，沒有返回值；reversed(list)不會改變原有l(wèi)ist招驴，有返回值篙程，而且返回的不是list，如果需要返回list别厘，需要寫成list(reversed(list))

110 有時候需要一個flag虱饿，就取名叫flag就好了，簡單明了

109 if not root: return []，寫成一行氮发，還有各種各樣變量的定義渴肉，也寫成一行，看上去會簡潔很多

108 matrix.reverse()是把按列reverse的爽冕，也就是說仇祭，把第一行換到第n-1行

107 Two's component 補碼，補碼是把正數(shù)所有位取反颈畸，然后加1

106?if byte >=128 and byte <=191:寫成兩下乌奇，不要寫成if 128<=byte<=191

105 1也是丑陋數(shù)字

104 if key in hashmap 或者 if key not in hashmap，判斷語句是這樣寫的眯娱，沒有is礁苗；還有判斷的時候是判斷key是否在hashmap中，不是判斷值有沒有在hashmap中徙缴，key沒在hashmap中的話就需要建立一個key到value的connection试伙，如果存在相應key的話，只需要把值加進去就行了于样；判斷值在不在hashmap中是沒有意義的疏叨，肯定每次都會不同，但是一個key可以對應很多值

103 sorted('cab') 會得到['a', 'b', 'c']

102 collections.Counter()相當于建立了一個hashtable百宇，將hash到同一個value的objects放在了一起

101 str是個關鍵字考廉，在白板上寫程序的時候要注意

100 abs(a-b)不是abs(a, b)

99 s=" ", 字符長度不是0，因為里面有空格符携御；也不是空字符串昌粤，因為里面有空格符

98 txt.split()默認就是空格符，txt是一個字符串啄刹，txt.split()會得到一個字符串list

97?[k for k, v in Counter(nums).most_common(k)], 通過k和v檢索的方式得到

96 quicksort(快速排序)的時間復雜度是O(nlogn)

95?list.sort是in-place的涮坐，不能寫成a =?list.sort(reverse=True), 直接寫成list.sort(reverse=True）就行了

94 list.sort()比sorted()要快些，因為list.sort()是in-place的誓军，不需要create copy; list.sort(reverse=True)可以得到reversed的list

93 計算質因子中5的個數(shù)袱讹，用floor(n/5)，但是像25昵时，125這種捷雕，本身是有2個5的，所以總的5的個數(shù)=floor(n/5)+floor(n/25)+floor(n/125)

92 0壹甥！也即0的階乘等于1

91 python沒有sqrt函數(shù)救巷，求平方根可以用a**0.5

90 a/b就已經(jīng)是整數(shù)部分了，不需要再在前面加個int

89?for i in xrange(length, -1, -1): 一定要寫后面那個-1句柠，代表降序浦译，不然返回null

88 L1=L和L1=L[:]的區(qū)別棒假，第一是把L1指向L的地址，第二個是把L中的值復制到L1中精盅，改變L1不會改變原來L的值帽哑；第一個改變L1的值會改變原來L的值，因為地址是指向L的

87 當numbers[i]看上去很復雜然后又要用到很多次的時候叹俏，可以將它賦值給一個字母妻枕，比如a =?numbers[i]，看著就不會那么累

86 STL: standard template library. STL中用的是quick sort（快速排序）

85?partition algorithm/?quick sort

84 動態(tài)規(guī)劃有時候只是和前兩個值相關她肯，所以為了減少空間復雜度佳头，可以只保留前面兩個值就行了

83 list.index(element)可以返回element在list中的index

82 要看清題目，比如說了是binary search tree晴氨，那就得利用binary search tree的特性

81 [::-1]倒敘輸出，[:-1]除掉最后一個元素的數(shù)

80 zip函數(shù)可以將兩個數(shù)組打包成元祖

79 注意位移符號優(yōu)先級很低碉输，沒有加減號高籽前，所以在一起使用的時候，位移處要打括號：比如(1<<leftDepth)+self.countNodes(root.right)

78 class里面調用成員函數(shù)時敷钾，需要加self.

77 不管是滿二叉樹還是完全二叉樹枝哄，一直往左遍歷，就能得到二叉樹的高度

76 若滿二叉樹的高度是n（包括根節(jié)點）阻荒，則所以節(jié)點的個數(shù)是2**n-1

75 完全二叉樹一個最重要的性質是：如果左子樹最左邊的深度等于右子樹最右邊的深度挠锥，則此完全二叉樹是滿二叉樹

74 能用迭代的時候用迭代（iterative），比遞歸（recursive）省時間些

73 位運算很省時間侨赡，比如<<比math.pow省時間很多

72 二叉樹的深度是指節(jié)點數(shù)蓖租，直徑是指connections的個數(shù)

71 full binary tree/ complete binary tree，完全二叉樹羊壹，假設深度為h蓖宦，則1~h-1層都打到了最大節(jié)點數(shù)，第h層的所有節(jié)點都聚集在最左邊油猫。滿二叉樹一定是完全二叉樹稠茂，完全二叉樹不一定是滿二叉樹；最后的h層最多有2**h個節(jié)點

70 binary search tree是可以沒有左子樹或者右子樹的

69 寫程序的時候情妖，變量中最好能看出含義

68 判斷是否是回文睬关，在python里面可判斷a==a[::-1]

67 堆(heap)和棧(stack)的區(qū)別，堆是金字塔式泥沙堆毡证，棧是直立性的一個桶电爹；heap是priority queue即優(yōu)先隊列；堆是完全二叉樹情竹，每一個父節(jié)點的值小于等于其子節(jié)點的值藐不；heap(k)<=heap(2k+1), heap(k)<=heap(2k+2)匀哄，最小值是root，即heap(0)雏蛮；創(chuàng)建一個heap涎嚼，用[]，也可以將一個populated list轉換成heap挑秉，用函數(shù)heapify()法梯，線性時間，in-place

66 二維條件表達式：[a,b][a>b], 如果第二個中括號為True犀概，則返回b立哑，若為Fasle，則返回a

63 bin(a)得到的就是一個string

62 modify數(shù)組in-place的時候姻灶，不要用return铛绰，直接就是在之前數(shù)組上改的

61?Manacher是查找一個字符串中最長回文串的線性算法

60 range里面是用逗號連接的，list里面是分號

59 python 函數(shù)里面寫函數(shù)的話产喉，不用self參數(shù)

58 一個數(shù)若是合數(shù)的話捂掰，必然能找到兩個數(shù)相乘得到這個數(shù)，必然是一個小于根號n曾沈，一個大于根號n这嚣，或者兩個都是根號n。所以在尋找質因數(shù)的時候塞俱，只需要循環(huán)到根號n就可以了姐帚，因為如果在小于等于根號n的循環(huán)中都找不到質因數(shù)的話，在大于根號n里更找不到了

57 BFS和DFS區(qū)別障涯，BFS是一石激起千層浪罐旗，DFS是不撞南墻不回頭；BFS和隊列有關像樊，DFS和遞歸有關

56 a[:-1]是去掉最后一個元素尤莺；a[-1]取出最后一個元素

55 對稱數(shù)：0，1生棍，6颤霎，8，9

54 DFS深度優(yōu)先遍歷

53?Fibonacci sequence?斐波那契數(shù)列 F(1)=F(2)=1 F(n)=F(n-1)+F(n-2) (n>=3)

52?lexicographical 詞典編纂的

51 string字符串

50 動態(tài)規(guī)劃核心步驟是寫出狀態(tài)轉移方程涂滴，需要維護局部最小友酱，局部最大，全局最大三個變量

49 要特別注意corner case

48 list就是array

47 map就是dictionary

46 只有l(wèi)ist有append柔纵，str沒有

45 兩個嵌套for循環(huán)缔杉，時間復雜度是O(n**2)，如果直接寫兩個并排的for循環(huán)搁料，則時間復雜度為O(n)

44 對list進行排序的兩種方法或详，一是list的成員函數(shù)sort系羞，在本地進行排序，不返回副本霸琴；二是build-in sorted函數(shù)椒振，返回函數(shù)，原始list不變梧乘，reverse=True為降序澎迎，reverse=False為升序

45?Manacher‘s Algorithm的時間復雜度是線性的

44 range從大到小，遍歷的時候不包括最小的那個數(shù)

43 拿到一道題选调，從最簡單的例子想起夹供，先把思路先想清楚

42 要對比誰小的時候，設置變量應該設置一個很大的值

41 二分查找法仁堪，binary search哮洽，時間復雜度O(logn)

40 range的index是從0開始的，假如有整數(shù)n弦聂，那么index=0的時候袁铐，n=1，index=1的時候横浑，n=2

39 range和xrange的區(qū)別：當range()里面的參數(shù)特別大的時候，容易出現(xiàn)memory的錯誤屉更，而xrange是一個生成器徙融，就不會出現(xiàn)這種錯誤，所以在參數(shù)特別大的時候瑰谜，用xrange函數(shù)欺冀。range是生成一個序列，xrange是生成一個生成器萨脑，所以當參數(shù)很大的時候隐轩，需要開辟一塊很大的內存空間，性能不如xrange好

1 python中tuple和list區(qū)別渤早，list[], tuple()职车，tuple一旦定義就固定了，不能刪除不能插入

2?collections.Counter()中Counter是大寫鹊杖，是Counter不是Count

3 split()默認字符是空格

4?' '.join([A, B])還可以簡化成A+“ ”+B

5 binary tree的diameter長度是指edges不是nodes數(shù)

6 Python3的除法要用//

7 搶錢題：動態(tài)規(guī)劃

8 二分搜索法：最好情況下時間復雜度是O(1)悴灵，最壞情況下（平均情況）時間復雜度是O(log n)

9 two-sum，如果用兩層循環(huán)骂蓖，時間復雜度必定是O(n^2)积瞒，如果用hashtable，就只需要遍歷一遍就行

10 two-sum hashtable, 如果target-num[i]在hash table里面的話登下，就說明前面已經(jīng)出現(xiàn)num[i]了茫孔，而num[i]的index存在了hashtable里的叮喳，所以這時候只需要return當前的index就可以

11 break跳出整個循環(huán)，continue跳出當前循環(huán)缰贝，開始下一個循環(huán)

12 對于while語句馍悟，用得還是不溜

13 if和else的時候，把簡單的留在最后面返回

14 寫每一句code的時候都要細心

15?maxProfit, minPrice= 0, float('inf')? 學會用float('inf')

16 str 不能寫成for i in str這種形式揩瞪，沒有循環(huán)

17?enumerate 枚舉就是一一列舉的意思赋朦，如果apply了enumerate函數(shù)，就會得到序列號和值的pair

18 dummy head for link list: ListNode(0)

19 要返回鏈表的話李破，返回鏈表的頭指針就可以

20 若返回的是matrix宠哄，則定義這個matrix的時候定義成[]就行，調用append函數(shù)的時候嗤攻，也是一個row一個row的往上append

21 substring和subsequence不一樣毛嫉，substring必須是原string的一個part，有前后順序妇菱，subsequence沒有順序

22 要返回什么承粤，你就得在最開始定義

23 定義一個map為a = {}，則取其中的元素的時候闯团，要用中括號辛臊，比如a[]

24 二分法查找：binary search

25 prime number質數(shù)也叫素數(shù)，大于1的natural number中房交，只能被1和本身整除的數(shù)彻舰；合數(shù)是composite number；1既不是prime number也不是composite number

26 python中power用**

27 求某個范圍內自然數(shù)中質數(shù)的個數(shù)候味，有埃氏篩法

28 unicode: unique binary code for every char in every language, the goal is to address the handle requirement for multi-language, multi-platform.

29 ASCii碼是對英文字母刃唤，數(shù)字，特殊字符做的編碼白群，為二進制編碼形式

30 ord()返回對應字符的ascii碼值尚胞，十進制形式。配對的是chr()函數(shù)

31 list.pop([index=-1])返回從列表中刪除的對象帜慢，默認是刪除最后一個元素笼裳，默認index=-1

32 list的初始化，[1]*n這樣就有n個1了崖堤，list加是把兩個list連起來

33 用reversed(s) s在這是string侍咱，可以返回reversed的string

34 n位數(shù)和n位數(shù)相乘的積最多也是2n位數(shù)

35 做coding題的時候，先把思路全部理清了密幔，給面試官說清楚了楔脯，再開始寫code

36 m位的數(shù)和n位數(shù)相乘的位數(shù)最大是m+n位，最小是m+n-1位

37 乘法中的zero-padding是指用0補充的意思

38 若一個list胯甩，從index=3開始取值昧廷，則為list[3:]堪嫂，就是中括號，沒有小括號

most_common