Java实现 LeetCode 304 二维区域和检索 - 矩阵不可变
2023-09-14 08:58:05 时间
304. 二维区域和检索 - 矩阵不可变
给定一个二维矩阵,计算其子矩形范围内元素的总和,该子矩阵的左上角为 (row1, col1) ,右下角为 (row2, col2)。
Range Sum Query 2D
上图子矩阵左上角 (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 {
static int[][] data = new int[1050][1050];
public NumMatrix(int[][] matrix) {
if(matrix.length > 0){
for(int i = 0;i < matrix.length;i++){
int sum = 0;
for(int j = 1;j <= matrix[0].length;j++){
sum += matrix[i][j - 1];
data[i][j] = sum;
}
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
int sum = 0;
for(int i = row1;i <= row2;i++ ){
sum += data[i][col2 + 1] - data[i][col1];
}
return sum;
}
}
/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix obj = new NumMatrix(matrix);
* int param_1 = obj.sumRegion(row1,col1,row2,col2);
*/
相关文章
- Java实现 LeetCode 830 较大分组的位置(暴力模拟)
- Java实现 LeetCode 826 安排工作以达到最大收益(暴力DP)
- Java实现 LeetCode 816 模糊坐标(暴力)
- Java实现 LeetCode 785 判断二分图(分析题)
- Java实现 LeetCode 692 前K个高频单词(map的应用)
- Java实现 LeetCode 659 分割数组为连续子序列 (哈希)
- Java实现 LeetCode 649 Dota2 参议院(暴力大法)
- Java实现 LeetCode 560 和为K的子数组(某著名排序大法改编)
- Java实现 LeetCode 999 车的可用捕获量(简单搜索)
- Java实现 LeetCode 519 随机翻转矩阵
- Java实现 LeetCode 518 零钱兑换 II
- Java实现 LeetCode 467 环绕字符串中唯一的子字符串
- Java实现 LeetCode 447 回旋镖的数量
- Java实现 LeetCode 443 压缩字符串
- Java实现 LeetCode 424 替换后的最长重复字符
- Java实现 LeetCode 405 数字转换为十六进制数
- Java实现 LeetCode 384 打乱数组
- Java实现 LeetCode 374 猜数字大小 II
- Java实现 LeetCode 304 二维区域和检索 - 矩阵不可变
- Java实现 LeetCode 218 天际线问题
- Java实现 LeetCode 150 逆波兰表达式求值
- Java实现 LeetCode 114 二叉树展开为链表
- Java实现 LeetCode 111 二叉树的最小深度
- Java实现 LeetCode 88 合并两个有序数组
- Java实现 LeetCode 2 两数相加
- Java实现 LeetCode_0038_CountandSay
- java实现取球游戏
- 【java】Java连接mysql数据库及mysql驱动jar包下载和使用
- Java 关于java.util.LinkedHashMap cannot be cast to 实体类问题答案