leetcode 304. Range Sum Query 2D - Immutable

题目大意，给定一个二维矩阵，再给定左上角和右下角的坐标，求坐标围成的矩形的元素的和

解题思路：这个题目和前面的221. Maximal Square类似。把矩形围成的区域表示成以(0, 0)为初始点的矩形的和的运算。这样在运算部分时间复杂度就是O(1).

在求解(0, 0)开始的矩形的元素和的时候，使用递推/动态规划。

动态规划

class NumMatrix(object):

    def __init__(self, matrix):
        """
        :type matrix: List[List[int]]
        """
        m = len(matrix)
        if m == 0:
            return
        n = len(matrix[0])
        sum_ = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        # padding sum_ to make sum calculation easier
        for i in range(1, m+1):
            for j in range(1, n+1):
                sum_[i][j] = sum_[i-1][j] + sum_[i][j-1] - sum_[i-1][j-1] + matrix[i-1][j-1]
        self.sum_ = sum_        

    def sumRegion(self, row1, col1, row2, col2):
        """
        :type row1: int
        :type col1: int
        :type row2: int
        :type col2: int
        :rtype: int
        """
        return self.sum_[row2 + 1][col2 + 1] - self.sum_[row1 - 1 + 1][col2 + 1] \
            - self.sum_[row2 + 1][col1 - 1 + 1] + self.sum_[row1 - 1 + 1][col1 - 1 + 1]

# Your NumMatrix object will be instantiated and called as such:
# obj = NumMatrix(matrix)
# param_1 = obj.sumRegion(row1,col1,row2,col2)

pydata

Keep Looking, Don't Settle

leetcode 304. Range Sum Query 2D - Immutable

动态规划