C语言重构【304】二维区域和检索 - 矩阵不可变

╰半夏微凉° 2023-01-19 13:00 9阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。
    
    
    上图子矩阵左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，该子矩形内元素的总和为 8。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5bXVhbXVh_size_16_color_FFFFFF_t_70]

示例：
    
    给定 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

#### 方案： ####

*  大致思想就是先存好每个元素到0.0元素的和，然后要算的时候简单计算一下就行了，不用每个都遍历过去

class NumMatrix
    { 
    public:
        vector<vector<int>> mymatrix;
        NumMatrix(vector<vector<int>> &matrix)
        { 
            //意思是计算出某一点到（0,0）的和然后-上-左+左上
            int row = matrix.size();
            int col = matrix[0].size();
            vector<vector<int>> tmp(row, vector<int>(col, 0));
            mymatrix = tmp;
            mymatrix[0][0] = matrix[0][0];
            for (int i = 1; i < row; i++)
            { 
                //init 第0列
                mymatrix[i][0] = mymatrix[i - 1][0] + matrix[i][0];
                // cout<<mymatrix[i][0]<<endl;
            }
            for (int i = 1; i < col; i++)
            { 
                //init 第0行
                mymatrix[0][i] = mymatrix[0][i - 1] + matrix[0][i];
                // cout<<mymatrix[0][i]<<endl;
            }
            for (int i = 1; i < row; i++)
            { 
                for (int j = 1; j < col; j++)
                { 
                    mymatrix[i][j] = mymatrix[i - 1][j] + mymatrix[i][j - 1] - mymatrix[i - 1][j - 1] + matrix[i][j];
                    // cout<<mymatrix[i][j]<<endl;
                }
            }
        }
    
        int sumRegion(int row1, int col1, int row2, int col2)
        { 
            //=(r2,c2)-(r1-1,c2)-(r2,c1-1)+(r1-1,c1-1)
            int res = mymatrix[row2][col2];
            if (row1 > 0)
                res -= mymatrix[row1 - 1][col2];
            if (col1 > 0)
                res -= mymatrix[row2][col1 - 1];
            if (row1 > 0 && col1 > 0)
                res += mymatrix[row1 - 1][col1 - 1];
            return res;
        }
    };
    
    /** * Your NumMatrix object will be instantiated and called as such: * NumMatrix* obj = new NumMatrix(matrix); * int param_1 = obj->sumRegion(row1,col1,row2,col2); */

##### 复杂度计算 #####

*  时间复杂度：O(1):但是建造和矩阵的时候是n^2
 *  空间复杂度：O(n^2)

[Git]: https://github.com/ch98road/leetcode
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5bXVhbXVh_size_16_color_FFFFFF_t_70]: /images/20221021/f1d2e3cbd78a457d8428c45e6a926078.png