二维子矩阵的和

给定一个二维矩阵 matrix，以下类型的多个请求：

  • 计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。

实现 NumMatrix 类：

  • NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
  • int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1) 、右下角 (row2, col2) 的子矩阵的元素总和。

1.二维前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class NumMatrix {
public:
    vector<vector<int>> prefix;
    NumMatrix(vector<vector<int>>& matrix) {
        /* 初始化前缀和数组 */
        if (matrix.size() == 0) return;
        int m = matrix.size();
        int n = matrix[0].size();
        prefix.assign(m + 1, vector<int>(n + 1, 0));
        //prefix.resize(m + 1, vector<int>(n + 1));
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                prefix[i + 1][j + 1] = prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j] + matrix[i][j];
    }
    
    int sumRegion(int x1, int y1, int x2, int y2) {
        /* 利用前缀和数组进行面积和sum的计算 */
        return prefix[x2 + 1][y2 + 1] + prefix[x1][y1] - prefix[x2 + 1][y1] - prefix[x1][y2 + 1];
    }
};

2.总结resize方法

初始化二维矩阵的两种方式：

  • prefix.assign(m + 1, vector<int>(n + 1, 0));
  • prefix.resize(m + 1, vector<int>(n + 1));

（1）resize函数作用：

改变容器的大小，使得其包含n个元素，常见三种用法

  1. 如果n小于当前的容器大小，那么则保留容器的前n个元素，去除（erasing）超过的部分。

  2. 如果n大于当前的容器大小，则通过在容器结尾插入(inserting)适合数量的元素使得整个容器大小达到n。

    • 且如果给出val，插入的新元素全为val，

    • 否则，执行默认构造函数。

  3. 如果n大于当前容器的容量（capacity）时，则会自动重新分配一个存储空间。

  4. 注意：如果发生了重新分配，则使用容器的分配器分配存储空间，这可能会在失败时抛出异常。

（2）测试：

对二维数组进行resize操作，注意：如果没有事先没有对vector进行resize初始化，直接使用下标访问会报segmentmentfault错误。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <vector>
using namespace std;

void print(vector<vector<int>> v) {
    int m = v.size();
    int n = v[0].size();
    cout << "print vector<" << m << ", " << n << ">" << endl;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) cout << v[i][j] << "\t ";
        cout << endl;
    }
}

int main() {
    //1.初始化方案1
    vector<vector<int>> v1;
    v1.resize(10, vector<int>(10));
    print(v1);
    for (int i = 0; i < 10; ++i)
        for (int j = 1; j <= 10; ++j)
            v1[i][j - 1] = i * 10 + j;
    print(v1);

    //2.初始化方案2
    vector<vector<int>> v2;
    v2.resize(10);
    for (int i = 0; i < 10; ++i)
        for (int j = 1; j <= 10; ++j)
            v2[i].push_back(i * 10 + j);
    print(v2);

    //3.其他测试
    vector<vector<int>> v3;
    vector<int> temp1; temp1.resize(10, -1);
    v3.resize(10, temp1);
    print(v3);

    //4.其他测试
    vector<vector<int>> v4;
    vector<int> temp2; temp2.resize(15);
    v4.resize(10, temp2);
    print(v4);

    return 0;
}