7.14 - medium总结15

286. Walls and Gates: 针对每一个0值做dfs或者bfs。
287. Find the Duplicate Number: 这题也是非正常解法，如果一个数组确切包含值1到n，那么小于某一个数的值的个数一定是等于这个值，否则这其中就缺少值。例如[1,2,4,5,6,6,7]，对于4来说小于等于4的值的个数为3 (1,2,4)，那么说明4以下没有重复的数，再去找5到7之间，同样，如果4以下的值多于4的话，那么一定就有重复的，这个算法的复杂度是O(nlog(n))

class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        low = 1
        high = len(nums)-1
        
        while low < high:
            mid = low+(high-low)/2
            count = 0
            for i in nums:
                if i <= mid:
                    count+=1
            if count <= mid:
                low = mid+1
            else:
                high = mid
        return low

288. Unique Word Abbreviation: 拿这个word的开头的char和结尾的char和中间的长度作为key，做一个dict就可以了
289. Game of Life: 其实这题不难，就是用多个bit来表示一个状态 #00 表示现在是死的，下次刷新是死的 #01 表示现在是活的，下次刷新是活的 #10 表示现在是死的，下次刷新是活的 #11 表示现在是活的，下次刷新是死的
294. Flip Game II: 状态不佳，且非常不擅长这种两人下棋的题，好像后面还有好几道，基本上都没做出来
298. Binary Tree Longest Consecutive Sequence: 今天有点崩，脑袋不太转，周五综合症？
299. Bulls and Cows: 这题用hashtable来解决
300. Longest Increasing Subsequence: 一道dp的题，不过有优化的解法
304. Range Sum Query 2D - Immutable: 我的解法是对每一行都做前缀和，然后再对每一行进行运算，虽然也AC了，但是时间上不太好，改进的方法是对行和列同时做前缀和。self.cum[i+1][j+1] = matrix[i][j] + self.cum[i][j+1] + self.cum[i+1][j] - self.cum[i][j]， 也就是当前的值是左边值的矩形+上面值的矩形+当前matrix值减去，重复的矩形部分，画一个图就比较明显了，算是二维的前缀和运算吧。
306. Additive Number: 想法的关键是前面两个数会决定后面所有的数，类似于插隔板，插入第一和第二块隔板，然后在第二块隔板后寻找和, 最初的两块板会决定后面所有的值。