[2536] Increment Submatrices by One

看起來是對的，但是會超時是吧XD

（一天到晚在超時XDDDD）

先紀錄一下會超時的版本....

/**

* 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** rangeAddQueries(int n, int** queries, int queriesSize, int* queriesColSize, int* returnSize, int** returnColumnSizes){

int **matrix= malloc (sizeof(int*)*n);

(*returnColumnSizes) = malloc (sizeof(int)*n);

for (int i=0;i < n; i++)

{

(*returnColumnSizes)[i] = n;

matrix[i]=malloc(sizeof(int)*n);

for (int j=0;j<n;j++)

matrix[i][j]=0;

}

for (int i=0;i <queriesSize; i++)

{

int x,y,x1,y1,x2,y2;

x1=queries[i][0];

y1=queries[i][1];

x2=queries[i][2];

y2=queries[i][3];

x=x1;

y=y1;

for (x=x1; x<=x2; x++)

for (y=y1;y<=y2;y++)

matrix[x][y]+=1;

}

*returnSize = n;

return matrix;

}

偷看了一下相關問題，竟然是prefix sum 嗎！！！

讓我想一想兒 XD

哦哦哦坐了個捷運偶爾想一想回家寫了稍微debug一下就寫好了！怎麼那麼感人！！！

但如果面試出這題，我第一次看見，也寫不出來吧。哈！

int** rangeAddQueries(int n, int** queries, int queriesSize, int* queriesColSize, int* returnSize, int** returnColumnSizes){

int **matrix= malloc (sizeof(int*)*n);

(*returnColumnSizes) = malloc (sizeof(int)*n);

for (int i=0;i < n; i++)

{

(*returnColumnSizes)[i] = n;

matrix[i]=malloc(sizeof(int)*n);

for (int j=0;j<n;j++)

matrix[i][j]=0;

}

for (int i=0;i <queriesSize; i++)

{

int x,y,x1,y1,x2,y2;

x1=queries[i][0];

y1=queries[i][1];

x2=queries[i][2];

y2=queries[i][3];

for (int j=x1; j<=x2;j++)

{

matrix[j][y1]+=1;

if (y2 != (n-1))

matrix[j][y2+1]-=1;

}

}

for (int i=0;i<n;i++)

for (int j=1;j<n;j++)

matrix[i][j]+= matrix[i][j-1];

*returnSize = n;

return matrix;

}