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 -> i
    for j1: 0 -> j
        s = s + before[i1][j1]
after[i][j] = s


1≤n,m≤1000

样例
样例1：

输入:
2
2
[[1,3],[4,10]]
输出: 
[[1,2],[3,4]]
解释:
before:
1 2
3 4

after:
1 3
4 10
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

前置知识

前缀和数组
二维数组前缀和数组
1
2

参考答案

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36