天天看點

力扣刷題筆記--304 二維區域和檢索 - 矩陣不可變 字首和304 二維區域和檢索 - 矩陣不可變

304 二維區域和檢索 - 矩陣不可變

作者:AC_OIer

連結:https://leetcode-cn.com/problems/range-sum-query-2d-immutable/solution/xia-ci-ru-he-zai-30-miao-nei-zuo-chu-lai-ptlo/

來源:力扣(LeetCode)

著作權歸作者所有。商業轉載請聯系作者獲得授權,非商業轉載請注明出處。

力扣刷題筆記--304 二維區域和檢索 - 矩陣不可變 字首和304 二維區域和檢索 - 矩陣不可變

思路:

二維字首和解決的是二維矩陣中的矩形區域求和問題。

二維字首和數組中的每一個格子記錄的是「以目前位置為區域的右下角(區域左上角恒定為原數組的左上角)的區域和」

即 sum 的每個元素表示其區域和。

假設 i 和 j 為固定值 3 來了解。

力扣刷題筆記--304 二維區域和檢索 - 矩陣不可變 字首和304 二維區域和檢索 - 矩陣不可變

如何初始化sum中的元素 , (sum 的每個元素表示其區域和);

根據上圖可知,就是求 f[i][j] ;

是以當我們要求 (x1, y1) 作為左上角,(x2, y2) 作為右下角 的區域和的時候,可以直接利用字首和數組快速求解:

至于求子矩陣元素和就是求 matrix[i][j];

class NumMatrix {
    int[][] sum;
    public NumMatrix(int[][] matrix) {
        int n = matrix.length, m = n == 0 ? 0 : matrix[0].length;
        // 與「一維字首和」一樣,字首和數組下标從 1 開始,是以設定矩陣形狀為 [n + 1][m + 1](模闆部分)
        sum = new int[n + 1][m + 1];
        // 預處理除字首和數組(模闆部分)
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
    }

    public int sumRegion(int x1, int y1, int x2, int y2) {
        // 求某一段區域和 [i, j] 的模闆是 sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];(模闆部分)
        // 但由于我們源數組下标從 0 開始,是以要在模闆的基礎上進行 + 1
        x1++; y1++; x2++; y2++;
        return sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
    }
}

           

繼續閱讀