1605. Sum the feasible matrix for a given row and column

Address ：

Power button https://leetcode-cn.com/problems/find-valid-matrix-given-row-and-column-sums/

subject ：

Here are two arrays of nonnegative integers  rowSum and  colSum , among  rowSum[i]  Is the second in a two-dimensional matrix i  Sum of row elements , colSum[j]  It's No j  The sum of column elements . In other words, you don't know every element in the matrix , But you know the sum of every row and column .

Please find the size of  rowSum.length x colSum.length  Arbitrarily Non-negative integer   matrix , And the matrix satisfies  rowSum and  colSum  The requirements of .

Please return any two-dimensional matrix that meets the requirements of the topic , The problem is guaranteed to exist At least one   Feasible matrix .

Example 1：

Input ：rowSum = [3,8], colSum = [4,7] Output ：[[3,0],       [1,7]] explain ： The first 0 That's ok ：3 + 0 = 3 == rowSum[0] The first 1 That's ok ：1 + 7 = 8 == rowSum[1] The first 0 Column ：3 + 1 = 4 == colSum[0] The first 1 Column ：0 + 7 = 7 == colSum[1] The sum of rows and columns meets the requirements of the title , And all matrix elements are nonnegative . Another feasible matrix is ：[[1,2],                   [3,5]]

Example 2：

Input ：rowSum = [5,7,10], colSum = [8,6,8] Output ：[[0,5,0],       [6,1,0],       [2,0,8]]

Example 3：

Input ：rowSum = [14,9], colSum = [6,9,8] Output ：[[0,9,5],       [6,0,3]]

Example 4：

Input ：rowSum = [1,0], colSum = [1] Output ：[[1],       [0]]

Example 5：

Input ：rowSum = [0], colSum = [0] Output ：[[0]]

Tips ：

1 <= rowSum.length, colSum.length <= 500 0 <= rowSum[i], colSum[i] <= 108 sum(rows) == sum(columns)

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/find-valid-matrix-given-row-and-column-sums
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas ：

Push backward to , The element takes the minimum value of the row and column , The maximum value will explode

When the element is determined , Row sum And Column sum The value will change accordingly

Repeat this process for the remaining elements

Method 1 、 Push backward

#define min(a,b) ( (a) < (b) ? (a) : (b) )

int **myMalloc(int r, int c, int *return_r, int **return_c)
{
	int **ret = (int **)malloc(sizeof(int *) * r);
	*return_r = r;
	
	*return_c =(int *)malloc(sizeof(int) * r); 
	for(int i=0; i<r; i++)
	{
		ret[i] = (int *)malloc(sizeof(int) * c);
		(*return_c)[i] = c;
	}

    return ret;
}

/**
 * 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** restoreMatrix(int* rowSum, int rowSumSize, int* colSum, int colSumSize, int* returnSize, int** returnColumnSizes){
    int row = rowSumSize;
    int col = colSumSize;
    int i, j;

    int **grid = myMalloc(row, col, returnSize, returnColumnSizes);

    for(i=0; i<row; i++)
    {
        for(j=0; j<col; j++)
        {
            grid[i][j] = min(rowSum[i], colSum[j]);
            rowSum[i] -= grid[i][j];
            colSum[j] -= grid[i][j];
        }
    }

    
 

    return grid;
}

See more brush notes