lintcode 1840 · 矩阵还原【中等 vip 二维前缀和数组】

题目

https://www.lintcode.com/problem/1840

现有一个n行m列的矩阵
before，对于before里的每一个元素
before[i][j]，我们会使用以下算法将其转化为
after[i][j]。现给定after矩阵，请还原出原有的矩阵before。s = 0
for i1: 0 -> ifor j1: 0 -> js = s + before[i1][j1]
after[i][j] = s1≤n,m≤1000样例
样例1：输入:
2
2
[[1,3],[4,10]]
输出: 
[[1,2],[3,4]]
解释:
before:
1 2
3 4after:
1 3
4 10

前置知识

前缀和数组
二维数组前缀和数组

参考答案

public class Solution {/*** @param n: the row of the matrix* @param m: the column of the matrix* @param after: the matrix* @return: restore the matrix*/public int[][] matrixRestoration(int n, int m, int[][] after) {/*after定义其实就是二维数组的前缀和after[i][j]=after[i-1][j]+after[i][j-1]+before[i][j]-after[i-1][j-1]可以推导处于before[i][j]的公式before[i][j]= after[i][j]-after[i-1][j]-after[i][j-1]+after[i-1][j-1]*/int[][] before = new int[n][m];for (int i = 0; i <n ; i++) {for (int j = 0; j <m ; j++) {int cur = after[i][j];if(i> 0){cur-= after[i-1][j];}if(j> 0){cur -= after[i][j-1];}if(i>0 && j>0){cur += after[i-1][j-1];}before[i][j] = cur;}}return before;}
}