leetcode Range Sum Query 2D - Immutable

leetcode Range Sum Query 2D - Immutable

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (_row_1, _col_1) and lower right corner (_row_2, _col_2).

The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:

Given matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

Note:

1. You may assume that the matrix does not change.
2. There are many calls to sumRegion function.
3. You may assume that _row_1 ≤ _row_2 and _col_1 ≤ _col_2.

题目地址  leetcode Range Sum Query 2D - Immutable

题意：

给定一个矩阵，和两个矩阵的坐标(row1,col1)，（row2,col2），让你计算他们之间元素的和

思路：

和之前的那题leetcode Range Sum Query – Immutable很像，只不过这次用二维数组进行和的存储。

记得多减去的要加回来~

Code:

class NumMatrix(object):
    def __init__(self, matrix):
        """
        initialize your data structure here.
        :type matrix: List[List[int]]
        """
        self.false_input =  not matrix or not matrix[0]
        if  self.false_input: return
        m, n = len(matrix) + 1, len(matrix[0]) + 1
        self.sum = [[0 for j in xrange(n)] for i in xrange(m)]
        for i in xrange(1, m):
            for j in xrange(1, n):
                self.sum[i][j] = self.sum[i][j - 1] + matrix[i - 1][j - 1]

        for i in xrange(1, m):
            for j in xrange(1, n):
                self.sum[i][j] = self.sum[i - 1][j] + self.sum[i][j]

    def sumRegion(self, row1, col1, row2, col2):
        """
        sum of elements matrix[(row1,col1)..(row2,col2)], inclusive.
        :type row1: int
        :type col1: int
        :type row2: int
        :type col2: int
        :rtype: int
        """
        if  self.false_input: return 0
        return self.sum[row2 + 1][col2 + 1]  - self.sum[row2 + 1][col1] - self.sum[row1][col2 + 1]\
               + self.sum[row1][col1]