7.24 - medium总结19

361. Bomb Enemy: 这题做出来一个TLE的版本，用的是记录每一个cell的左边和右边的值上面和下面的值。感觉重复了很多信息，其实更新的方案是，对于每一个0点，只有当其左边的那个或者上边的那个撞墙的时候才更新之前的数值，否则就可以直接用左边点或者上边点的那个值

class Solution(object):
    def maxKilledEnemies(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not grid:
            return 0
        m = len(grid)
        n = len(grid[0])
        cols_hit = [0]*n
        res = 0
        for i in range(m):
            for j in range(n):
                if j == 0 or grid[i][j-1] == "W":
                    rows_hit = 0
                    k = j
                    while k < n and grid[i][k] != "W":
                        rows_hit += grid[i][k] == "E"
                        k += 1
                if i == 0 or grid[i-1][j] == "W":
                    cols_hit[j] = 0
                    k = i
                    while k < m and grid[k][j] != "W":
                        cols_hit[j] += grid[k][j] == "E"
                        k += 1
                
                if grid[i][j] == "0":
                    res = max(res, rows_hit+cols_hit[j])
        
        return res

362. Design Hit Counter：我是用两个300的array来解决的，看了下时间比较小的答案，发现用deque来解决更加合理一些。因为只要考虑头和尾就可以了
364. Nested List Weight Sum II：用bfs就可以解决这个问题了，记录一下每一层的integer就可以了。
365. Water and Jug Problem：找gcd，ax+by=z，如果能找到这样的ab，就说明可解。gcd是最大公约数。这就是一道数学题，知道就知道不知道就拉倒。
366. Find Leaves of Binary Tree: 这要就是用divide and conquer的方法，找每一个节点的depth2leaf
368. Largest Divisible Subset: 用backtracking写出一个TLE版本，然后看了一眼tag，发现用DP，然后用DP写出来了。
369. Plus One Linked List：reverse, 加法，再reverse
370. Range Addition: 有点tricky，像更新array或者矩阵的时候，可以先考虑最坏情况，然后再慢慢优化。
372. Super Pow：比较扯淡的数学题ab % k = (a%k)(b%k)%k， a^1234567 % k = (a^1234560 % k) * (a^7 % k) % k = (a^123456 % k)^10 % k * (a^7 % k) % k ， 对于数学题也不要心存畏惧，先去思考一些题目相关的数学规律，然后也是可以尝试着去解出来的
373. Find K Pairs with Smallest Sums：先把题目扩展成矩阵，然后再利用heap逐个push和pop出元素。