LeetCode 筆記 - 304. Range Sum Query 2D - Immutable

Posted on

題目在此 304. Range Sum Query 2D - Immutable

給定一個 2D matrix，請根據給定的矩形範圍計算出舉行總和

image 55

解題思維

這題我們要用 Prefix Sum 來幫助我們
如果沒寫過他的基本題，建議可以先從 303. Range Sum Query - Immutable 這裡開始

基本概念很簡單，先建立起 2D 的 Prefix Sum Table
每個 x, y 代表的是從 matrix[0][0] 到 matrix[y][x] 形成的矩形總和

所以如果我們想要白色那塊矩形的總和，那就會是

Prefix Sum Table [y][x]
-
Prefix Sum Table [y][x - 1]
-
Prefix Sum Table [y - 1][x1]
+
Prefix Sum Table [y - 1][x1 - 1]

如下圖所示

image 56

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        
        self.y = len(matrix)
        self.x = len(matrix[0])
        
        self.count_map = collections.defaultdict(int)

        for y in range(self.y):
            count = 0
            for x in range(self.x):
                count += matrix[y][x]
                self.count_map[(y, x)] = self.count_map[(y - 1, x)] + count

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return self.count_map[(row2, col2)] - self.count_map[(row1 - 1, col2)] - self.count_map[(row2, col1 - 1)] + self.count_map[(row1 - 1, col1 - 1)]

也許你也會想看看