leetcode304

 1 class NumMatrix:
 2     def __init__(self, matrix: 'List[List[int]]'):
 3         self.matrix = matrix
 4         m,n = 0,0
 5         m = len(matrix)
 6         if m > 0:
 7             n = len(matrix[0])
 8         self.prefix = [[0 for _ in range(n)]for _ in range(m)]
 9         for i in range(m):
10             for j in range(n):
11                 if j == 0:
12                     self.prefix[i][j] = matrix[i][j]
13                 else:
14                     self.prefix[i][j] = self.prefix[i][j-1] + matrix[i][j]
15         #print(self.prefix)
16         for j in range(n):
17             for i in range(1,m):
18                 self.prefix[i][j] = self.prefix[i-1][j] + self.prefix[i][j]
19         #print(self.prefix)
20 
21     def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
22         if row1 == row2  and col1 == col2:
23             return self.matrix[row1][col1]
24         botton_right = self.prefix[row2][col2]
25         botton_left = 0
26         if col1 > 0:
27             botton_left = self.prefix[row2][col1-1]
28         top_right = 0
29         if row1 > 0:
30             top_right = self.prefix[row1-1][col2]
31         top_left = 0
32         if row1 > 0 and col1 > 0:
33             top_left = self.prefix[row1-1][col1-1]
34 
35         return botton_right - botton_left - top_right + top_left

算法思路：二维数组。

这道题目是二维数组区域求和的常见题型，先计算从(0,0)点到(i,j)点的累加和。

然后再用四个矩形区域的加减运算，求出局部矩形的和。