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个节点的完全二叉树,其叶子节点的个数n0为: n/2 向上取整，或者(n+1)/2 向下取整
key = ''.join(sorted(string)) sorted函数返回时一个list，不是string，要特别注意
iterator next()作用在dictionary上返回的是key
float('-inf') -不能写在‘’外面
& 用于两个set的话，可以得到intersection
collections.defaultdict(lambda: 1) 因为如果写成int，默认值将是0，这样写是为了得到一个匿名函数
stack经常只用来存储index
迭代器的优势：在构建迭代器的时候，不是将所有的元素一次性加载，而是等调用next方法时返回元素，所以不用考虑内存的问题
迭代器的使用场景：数列的数据规模巨大；数列有规律，但是不能使用列表推导式描述
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，因为负数的表示是正数的反码加1，所以-1是111111...1，左移31就是10000000，代表计算机能表示的最小数
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.
计算机里面都是存的补码，是一个圈，最大数是127(01111111)，最小数是-128(10000000), 所以127+1后会出现溢出，然后就等于-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一起用
一是只要遇到字符串的子序列或配准问题首先考虑动态规划DP，二是只要遇到需要求出所有可能情况首先考虑用递归
ord函数返回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函数，返回的是一个数组
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函数弹出最小元素将另一个元素加入堆：
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)时间
遇到一个数组，如果是想求其最大，最小，最长，最短值，而并不需要知道具体解的题，可以考虑使用动态规划
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()函数的，得到一个迭代器，迭代器有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的数最多只能有两个；
建立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
拓扑排序：将有向无环图的所有顶点排成一个线性序列，使得对图中的任意两个顶点u，v，如果存在边u->v，那么在序列中u一定在v的前面，这个序列又叫拓扑序列。
有向无环图：如果一个有向图的任何顶点都无法通过一些有向边回到自己，那么这个有向图叫有向无环图(DAG: directed acyclic graph)
使用sqrt的时候，要加一个math.sqrt()
BFS 二叉树的时候，注意如果在while循环里面使用了pop，则queue里面就没有这个node啦，后面如果还想用就会出错；下图中后面想用的时候就是空了
这样判断是不是square数不行，要么就加一个int(num**0.5)==num
DFS有时候从大数开始可以更快的得到结果
长方形是rectangle，正方形是square
求距离场BFS是不二之选
想要得到最小步数等问题，可以使用heap
要返回True和False的话，初始化dp数组的时候，就初始化成True或者False，不能写成0或者1，在python里是不一样的
dic.get(key)可以防止返回key错误
python中get()，如果键不存在，则会返回None，所以在计数的时候，不要当做返回0来处理
DFS应用在matrix的时候，一定要注意visited情况，如果visit过的再visit的话，很容易出现超时的情况，可以用设置visited为一个set，将visited过的加到set中去
from在python中是一个关键字，定义变量时不要用它
pop还有删除的功能，所以在需要取出和删除操作时，就直接用pop
在写上面的code时，我经常会犯错误，就是把dfs(newStart)和if对其，这是不对的，因为newStart是依赖上面一行得到的结果的
string.startswith(word) 应该是string的一个常用函数，要学会利用起来
list不能当做hashtable的key
如果一个数是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的个数
更新rank的时候，如果两个rank不一样的话，把小的merge到大的，这样都不用更新rank，但如果两个rank一样的话，需要更新rank值
union find的思想是每个个体先初始化成不同的群主，然后遍历有关联的两个个体，如果发现find的值不同，则手动将二者加入到一个群主，然后总群主数减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，传参数的时候传的是inference也就是指针。像variable这种就没关系
str object doesn't support item assignment
string 才能join，int不能join
list(N) N是整数，这是错误的，整数不能被list
MSB：most significant bit
greedy算法
divide and conquer：把一个问题分成等价的子问题，分别进行解答，最后再把结果合并
第一步：把每个结点的根节点指向它自己，这样就有n个cluster，rank都初始化成0。find的过程把当前结点和它的父母结点都指向root结点；在find中，当这个结点不是根节点时，
union by rank：rank的话可以看成是平均长度，把low rank的cluster merge到high rank的cluster，这样可以 减少做path compression的次数
path compression：每次寻找某个结点的root时，就把此node的所有父母结点指向root，这样相当于flat了整个cluster，下一次查找的时候就直接是O(1)时间了
union find: 有find和union，find的话就是找某个node的root或者叫cluster id。总的node数是n。union是merge两个cluster。查找两个node是否在同一个cluster中，就是看它们的root是不是同一个，查找时间是O(1)
无向连通图：undirected graph.
alphanumeric 代表数字字母两种；s[l].isalnum()判断是否是字母和数字
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:
动态规划，当前状态需要依赖前一状态的值
subarray必须是连续的
binary search：中间值下标的计算，如果写成(l+h)/2，l+h有可能会溢出，从而导致数组访问出错；改进的方法是l+((h-l)>>1)
sliding window: standard template：记录左指针，右指针，每个循环更新左指针，右指针是当前index；外循环遍历整个数组，内部一个while循环遵循题意要求；一个全局变量更新题意要求
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)函数时，相当于把一个元组args拆开，当成参数传进函数中。
*代表该位置可以接受任意多个非关键字参数，在函数中将其转化成元组
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 动态规划解决0-1背包问题步骤：（1）选择一个给定物品i，需要比较选择i形成的子问题最优解和不选择i的子问题最优解，再对两个子问题进行比较，选择最优的。https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/
192 部分背包问题：总是选择每一磅价值（Vi/Wi）最大的物品添加到背包中。解决过程：对每磅价值进行排序，依次从大到小选择添加进背包中
191 0/1背包问题：在选择是否把一个物品加到背包中，需要对把这个物品加到背包的子问题和不加到背包的子问题进行比较。这种方式形成的问题导致了很多重叠子问题，满足动态规划的特征
190 0/1背包，动态规划；部分背包，贪心法
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 判断是奇数偶数，还可以和1按位与，如果与的结果是0，则为偶数，否则为奇数
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已经是一个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循环的时候，queue = [kid for q in queue for kid in (q.left, q.right) if kid]省memory
172 collections.deque(maxlen=size)可以设置一个最长len，这样如果queue满了，append进来的数也会挤掉前面的数，不用再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()为字典提供默认值，防止出现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:研究动态连通性
158 ".join()和‘ ’.join()中间有无空格时不一样的
157 find返回子字符串开始的位置
156 for BST, inorder traverse is an ascending sequence
155 random.randint(a,b)生成一个指定范围内的整数，即生成的整数n满足：a<=n<=b
154 heapq.heapify(self.heap)是in-place的，不要写成self.heap = heapq.heapify(self.heap)
153 heap[0]是最上面那个数，stack[-1]是最上面那个数
152 如果是import heapq的话，调用任何heap相关函数，前面都要加heapq.
151 max heap就是min heap的invert
150 使用heapq的时候，直接import heapq就可以了
149 self只在类的方法中才有，在独立的函数中是没有必要带的，self在定义类的方法时必须有，在调用的时候会自动传入；self就是指类实例对象本身
148 query疑问，质问
147 dic.pop('key', None)删除字典中的key，如果key不存在，返回None，因为不会产生keyerror
146 decimal小数的
145 str.isalpha()只是字符，像[这种特殊字符，并不能用这个来判断
144 [::-1] the the best and the fastest way to reverse a list.
143 list.pop()默认是pop最后的那个元素，所以我们如果想pop最开始的元素，需要把参数设置成0
142 list.index(element)返回element的index，time complexity是O(n)
141 注意注意注意：push到heap中，是按照push进去的第一个纬度来衡量最小值的！！！比如计算最小步数，一定要把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：用于匹配字母，数字或下划线字符； \W：用于匹配所有与\w不匹配的字符；
131 string.split()返回list
130 string.split()会改变string本身吗？还是会产生一个copy。貌似不改变本身
129 heappushpop() 将值插入到堆中同时弹出堆中的最小值。 heapq.heappushpop(heap, item) #首先判断添加元素值与堆的第一个元素值对比，如果大于则删除最小元素，然后添加新的元素值，否则不更改堆
128 maxheap
127 heapify()以线性时间将一个列表转换成堆
126 删除并返回heap中最小的元素，使用heapify()和heappop()来实现
125 set.remove(item)
124 denomination面值
123 从0变成1，从1变成0，可以用1-matrix[i][j]来实现
122 初始化一个矩阵，dp = [[1]*n for i in range(m)]是先弄一整行，然后再traverse行数
121 写新的内部函数的时候，一定要放在最前面，方便调用
120 写程序时写完一句就检查一下，养成一遍写好所有程序的习惯
119 看到别人的好建议，就马上执行
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 局部函数一般写在前面
112 yield是一个类似return的关键字，只是这个函数返回的是一个生成器
111 generator可以有效节约系统资源，避免不必要的系统占用
110 带有yield的函数在python中称为generator；这个函数和普通函数不一样，看起来像函数调用，但不会执行任何代码，直到对其调用next()才开始执行，在for循环中自动调用next()。每执行到一个yield语句就会中断，并返回一个迭代值，下次执行从yield的下一个语句开始执行
109 两个矩阵相乘，第一个矩阵的列数要和第二个矩阵的行数相等，最后的出来的矩阵行数是第一个矩阵的行数。列数是第二个矩阵的列数
108 forty 四十
107 bin函数返回的就是string
106 int(a, 2)代表以2为base，即把string a按照base为2转换，比如int('11',2)=3, 如果是int('11')=11，默认base是10
105 不管是Counter还是hashmap，都有values这个成员函数，collections.Counter(tasks).values()
104 python的数据类型分为mutable和immutable两种类型，mutable: list和dict，immutable：int,string, float, tuple
102 python中逗号
101 线性时间就是O(n)
100 sorted(L, key = len) 按len来排序
99 for循环本质上是通过不断调用next()函数实现的
98 iterator甚至可以表示一个无限大的数据流，比如全体自然数，但使用list是不可能存储所有自然数的
97 可以把这个数据流看成是一个有序数列，但我们不能提前知道这个有序数列的长度，只能不断通过next()函数实现按需计算下一个数据。所以iterator的计算是惰性的，只有在需要下一个数据的时候，它才会计算
96 可以被next()函数不断调用并返回下一个值的对象称为iterator；可以作用于for循环的对象称为iterable，比如list，tuple，str，dict，set，generator；list，str，dict是iterable，但不是iterator；iter()函数可以把list，str，dict等iterable转成iterator；iterator对象表示的是一个数据流，可以被next()函数不断调用返回下一个值，直到没有数据。
95 escape character转义字符；\n换行，\t横向制表符 ASCII Horizontal Tab (TAB)
94 DFA：deterministic finite automaton，是一个含有5个元素的tuple（S，q0，T, F，），S：状态的集合，q0：初始化状态，T：transition function, F: 结束状态的集合，
是全部的字母表。
93 str.isalpha()全部是字母就返回True，否则返回False
92 index超出范围，总是出这样的错，一定要细心啊; 一定要从最简单的开始考虑
91 在纸上写testcase
90 二分查找法时间复杂度：O(logn)
89 list和string都有count函数
88 创建一个图，首先也得创建一个root
87 union find，并查集，是解决动态连通性的一种很高效的数据结构。
86 queue因为是list，所以添加元素的时候，可以用queue+= i
85 any() 和 all()的区别。any()判断对象是否为空对象，如果都是空，0，false，返回false，如果不都返回空，0，false，返回True；all()，如果里面所有元素不为0，空，false，则返回True，但是all(x)如果x是个空对象，则返回True
84 从现在开始，看到一道题，就模拟是在面试，认真读题，积极思考，用英语说
83 id, type也是关键字
82 在最开始时除了要初始化好需要用的stack什么的，也要注意初始化一个返回array，或者返回value
81 deque是双端队列，可以从两端append数据；如果想实现随机访问，用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循环体中值需要考虑当前节点就行，下面的直接递归调用
76 if not i这样的判断语句代表如果i为False，就可以执行if下面的语句
75 python中is和==的比较：==是对比两个对象的内容是不是一样的，即内存地址可以不一样，只要内容一样就行；is是判断两个对象的内存地址是不是一样，是不是同一个对象
74 dividend：被除数，divisor：除数
73 通常用于求解某种具有最优性质的问题，一般用于多阶段决策问题。
72 贪心算法，greedy algorithm，只是局部最优解，没有从整体最优上加以考虑
71 链表的node，是包含值和指针的，指针就是指向的地址，所以当我们把head node放置在队伍中去的时候，因为有指针，所以就可以找到它后面的node
70 建立dummy head和head一样，建好后一般会设置一个curr指针来帮助建立后面的node
69 heap和stack区别：heap像一堆金字塔型泥沙，stack像一个直立垃圾桶；heap也是priority queue，按照元素的优先级取出元素；heap性质：任意节点小于或大于它的所有后裔，最小元或者最大元在堆的根上；heap总是一颗完全树，即除了最底层，其它层的节点都被元素填满，且最底层尽可能地从左到右填入；heap实现：主要是插入和删除最小元素，元素值本身是优先级键值，小元素享有最高优先级；插入或者删除之后，heap还是要保持为一颗完全树，即完全二叉树和每个节点值都小于或者等于它的子节点
68 Queue类，FIFO；Queue.PriorityQueue, lowest valued entry retrieved first.
67 复制链表的方法：创建一个hashmap，旧节点是key，新节点是value
66 next()返回迭代器的下一个项目
65 items函数，将一个字典以列表的形式返回，因为字典是无序的，所以返回的列表也是无序的，比如a = {‘a’: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列表操作，删除一个或者连续几个元素，比如a=[1,2,3,4], del a[0], 则a=[2,3,4]
61 collections模块中有一个子类OrderedDict，可以对字典对象中的元素进行排序，会根据输入的顺序放置
60 建立字典树Trie需要先建立一个TrieNode, init函数里有self.children； 建立binary tree也需要建立一个TreeNode的class，init函数里是当前节点的self.val=x, self.left=None, self.right=None; Linked list有ListNode， init函数里特有属性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的话就是要找到与该节点相邻的所有节点
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 极值的问题考虑使用动态规划
55 已知三角形两边a和b，以及夹角C，则三角形面积是1/2*absinC
54 operator.mul()
53 reduce函数会对参数序列中的元素进行累积；reduce(function, iterable)，如果fucntion中有两个参数，比如lambda函数，则将集合中的第一第二个元素进行操作，再和之后的元素进行依次操作
52 list+list=list，比如[1, 2, 3]+[4, 5 ,6]=[1, 2, 3, 4, 5, 6]
51 遇到排列组合，可以结合stack做，因为stack返回的就是list，表示成[]，返回到res中就是一个一个[]，最后是[[]]
50 一直让loop循环，知道满足条件再跳出循环，可以用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’的ASCii值是97，‘A’的ASCii码值是65
42 range(1, n+1)我老是喜欢写成range(1:n+1)
41 遇到困惑就要去解决，比如知道刷了的题还是会忘记，那就在第二天，第四天，第八天。。。花很短的时间去复习下
40 memorization存储调用函数的结果，当相同的参数传进来的时候，直接返回值就行了。在递归函数中用得比较多
39 memorization技术：就是把每次函数执行的结果存储在键值对中，在接下来的执行中，现在键值对中查找是否有相应执行过的值，如果有，直接返回该值，没有的话才真正执行函数体的求值部分。在键值中找值比去执行函数快多了。
38 2的3次方，2 to the power of 3
37 遇到Parenthesis的题，就可以用count来做
36 backtracking回溯法，是一种搜索尝试过程，当发现不满足条件时，就退回来寻找新的路径，退回来这个过程就是回溯。是一种系统搜索问题解的方法。使用DFS的方法。适用于求解组合数较大的问题。回溯问题递归函数模板：
1 ）最开始写好跳出条件，满足条件才加到总结果中
2） 已经拿过的数不再拿
3）遍历过当前节点后，为了回溯到上一步，需要去掉已经加入到list中的当前节点
35 open parenthesis 是左括号的意思
34 deque.popleft获取最左边的元素并删除
33 对于stack来说，最上面的元素可以通过stack[-1]来得到
32 设计一个class，class的成员函数间是可以调用的，我经常忘记调用其他的函数
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 在草稿纸上多写几个例子找规律
24 for b in zip(*xmap) 在这句code中，zip中是unpacked的individual字符串，每一个individual字符串是32长度的num转换来的，这样在每一次for循环中，b先取每个字符串的第一位，这样b的长度就是32的tuple，然后调用tuple.count()
23 总是忘记使用string.count()这个函数，比如想统计string中‘a’的个数，可以写成string.count('a')
22 python中*的作用是unpack list to individual arguments，比如zip(*['0100','1110','0010'])等于zip('0100','1110','0010')
21 '{:032b}'.format的作用是将输入参数转换成32位无符号数字符串
22 set()和{}都可以用来创建集合，但要创建一个空集合的话，只能用set()，因为{}是创建字典的。创建过程是{‘a’, 'o', 'e', 'i', 'u'}, set('aoeiu')，set('aoeiu')运行后为set([‘a’, 'o', 'e', 'i', 'u'])。原来set中也是一个list，无序不重复结合
21 set的in operation比string的in operation要快些，所以在做lookup的时候，尽量用set
20 map(f, list)将f函数作用在list的每一个元素上，一个一个mapping，所以叫map函数
19 str.format()，可以接受很多个参数，可以在format函数里面对应赋值，也可以在format()函数里面给变量赋值
18 一定要避免使用两个for loop，一般都会time limited
17 每刷一题，分析时间复杂度和空间复杂度
16 sum是python关键字，可以用sums
15 二叉搜索是，每个节点的值比它左子树的任意节点值大，比它右子树的任意节点值小
14 先要把题意弄明白，然后想明白该怎么做，最后再写code
13 二叉查找树的中序遍历是递增序列
12 set(['John','Jane','Jack','Janice'])中存字符串是这样存的，set([1, 2, 3]) 存number
11 trie的两个应用，词频统计，也可以用hash和堆来做，可是没有trie节省空间，因为字符的公共前缀是用同一个节点来存的
10 trie的insert和search time complexity都是O(k)，k是key的长度，trie的缺点是space complexity高；
9 由于trie可以最大限度地减少字符串比较，所以可用于词频统计和大量字符串排序；优点是最坏情况时间复杂度此hashtable好。也有key到value的映射，但这里的key是字符串
8 trie中的key通常是字符串，根节点不包含字符，除根节点以外的所有节点都包含一个字符，从根节点到某一个节点，所有的字符连接起来，就是该节点的字符；每个节点的所有子节点包含的字符串不相同。
7 set.add() list.append()
6 普通dict和collections.defaultdict()的区别，普通dict添加和查找元素都可以用dict[key]=value来实现，但是在查找的时候，如果key不在字典中，则会出现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的区别：hashMap实现了map接口，hashSet实现了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模块的几个函数，第一个是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就返回插入数在最左边的位置就好了，因为插入进去也是会插入到这个位置；但是bisect_right是会返回当前位置加1的，因为插入的话会插到当前位置加1上；bisect.insort_left的话是真正把这个元素插进去了，返回插入后的序列，left的话就插在左边，right的话就插在右边
201 bisect.insort()是插入后再排序，时间复杂度是O(n)
200 在python里面，/做除法的时候，如果想得到小数部分，floating point的结果，可以把除数写成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中数字的处理一定要注意，要用int转换成数字
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()的区别是，stack.pop()会删除顶端这个元素，stack.top()只是读顶端这个元素
187 类是抽象的模板，会把必须绑定的属性放在init函数里边
186 写类的function的时候，function的第一个参数都是self。self是指类实例本身
185 _init_是初始化一个类，是在类实例创建之后调用，对当前实例的一些初始化
184 要注意看note
183 string.split('@') split的字符是在括号里面的
182 python和python3一个最重要的区别是：在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 方法把数组分为< = >三部分，只需要一次扫描
177 quick sort中经常用到Lomuto partition algorithm；quick sort中用partition将数组分成两组，对每组再递归调用quick sort方法；有一排小球，有红黄绿三种颜色，需要将三种颜色的球排好，相同颜色的球球相邻排着，这是经典的Dutch national flag problem
176 merge sort每次都是比较最开头的元素，然后调用递归
175 *是该变量可以接收多个参数，并将参数转化成元组；**是该变量可以接收多个参数，但是将参数转化成字典[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稳定，所以sort list的时候用merge sort
171 L.next = head 可以理解成L节点的next指针指向head节点
170 dummy = ListNode(None) 是建立一个listNode，其中None是传入到init的参数，也就是dummy.val
169 dummy head就是在head前面再加一个节点，这样就可以把head和后面的节点一起处理了，不用单独再考虑head节点，返回时返回dummy->head就行了
168 快速排序是选择一个键值，一般选第一个，将所有比它小的放在左边，所有比它大的放在右边，然后再递归调用
167 将链表一分为二的时候，比如找到了中间节点，需要将中间节点指向NULL，这样才代表真正将链表一分为二了
166 merge sort (归并排序)和quick sort一样，时间复杂度都是O(nlogn)，都是将array分成两部分，对每一部分再递归调用，但是merge sort需要额外的O(n)存储空间，从这一点上没有quick sort有优势，但是相对于quick sort，merge sort更加稳定。merge sort是将数组分成两部分，对每一部分进行排序，最后进行合并。merge sort更适合于linked list sort，quick sort更适合于数组排序
165 bucket sort algorithm: 是最快的也最耗空间的一种排序，比quick sort还快；bucket sort algorithm用于数字是在固定区间，比如学生的分数是在[0,100]间：先将original array中的元素分别放在buckets中，再对每个bucket进行排序，最后再gather所有的元素
164 dic[key]是放在中括号中的，不是小括号
163 在字典中，key必须不一样
162 函数没有返回值的时候，默认返回的是None；return后没有值也是返回None
161 dic.get(key, specified value) 好处是当key不存在时，就会返回specified value， 如果没有这个默认值的话，就会返回None
160 命名一个dictionary就叫dic好了，简洁明了，也不会和关键字dict重合
159 想要得到dictionary中某个键对应的值，可以有两种方法，第一种是dictt[键]，但这种方法不优雅，容易触发keyError的问题；第二种方法是用成员函数get，dictt.get(键)，这种方法不会触发keyError，如果输入key不存在，则返回None，同时也可以接受两个key，第一个key不存在，就返回第二个key对应的值
158 dictionary中键与值之间用冒号隔开，每一对用逗号隔开，整体放在花括号中。所以初始化一个dictionary的时候，可以这样：hashmap{0:1}
157 设置变量的时候要注意，要避免关键字，比如sum就是关键字，不能用来当变量
156 若想要得到一个array中出现频率最多的次数：可以使用下面两句code，task = collections.Counter(tasks).values() M=max(task)
155 需要无限循环的时候，就用while True
154 string.replace(old, new)，会建立一个新的copy
153 filter(function, iterable)，过滤掉不符合条件的元素，后面输入是一个list，其中的每一个element会送到function中进行验证，返回的是过滤后的list；此处的function是判断函数，整个filter函数返回判断函数得到为True的iterable
152 枚举enumerate(('Thousand', 'Million', 'Billion'), 1)，第一个参数要用括号括起来
151 enumerate(iterable, start) start默认为0，即从0开始count，如果设置成1，则从1开始
150 string.split()将一个string split，将返回一个list
149 string也有自带的count成员函数，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循环
145 map函数就是返回一个list，使用的时候不需要额外加[]
144 python中有dict函数，输入两组数，就可以建立一个dictionary
143 [traverse(row+ x,col+ y)for(x, y)in((0,1), (1,0), (0, -1), (-1,0))] 虽然里面是个函数，但因为有很多种情况，所以也需要用[]装起来
142 什么时候定义局部函数？如果局部函数需要用到上一级函数的参数，可以定义成局部函数；如果有很多其他函数调用这个函数，可以写成全局函数
141 stack.append(root)和stack.pop()操作对象都是node，不是node.val
140 iterative, binary tree, BFS 用queue，DFS用stack
139 二叉树遍历右两种方法，一种是递归，时间复杂度是O(n)，空间复杂度是O(logn) （递归栈的原因）；还有种方法是iterative（迭代），用栈来实现，时间复杂度也是O(n)，空间复杂度是O(logn) 。
138 inorder traversal: 中序遍历。先中序遍历左子树，根节点，再中序遍历右子树；preorder traversal: 前序遍历。先遍历根节点，再前序遍历左子树，再前序遍历右子树，每次遍历子树的时候，依旧采取前序遍历。postorder traversal：后序遍历，先后序遍历左子树，再后序遍历右子树，再访问根节点。
137 马拉车算法：首先在每一个字符的前后加#，整个字符串的首尾也加#，这样不管原始字符串的长度是奇数还是偶数，加上#后长度都变成奇数了，因为是2*n+1；需要用一个数组来存储以T[i]为中心的回文长度，返回数组中最大的那个数就行了
136 map(None, )可以用作transpose matrix，在空缺的地方补None，https://leetcode.com/problems/valid-word-square/discuss/91126/1-liner-Python
135 *代表拆开list中的元素
134 python中的星号*（*list）代表的意思是把list中的元素都当做位置参数传进去；**是接受字典key和value
133 map(f, list), 使得list中每个元素都经过函数f，然后返回一个新的list
132 字符也可以直接比大小？比如‘c’>'a'
131 如果是一个sorted的array，而且需要在此array中寻找某个target，为了减少时间复杂度，可以使用binary search
130 字符串是不可变对象（tuple也是），不能通过下标的方式进行赋值，比如S[8]='g'是不允许的
129 str.sort()不能对string片段进行排序，需使用sorted函数产生一个copy再赋值回去
128 nums[::-1]不是in-place的，是有一个copy的
127 list[list]不能用set函数来除去duplicate，如果想要除掉duplicate，可以先把list[list]中的list先转化成tuple，然后再使用set
126 初始化一个list，list中element是字符串的，初始化为['']
125 str.lower() str.upper()
124 判断一个string是否是字母，可以用str.isalpha()，不分大小写的
123 可以使用str.isnumeric()函数来监测str是不是数字
122 遇到比对两个字符串的时候，可以试着使用双指针
121 backtracking
120 十进制转换成其他进制的方法，比如八进制，用十进制数除以8得到商1余数1，再用商1除以8得到商2余数2.。。。。一直到商为0余数n，则最后八进制为（余数n，余数n-1,。。。，余数2，余数1）
119 dummy node的作用是保护head不会在删除操作中丢失，一般用在single list没有前向指针的问题；一般遇到head节点会变的时候，就会引入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函数将参数转换成bool型，bool()参数为空的情况下，返回False；bool(0)返回False
112 preorder traversal 先序遍历
111 list.reverse()和reversed(list)区别，list.reverse()会改变原有list，没有返回值；reversed(list)不会改变原有list，有返回值，而且返回的不是list，如果需要返回list，需要写成list(reversed(list))
110 有时候需要一个flag，就取名叫flag就好了，简单明了
109 if not root: return []，写成一行，还有各种各样变量的定义，也写成一行，看上去会简洁很多
108 matrix.reverse()是把按列reverse的，也就是说，把第一行换到第n-1行
107 Two's component 补码，补码是把正数所有位取反，然后加1
106 if byte >=128 and byte <=191:写成两下，不要写成if 128<=byte<=191
105 1也是丑陋数字
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的个数，用floor(n/5)，但是像25，125这种，本身是有2个5的，所以总的5的个数=floor(n/5)+floor(n/25)+floor(n/125)
92 0！也即0的阶乘等于1
91 python没有sqrt函数，求平方根可以用a**0.5
90 a/b就已经是整数部分了，不需要再在前面加个int
89 for i in xrange(length, -1, -1): 一定要写后面那个-1，代表降序，不然返回null
88 L1=L和L1=L[:]的区别，第一是把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 动态规划有时候只是和前两个值相关，所以为了减少空间复杂度，可以只保留前面两个值就行了
83 list.index(element)可以返回element在list中的index
82 要看清题目，比如说了是binary search tree，那就得利用binary search tree的特性
81 [::-1]倒叙输出，[:-1]除掉最后一个元素的数
80 zip函数可以将两个数组打包成元祖
79 注意位移符号优先级很低，没有加减号高，所以在一起使用的时候，位移处要打括号：比如(1<<leftDepth)+self.countNodes(root.right)
78 class里面调用成员函数时，需要加self.
77 不管是满二叉树还是完全二叉树，一直往左遍历，就能得到二叉树的高度
76 若满二叉树的高度是n（包括根节点），则所以节点的个数是2**n-1
75 完全二叉树一个最重要的性质是：如果左子树最左边的深度等于右子树最右边的深度，则此完全二叉树是满二叉树
74 能用迭代的时候用迭代（iterative），比递归（recursive）省时间些
73 位运算很省时间，比如<<比math.pow省时间很多
72 二叉树的深度是指节点数，直径是指connections的个数
71 full binary tree/ complete binary tree，完全二叉树，假设深度为h，则1~h-1层都打到了最大节点数，第h层的所有节点都聚集在最左边。满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树；最后的h层最多有2**h个节点
70 binary search tree是可以没有左子树或者右子树的
69 写程序的时候，变量中最好能看出含义
68 判断是否是回文，在python里面可判断a==a[::-1]
67 堆(heap)和栈(stack)的区别，堆是金字塔式泥沙堆，栈是直立性的一个桶；heap是priority queue即优先队列；堆是完全二叉树，每一个父节点的值小于等于其子节点的值；heap(k)<=heap(2k+1), heap(k)<=heap(2k+2)，最小值是root，即heap(0)；创建一个heap，用[]，也可以将一个populated list转换成heap，用函数heapify()，线性时间，in-place
66 二维条件表达式：[a,b][a>b], 如果第二个中括号为True，则返回b，若为Fasle，则返回a
63 bin(a)得到的就是一个string
62 modify数组in-place的时候，不要用return，直接就是在之前数组上改的
61 Manacher是查找一个字符串中最长回文串的线性算法
60 range里面是用逗号连接的，list里面是分号
59 python 函数里面写函数的话，不用self参数
58 一个数若是合数的话，必然能找到两个数相乘得到这个数，必然是一个小于根号n，一个大于根号n，或者两个都是根号n。所以在寻找质因数的时候，只需要循环到根号n就可以了，因为如果在小于等于根号n的循环中都找不到质因数的话，在大于根号n里更找不到了
57 BFS和DFS区别，BFS是一石激起千层浪，DFS是不撞南墙不回头；BFS和队列有关，DFS和递归有关
56 a[:-1]是去掉最后一个元素；a[-1]取出最后一个元素
55 对称数：0，1，6，8，9
54 DFS深度优先遍历
53 Fibonacci sequence 斐波那契数列 F(1)=F(2)=1 F(n)=F(n-1)+F(n-2) (n>=3)
52 lexicographical 词典编纂的
51 string字符串
50 动态规划核心步骤是写出状态转移方程，需要维护局部最小，局部最大，全局最大三个变量
49 要特别注意corner case
48 list就是array
47 map就是dictionary
46 只有list有append，str没有
45 两个嵌套for循环，时间复杂度是O(n**2)，如果直接写两个并排的for循环，则时间复杂度为O(n)
44 对list进行排序的两种方法，一是list的成员函数sort，在本地进行排序，不返回副本；二是build-in sorted函数，返回函数，原始list不变，reverse=True为降序，reverse=False为升序
45 Manacher‘s Algorithm的时间复杂度是线性的
44 range从大到小，遍历的时候不包括最小的那个数
43 拿到一道题，从最简单的例子想起，先把思路先想清楚
42 要对比谁小的时候，设置变量应该设置一个很大的值
41 二分查找法，binary search，时间复杂度O(logn)
40 range的index是从0开始的，假如有整数n，那么index=0的时候，n=1，index=1的时候，n=2
39 range和xrange的区别：当range()里面的参数特别大的时候，容易出现memory的错误，而xrange是一个生成器，就不会出现这种错误，所以在参数特别大的时候，用xrange函数。range是生成一个序列，xrange是生成一个生成器，所以当参数很大的时候，需要开辟一块很大的内存空间，性能不如xrange好
1 python中tuple和list区别，list[], tuple()，tuple一旦定义就固定了，不能删除不能插入
2 collections.Counter()中Counter是大写，是Counter不是Count
3 split()默认字符是空格
4 ' '.join([A, B])还可以简化成A+“ ”+B
5 binary tree的diameter长度是指edges不是nodes数
6 Python3的除法要用//
7 抢钱题：动态规划
8 二分搜索法：最好情况下时间复杂度是O(1)，最坏情况下（平均情况）时间复杂度是O(log n)
9 two-sum，如果用两层循环，时间复杂度必定是O(n^2)，如果用hashtable，就只需要遍历一遍就行
10 two-sum hashtable, 如果target-num[i]在hash table里面的话，就说明前面已经出现num[i]了，而num[i]的index存在了hashtable里的，所以这时候只需要return当前的index就可以
11 break跳出整个循环，continue跳出当前循环，开始下一个循环
12 对于while语句，用得还是不溜
13 if和else的时候，把简单的留在最后面返回
14 写每一句code的时候都要细心
15 maxProfit, minPrice= 0, float('inf') 学会用float('inf')
16 str 不能写成for i in str这种形式，没有循环
17 enumerate 枚举就是一一列举的意思，如果apply了enumerate函数，就会得到序列号和值的pair
18 dummy head for link list: ListNode(0)
19 要返回链表的话，返回链表的头指针就可以
20 若返回的是matrix，则定义这个matrix的时候定义成[]就行，调用append函数的时候，也是一个row一个row的往上append
21 substring和subsequence不一样，substring必须是原string的一个part，有前后顺序，subsequence没有顺序
22 要返回什么，你就得在最开始定义
23 定义一个map为a = {}，则取其中的元素的时候，要用中括号，比如a[]
24 二分法查找：binary search
25 prime number质数也叫素数，大于1的natural number中，只能被1和本身整除的数；合数是composite number；1既不是prime number也不是composite number
26 python中power用**
27 求某个范围内自然数中质数的个数，有埃氏筛法
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码是对英文字母，数字，特殊字符做的编码，为二进制编码形式
30 ord()返回对应字符的ascii码值，十进制形式。配对的是chr()函数
31 list.pop([index=-1])返回从列表中删除的对象，默认是删除最后一个元素，默认index=-1
32 list的初始化，[1]*n这样就有n个1了，list加是把两个list连起来
33 用reversed(s) s在这是string，可以返回reversed的string
34 n位数和n位数相乘的积最多也是2n位数
35 做coding题的时候，先把思路全部理清了，给面试官说清楚了，再开始写code
36 m位的数和n位数相乘的位数最大是m+n位，最小是m+n-1位
37 乘法中的zero-padding是指用0补充的意思
38 若一个list，从index=3开始取值，则为list[3:]，就是中括号，没有小括号
most_common
