leetcode链接:二维区域和检索
要点:前缀和
class NumMatrix {// 定义:preSum[i][j] 记录 matrix 中子矩阵 [0, 0, i-1, j-1] 的元素和
private int[][] preSum;
public NumMatrix(int[][] matrix) {int m = matrix.length;
int n = matrix[0].length;
if(m == 0 || n == 0) return;
// 构造前缀和矩阵
preSum = new int[m + 1][n + 1];
for(int i = 1; i< m + 1; i++){for(int j = 1; j< n + 1; j++){// 计算每个矩阵 [0, 0, i, j] 的元素和
preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + matrix[i -1][j - 1];
}
}
}
// 计算子矩阵 [x1, y1, x2, y2] 的元素和
public int sumRegion(int row1, int col1, int row2, int col2) {// 目标矩阵之和由四个相邻矩阵运算获得
return preSum[row2 + 1][col2 + 1] - preSum[row2 + 1][col1] - preSum[row1][col2 + 1] + preSum[row1][col1];
}
}
2、pythonclass NumMatrix:
def __init__(self, matrix: List[List[int]]):
m, n = len(matrix), (len(matrix[0]) if matrix else 0)
self.sums = [[0] * (n + 1) for _ in range(m + 1)]
_sums = self.sums
for i in range(m):
for j in range(n):
_sums[i + 1][j + 1] = _sums[i][j + 1] + _sums[i + 1][j] - _sums[i][j] + matrix[i][j]
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) ->int:
_sums = self.sums
return _sums[row2 + 1][col2 + 1] - _sums[row1][col2 + 1] - _sums[row2 + 1][col1] + _sums[row1][col1]
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧