kitt blog (欢迎留言，最近刷的题目放到github上了)

动态规划, 节点数为0算一种情况, 即null。左、右子树节点共n-1个。左子树节点数从0走到n-1, 当左子树节点数为k时, 所有可能情况有dp[k] * dp[n-1-k]种。

用一个变量记录最大可到达的位置, 每次在这个位置之前找。

key = sorted word, value = [word1, word2, word3, ...]

看了这个解法, 犀利！首先转成求A和B数组中第k小的数的问题, 然后用k/2在A和B中分别找。比如k = 6, 分别看A和B中的第3个数, 已知 A1 < A2 < A3 < A4 < A5... 和 B1 < B2 < B3 < B4 < B5..., 如果A3 <＝ B3, 那么第6小的数肯定不会是A1, A2, A3, 因为最多有两个数小于A1, 三个数小于A2, 四个数小于A3。B3至少大于5个数, 所以第6小的数有可能是B1 (A1 < A2 < A3 < A4 < A5 < B1), 有可能是B2 (A1 < A2 < A3 < B1 < A4 < B2), 有可能是B3 (A1 < A2 < A3 < B1 < B2 < B3)。那就可以排除掉A1, A2, A3, 转成求A4, A5, ... B1, B2, B3, ...这些数中第3小的数的问题, k就被减半了。每次都假设A的元素个数少, pa = min(k/2, lenA)的结果可能导致k == 1或A空, 这两种情况都是终止条件。 

使用两个指针

经xyz点播, 从后往前放, 方便快捷。

用最小堆, 每个list有一个指针, k个指针放入堆中, 每次pop出最小的, 然后指向相应list的下一个node, 再push入堆。

最小堆是一个数组, 所有元素满足heap[k] <= heap[2*k+1]和heap[k] <= heap[2*k+2], heap[0]即堆顶最小。

heapq.heapify(a) 把list a中元素调换顺序使其成为最小堆, a还是list

heapq.heappush(a, (10, sth_else))  把(10, sth_else)插入堆a中, a仍为最小堆, 也可以只插入数10

heapq.heappop(a) 弹出堆顶元素, a中的最小值

heapq.heappushpop(a, (10, sth_else)) 先push再pop, 效率比依次调用heappush()和heappop()高 

异或

看了此文, 如果是重复数字, 只扩展上一次的结果, 如果是不重复数字, 则扩展全部结果。

二叉树的非递归后序遍历, 还是此文, ^_^

二叉树的非递归中序遍历, 请看此文, 总结得非常好, 前序非递归还可以再简单一些, 一开始root在栈中, 然后while循环只要栈不空, 弹栈print, 右子节点入栈, 左子节点入栈即可。

非递归先序遍历二叉树, 弹栈print, 右子节点入栈, 再左子节点入栈。

写了DP的做法居然Memory Limit Exceeded了, 看了Yu Zhu的这个解法, O(N), 太犀利了! 遇到'*'时, 用star变量记录'*'在p中出现的位置, 用ss变量记录此时s字符串指针sPointer的位置, 但不移动sPointer, 因为'*'可以匹配0个字符, ss表示这个'*'所能匹配到的位置。遇到不匹配的情况时, 即走到if star!= -1时, pPointer被拉回到star的下一个位置, sPointer被拉回到ss的下一个位置, 继续匹配。把s字符串走完, p中还可以剩下一堆'*', 如果p中还有其他字符就返回False了。

动态规划, dp[i][j] = m的含义是s1的前i个字母和s2的前j个字母可以成功组成s3的前m个字母, 当dp[len_s1][len_s2]==len_s3时返回True。

计算每两点之间的斜率，找最大值，要注意同一个坐标多次出现的情况。