2020-2-20 刷题记录

0X00 leetcode 刷题 6 道

• Leetcode 62. Unique Paths
• Leetcode 63. Unique Paths II
• Leetcode 64. Minimum Path Sum
• Leetcode 120. Triangle
• Leetcode 174. Dungeon Game
• Leetcode 304. Range Sum Query 2D - Immutable

0X01 每道题的小小记录

今天开始刷 DP 了

如何分辨是不是 DP

九章算法公开课里面给了我一些提示.这一部分的总结我放在我 DP 做了很多题以后

如何做 DP 题

我把他分成四部分:

• 找到子问题(最后一步是怎么生成的)
• 写出「转移方程」
• 边界条件与初始值
• 计算顺序

通常我们能把这四个问题解决了就能做出 DP 题目了

62. Unique Paths

动态规划的基础题目不多说

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        paths = [[1 for _ in range(n)] for _ in range(m)]

        def helper(x, y):
            # 边界
            if x < 0 or y < 0: return 0
            return paths[x][y]

        for x in range(m):
            for y in range(n):
                # 转移方程
                if x == y == 0: 
                    paths[x][y] == 0
                    continue
                paths[x][y] = helper(x-1, y) + helper(x, y-1)
        
        return paths[-1][-1]

63. Unique Paths II

边界没考虑清楚导致错误频出

class Solution:
    # 边界问题没考虑清楚
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:

        m, n = len(obstacleGrid), len(obstacleGrid[0])
        paths = [[0 for _ in range(n)] for _ in range(m)]
        def helper(x, y):
            if x < 0 or y < 0 or  obstacleGrid[x][y] == 1:
                return 0
            return paths[x][y]

        paths[0][0] = 1 if obstacleGrid[0][0] != 1 else 0

        for x in range(m):
            for y in range(n):
                if x == 0 and y == 0 or obstacleGrid[x][y] == 1 : continue
                paths[x][y] = helper(x-1, y) + helper(x, y-1)
        

        return paths[-1][-1]

64. Minimum Path Sum

这道题和爬梯子差不多,没有什么特别之处

找到每个点的最小 cost

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        def helper(x, y):
            if x < 0 or y < 0:return float("inf")
            return grid[x][y]

        for x in range(m):
            for y in range(n):
                if x == 0 and y == 0:continue
                grid[x][y] += min(helper(x-1, y), helper(x, y-1))
        
        return grid[-1][-1]

120. Triangle

跟上面那题差不多

这里有一个 follow up 空间 从 O() -> O(n)

原因就是我只需要上一层的每个点的最小值就行了

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        # s(x, y) = min(s(x-1, y-1) + s(x, y-1)) + cost[x][y]
        sums = [[v for v in line] for line in  triangle]
        def helper(x, y):
            if y < 0 or y >= len(sums[x]): return float("inf")
            return sums[x][y] 

        
        for x in range(len(triangle)):
            for y in range(len(triangle[x])):
                if x == y == 0: continue
                sums[x][y] += min(helper(x-1, y-1), helper(x-1, y))
        
    
        return min(sums[-1])

174. Dungeon Game

这道题我很难找到子问题

后来看了答案发现居然是倒着的,找到每点最小的 hp 不能是 0 最小是 1

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        # 这题非常的巧妙反着来的..
        # 求每点需要的最小的 Hp

        m, n = len(dungeon), len(dungeon[0])
        # 处理边界
        minHps = [[float("inf") for _ in range(n+1)] for _ in range(m+1)]
        # 到达公主那里最少需要 1 点血量
        minHps[m-1][n] = minHps[m][n-1] = 1
        print(minHps)
        # hp(x, y) = max(1, min(hp(x+1, y), hp(x, y+1)))

        for x in range(m-1, -1, -1):
            for y in range(n-1, -1, -1):
                minHps[x][y] = max(1, min(minHps[x+1][y], minHps[x][y+1]) - dungeon[x][y])
        
        return minHps[0][0]

304. Range Sum Query 2D - Immutable

这道题是 Range Sum Query 的矩阵版关键在于:

所以我们的代码:

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        self.sums =matrix
        
        for x in range(len(matrix)):
            for y in range(len(matrix[0])):
                if x == 0 and y == 0: continue
                elif x == 0: self.sums[x][y] += self.sums[x][y-1]
                elif y == 0: self.sums[x][y] += self.sums[x-1][y]
                else: self.sums[x][y] += self.sums[x][y-1] + self.sums[x-1][y] - self.sums[x-1][y-1]


    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        
        if row1 == 0 and col1 == 0:
            return self.sums[row2][col2]
        elif row1 == 0:
            return self.sums[row2][col2] - self.sums[row2][col1 - 1]
        elif col1 == 0:
            return self.sums[row2][col2] - self.sums[row1-1][col2]
        
        return self.sums[row2][col2] - self.sums[row2][col1 - 1] - self.sums[row1-1][col2] + self.sums[row1-1][col1 - 1]