一个网站应该怎么做,无极电影网首页,自己建一个网站需要多少钱,如何建立游戏网站平台给定一个二维矩阵#xff0c;计算其子矩形范围内元素的总和#xff0c;该子矩阵的左上角为 (row1, col1) #xff0c;右下角为 (row2, col2)。 上图子矩阵左上角 (row1, col1) (2, 1) #xff0c;右下角(row2, col2) (4, 3)#xff0c;该子矩形内元素的总和为 8。
示例…给定一个二维矩阵计算其子矩形范围内元素的总和该子矩阵的左上角为 (row1, col1) 右下角为 (row2, col2)。 上图子矩阵左上角 (row1, col1) (2, 1) 右下角(row2, col2) (4, 3)该子矩形内元素的总和为 8。
示例:
给定 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 说明:
你可以假设矩阵不可变。 会多次调用 sumRegion 方法。 你可以假设 row1 ≤ row2 且 col1 ≤ col2。
思路 我们想求黑框框应该黄框框红框框-灰框框红黄重合部分加了两次所以要减去
请注意 不要忘了判空。
class NumMatrix {int[][] temp;public NumMatrix(int[][] matrix) {if (matrix.length 0 || matrix[0].length 0) return;int lenAmatrix.length;int lenBmatrix[0].length;tempnew int[lenA][lenB];temp[0][0]matrix[0][0];for(int i1;ilenA;i){temp[i][0]temp[i-1][0]matrix[i][0];}for(int i1;ilenB;i){temp[0][i]temp[0][i-1]matrix[0][i];}for(int i1;ilenA;i){for(int j1;jlenB;j){temp[i][j]temp[i-1][j]temp[i][j-1]-temp[i-1][j-1]matrix[i][j];}}}public int sumRegion(int row1, int col1, int row2, int col2) {int Acol10?temp[row2][col1-1]:0;int Brow10?temp[row1-1][col2]:0;int CA0 || B0?0:temp[row1-1][col1-1];return temp[row2][col2]-A-BC;}
}/*** Your NumMatrix object will be instantiated and called as such:* NumMatrix obj new NumMatrix(matrix);* int param_1 obj.sumRegion(row1,col1,row2,col2);*/
这个代码还不对看求C的时候我使用A和B区域是否等于零来判断是否是边界其实是不对的万一一堆数加起来真的等于零呢
最终
class NumMatrix {int[][] temp;public NumMatrix(int[][] matrix) {if (matrix.length 0 || matrix[0].length 0) return;int lenAmatrix.length;int lenBmatrix[0].length;tempnew int[lenA][lenB];temp[0][0]matrix[0][0];for(int i1;ilenA;i){temp[i][0]temp[i-1][0]matrix[i][0];}for(int i1;ilenB;i){temp[0][i]temp[0][i-1]matrix[0][i];}for(int i1;ilenA;i){for(int j1;jlenB;j){temp[i][j]temp[i-1][j]temp[i][j-1]-temp[i-1][j-1]matrix[i][j];}}}public int sumRegion(int row1, int col1, int row2, int col2) {int Acol10?temp[row2][col1-1]:0;int Brow10?temp[row1-1][col2]:0;int Ccol10 || row10?0:temp[row1-1][col1-1];return temp[row2][col2]-A-BC;}
}/*** Your NumMatrix object will be instantiated and called as such:* NumMatrix obj new NumMatrix(matrix);* int param_1 obj.sumRegion(row1,col1,row2,col2);*/
官方思路一样在数组左边和上边加了一层写起来方便很多我给忘了可以这么写了。
又被官方虐了55555
private int[][] dp;public NumMatrix(int[][] matrix) {if (matrix.length 0 || matrix[0].length 0) return;dp new int[matrix.length 1][matrix[0].length 1];for (int r 0; r matrix.length; r) {for (int c 0; c matrix[0].length; c) {dp[r 1][c 1] dp[r 1][c] dp[r][c 1] matrix[r][c] - dp[r][c];}}
}public int sumRegion(int row1, int col1, int row2, int col2) {return dp[row2 1][col2 1] - dp[row1][col2 1] - dp[row2 1][col1] dp[row1][col1];
}
