娄底网站建设最专业,常州网站制作市场,推荐十个网站,各大招聘网站收费标准文章目录 题目问题反思 题目
题目如下#xff0c;其实并不难#xff0c;属于小而美的前缀和技巧中的体型。因为我之前做过这道题#xff0c;所以重刷也马上就能写。但是对比我写的和之前看别人写的#xff0c;明显我的代码不够简洁#xff0c;一个核心的差异在于对DP数组… 文章目录 题目问题反思 题目
题目如下其实并不难属于小而美的前缀和技巧中的体型。因为我之前做过这道题所以重刷也马上就能写。但是对比我写的和之前看别人写的明显我的代码不够简洁一个核心的差异在于对DP数组的定义上。 问题
先看下我的代码我对DP数组的定义是存储以00为起点到i j的数组之和。提交代码显示超出时间限制。
两个问题
边界条件处理贼麻烦我自己写的时候也注意到了(但这不是导致超时的原因)处理超时因为我每次要算一遍DP。
class NumMatrix:def __init__(self, matrix: List[List[int]]):self.matrix matrixdef sumFromLeftCorner(self):R, C len(self.matrix), len(self.matrix[0])dp [[0 for j in range(C)] for i in range(R)]for i in range(R):for j in range(C):if i 0 and j 0:dp[i][j] self.matrix[i][j]elif i 0:dp[i][j] dp[i][j-1] self.matrix[i][j]elif j 0:dp[i][j] dp[i-1][j] self.matrix[i][j]else:dp[i][j] dp[i-1][j] dp[i][j-1] - dp[i-1][j-1] self.matrix[i][j]return dpdef sumRegion(self, row1: int, col1: int, row2: int, col2: int) - int:dp self.sumFromLeftCorner()if row1 0 and col1 0:return dp[row2][col2]elif row1 0:return dp[row2][col2] - dp[row2][col1 - 1]elif col1 0:return dp[row2][col2] - dp[row1 - 1][col2]else:return dp[row2][col2] - dp[row1-1][col2] - dp[row2][col1-1] dp[row1-1][col1-1]
反思
对于第一个问题 边界条件处理贼麻烦我自己写的时候也注意到了(但这不是导致超时的原因) 只要改一下DP数组的定义即可存储以00为起点到i-1 j-1的数组之和。因此DP数组的长宽都要加1
对于第二个问题 处理超时因为我每次要算一遍DP。 将DP数组计算的过程放在__init__下面总是只计算一次然后重复调用其结果即可/
修改以后的代码如下明显简洁很多
class NumMatrix:def __init__(self, matrix: List[List[int]]):self.matrix matrixself.dp self.sumFromLeftCorner()def sumFromLeftCorner(self):R, C len(self.matrix), len(self.matrix[0])dp [[0 for j in range(C1)] for i in range(R1)]for i in range(1, R1):for j in range(1, C1):dp[i][j] dp[i-1][j] dp[i][j-1] - dp[i-1][j-1] self.matrix[i-1][j-1]return dpdef sumRegion(self, row1: int, col1: int, row2: int, col2: int) - int:return self.dp[row21][col21] - self.dp[row1][col21] - self.dp[row21][col1] self.dp[row1][col1]
