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

经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。

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

neighbors就是指左边一个和右边一个, 只有比neighbor的rating高的孩子得到的糖才能更多, rating为1, 2, 2时糖数为1, 2, 1。正向扫一遍, 后一个比前一个rating高则后一个的糖数要增加, 再反向扫一遍, 同样处理。

每个node的值可正可负, 参考了网上C++解法, 类变量Solution.maxSum用于记录最大路径和, 当level为0时返回它; maxPathSum(root)函数返回的是经过root的路径最大和, 可以只是root, 也可以是左子树某一部分+root或者root+右子树某一部分。这个函数是可以返回0的, 也就是说currRoot, currRoot+左子树, currRoot+右子树的值都小于等于0, 对max path sum没有贡献, 之后就不再考虑了。

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        L, res, lastAppear = -1, 0, [-1] * 128
        for R, char in enumerate(s):
            pos = ord(char)
            if lastAppear[pos] > L:
                L = lastAppear[pos]
            else:
                res = max(res, R - L)
            lastAppear[pos] = R
        return res

看到了用左右边界的做法，犀利啊！我感觉思考这道题的时候不要关注tree，而要关注node。

递归方法，确保在每一步右括号数 <= 左括号数 <= n即可。