一【題目類(lèi)別】

• 矩陣

二【題目難度】

• 中等

三【題目編號(hào)】

• 304.二維區(qū)域和檢索-矩陣不可變

四【題目描述】

• 給定一個(gè)二維矩陣 matrix，以下類(lèi)型的多個(gè)請(qǐng)求：
  • 計(jì)算其子矩形范圍內(nèi)元素的總和，該子矩陣的 左上角 為 (row1, col1) ，右下角 為 (row2, col2) 。
• 實(shí)現(xiàn) NumMatrix 類(lèi)：
  • NumMatrix(int[][] matrix) 給定整數(shù)矩陣 matrix 進(jìn)行初始化
  • int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩陣的元素總和。

五【題目示例】

• 示例 1：
  • 
  • 輸入:
    • [“NumMatrix”,“sumRegion”,“sumRegion”,“sumRegion”]
    • [[[[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]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
  • 輸出:
    • [null, 8, 11, 12]
  • 解釋:
    • NumMatrix numMatrix = new NumMatrix([[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]]);
    • numMatrix.sumRegion(2, 1, 4, 3); // return 8 (紅色矩形框的元素總和)
    • numMatrix.sumRegion(1, 1, 2, 2); // return 11 (綠色矩形框的元素總和)
    • numMatrix.sumRegion(1, 2, 2, 4); // return 12 (藍(lán)色矩形框的元素總和)

六【題目提示】

• $m==matrix.length$
• $n==matrix[i].length$
• $1<=m,n<=200$
• $?10^5<=matrix[i][j]<=10^5$
• $0<=row1<=row2<m$
• $0<=col1<=col2<n$
• $最多調(diào)用10^4次sumRegion方法$

七【解題思路】

• 利用前綴和的思想
• 新建一個(gè)二維數(shù)組，這個(gè)二維數(shù)組比原來(lái)的二維數(shù)組多一列，因?yàn)槎S數(shù)組的每個(gè)位置都存儲(chǔ)了之前元素的和，故多添加的一列就存儲(chǔ)了原來(lái)二維數(shù)組最后一列的元素及之前值的和，我們只需要按照這個(gè)規(guī)律遍歷填充這個(gè)新的二維數(shù)組即可
• 對(duì)于傳入的二維區(qū)域，我們只需要逐行的利用前綴和進(jìn)行計(jì)算求和
• 最后返回結(jié)果即可

八【時(shí)間頻度】

• 時(shí)間復(fù)雜度：$O(mn)$，$m、n$分別為傳入的二維數(shù)組的行數(shù)和列數(shù)
• 空間復(fù)雜度：$O(mn)$，$m、n$分別為傳入的二維數(shù)組的行數(shù)和列數(shù)

九【代碼實(shí)現(xiàn)】

1. Java語(yǔ)言版

class NumMatrix {

    int[][] sums;

    public NumMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        sums = new int[m][n+1];
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                sums[i][j + 1] = sums[i][j] + matrix[i][j];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int res = 0;
        for(int i = row1;i <= row2;i++){
            res += sums[i][col2 + 1] - sums[i][col1];
        }
        return res;
    }

}

2. C語(yǔ)言版

typedef struct 
{
    int** sums;
    int sumsSize;
} NumMatrix;


NumMatrix* numMatrixCreate(int** matrix, int matrixSize, int* matrixColSize) 
{
    int m = matrixSize;
    int n = matrixColSize[0];
    NumMatrix* obj = (NumMatrix*)malloc(sizeof(NumMatrix));
    obj->sums = (int**)malloc(sizeof(int*) * m);
    obj->sumsSize = m;
    for(int i = 0;i < m;i++)
    {
        obj->sums[i] = (int*)malloc(sizeof(int) * (n + 1));
    }
    for(int i = 0;i < m;i++)
    {
        for(int j = 0;j < n;j++)
        {
            obj->sums[i][j + 1] = obj->sums[i][j] + matrix[i][j];
        }
    }
    return obj;
}

int numMatrixSumRegion(NumMatrix* obj, int row1, int col1, int row2, int col2) 
{
    int res = 0;
    for(int i = row1;i <= row2;i++)
    {
        res += obj->sums[i][col2 + 1] - obj->sums[i][col1];
    }
    return res;
}

void numMatrixFree(NumMatrix* obj) 
{
    for(int i = 0;i < obj->sumsSize;i++)
    {
        free(obj->sums[i]);
    }
    free(obj);
}

3. Python語(yǔ)言版

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        m = len(matrix)
        n = len(matrix[0])
        self.sums = [[0] * (n + 1) for _ in range(m)]
        for i in range(0, m):
            for j in range(0, n):
                self.sums[i][j + 1] = self.sums[i][j] + matrix[i][j]

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        res = 0
        for i in range(row1, row2 + 1):
            res += self.sums[i][col2 + 1] - self.sums[i][col1]
        return res

4. C++語(yǔ)言版

class NumMatrix {
public:
    vector<vector<int>> sums;

    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        sums.resize(m, vector<int>(n + 1));
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                sums[i][j + 1] = sums[i][j] + matrix[i][j];
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        int res = 0;
        for(int i = row1;i <= row2;i++){
            res += sums[i][col2 + 1] - sums[i][col1];
        }
        return res;
    }
};

十【提交結(jié)果】

1. Java語(yǔ)言版
   

2. C語(yǔ)言版
   

3. Python語(yǔ)言版
   

4. C++語(yǔ)言版
   文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-642322.html

到了這里，關(guān)于【LeetCode每日一題】——304.二維區(qū)域和檢索-矩陣不可變的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！