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

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即可。

curr = curr.next执行后要确保curr不是None, 而是一个ListNode, 这就需要预先给curr一个ListNode, 也就是开头的curr ＝ ListNode(0), 调了好久才发现, 晕...

动态规划，依次求出target＝1, 2, 3 ... N时的solution set, 后面的结果依赖于前面的结果。

先遍历，记录下每个节点在第几层，然后按层输出。

递归方法，str(int(s)) == s是为了去掉前导0，即Input＝"010010"时, Output不能是"0.1.0.010"之类的。

In-place的话，先以matrix[0][n-1]...matrix[n-1][0]对角线为轴交换元素，再以水平中线(即第(n+1)/2行)交换元素。

看了这个, 挺简洁的, 不断消灭每一层的左子树。

树的题一开始要讨论root是否为空

题目给出1到N的正整数，但是不全，里面也可能混着0和负整数，找出第一个缺失的正整数。要求时间O(N)空间固定，可使用原数组，通过交换元素使得A[i] = i + 1，第二次遍历时不满足A[i] = i + 1的就是要找的数。

二分法，分别讨论左边单调递增还是右边单调递增。

自己写果然一上来就超时啊, 看了水中的鱼的解体报告, 可以用二分法, 也可以用牛顿迭代法, x = (x + a / x) / 2, 膜拜大神啊

看了这个讲解, O(N)解法, 挺明白的。要一个栈来存放非递减的height序列, 即碰到大于等于栈顶的就入栈, 碰到小于栈顶的就pop。对于每个pop出的元素h[stack[top]]，都要计算以它为最低高度的矩形的面积, 高度就是h[stack[top]], 宽度就是i － stack[-1] - 1, 注意栈中的元素都是非递减的。在h末尾多加一个0的目的是保证栈中的元素都可以被pop出。感谢朱老师提供了一个升级版(Largest rectangle problem)。

摘自维基百科

内存按chunk分配，每个程序保留的chunk的大小和时间都不同。一个程序可以多次请求和释放memory chunk。程序一开始时，空闲内存有很多并且连续，随后大的连续的内存区域碎片化，变成更小的连续区域，最终程序无法获取大的连续的memory chunk。

1) Internal fragmentation ＝ 分给程序的内存比它实际需要的多，多分的内存被浪费。

看了Discuss才会的, 题目说还可以divide and conquer, 咋整捏? S[i]存的是以A[i]为结尾的Subarray的最大和。