Matrix Block Sum
给一个2d数组和一个k, 求k的范围内的和. 这个题和range sum的那个一样的结构, 只是query部分稍加改动. 附上一个答案里很简练的做法.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Solution { public int[][] matrixBlockSum(int[][] mat, int K) { int m = mat.length, n = mat[0].length; int[][] sum = new int[m + 1][n + 1]; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + mat[i][j]; int[][] ans = new int[m][n]; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) { int r1 = Math.max(0, i - K); int c1 = Math.max(0, j - K); int r2 = Math.min(m, i + K + 1); int c2 = Math.min(n, j + K + 1); ans[i][j] = sum[r2][c2] - sum[r2][c1] - sum[r1][c2] + sum[r1][c1]; } return ans; } } |