2020-2-20 刷题记录
2020-02-20 本文已影响0人
madao756
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]
