1314. 矩阵区域和-矩阵前缀和算法

1314. 矩阵区域和-矩阵前缀和算法

给你一个 m x n 的矩阵 mat 和一个整数 k ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和：

i - k <= r <= i + k,
j - k <= c <= j + k 且
(r, c) 在矩阵内。
1
2
3

示例 1：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1
输出：[[12,21,16],[27,45,33],[24,39,28]]

示例 2：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2
输出：[[45,45,45],[45,45,45],[45,45,45]]

这题用c语言去做属实太难，可以学习一下，解题代码如下：

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** matrixBlockSum(int** mat, int matSize, int* matColSize, int k, int* returnSize, int** returnColumnSizes){

     int n=matSize,m=matColSize[0];
     *returnSize=n;
    int **presum=(int **)malloc(sizeof(int *)*matSize);
      int **re=(int **)malloc(sizeof(int *)*matSize);
    *returnColumnSizes=(int *)malloc(sizeof(int )*matSize);
    for(int i=0;i<matSize;i++){
        presum[i]=(int *)malloc(sizeof(int)*matColSize[0]);
         re[i]=(int *)malloc(sizeof(int)*matColSize[0]);
        ( *returnColumnSizes)[i]=m;
    }
   int col=1,rol=0;
 
     for(int i=0;i<n;i++){
       for(int j=0;j<m;j++){
         presum[i][j]=0;
       }
   }
  
     presum[0][0]=mat[0][0];
   

   while(col!=m&&rol!=n||m==1){
     
       if(rol==0){
          
           for(int i=col;i<m;i++){
               presum[rol][i]=presum[rol][i-1]+mat[rol][i];
           }
            rol++;
          
       }
       else{
             for(int i=col;i<m;i++){
               presum[rol][i]=presum[rol][i-1]+mat[rol][i]+presum[rol-1][i]-presum[rol-1][i-1];
           }
            rol++;

       }  if(col==1){
           for(int i=1;i<n;i++){
               presum[i][0]=presum[i-1][0]+mat[i][0];
           }
           
          
       }
       else{
             for(int i=rol;i<n;i++){
               presum[i][col]=presum[i-1][col]+mat[i][col]+presum[i][col-1]-presum[i-1][col-1];
           }
            col++;

       }
       if(m==1){
           break;
       }
   }
    

   for(int i=0;i<n;i++){
       for(int j=0;j<m;j++){
        int x0=fmax(0,i-k);
        int y0=fmax(0,j-k);
        int x1=fmin(n-1,i+k);
        int y1=fmin(m-1,j+k);
        int a,b;
        int d;
      
          if(x0==0||y0==0){
              d=0;
          }
          else{
              d=presum[x0-1][y0-1];
          }
          
        if(x0==0&&y0==0){
            a=0;
            b=0;
        }
        else{  
                if(y0==0){
                    a=0;
                }
                else{
                    a=presum[x1][y0-1];

                }
                if(x0==0){
                    b=0;
                }
                else{
                    b=presum[x0-1][y1];

                }
             }
          
            int sum=presum[x1][y1]-a-b+d;
            re[i][j]=sum;
          

       }
   }
  
return re;

}
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111