当前位置:网站首页>1605. Sum the feasible matrix for a given row and column
1605. Sum the feasible matrix for a given row and column
2022-07-06 16:08:00 【mrbone9】
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;
}
边栏推荐
- 【练习-2】(Uva 712) S-Trees (S树)
- 7-1 understand everything (20 points)
- 渗透测试 ( 8 ) --- Burp Suite Pro 官方文档
- Information security - security professional name | CVE | rce | POC | Vul | 0day
- 【练习-4】(Uva 11988)Broken Keyboard(破损的键盘) ==(链表)
- Analyse du format protobuf du rideau en temps réel et du rideau historique de la station B
- 想应聘程序员,您的简历就该这样写【精华总结】
- Understand what is a programming language in a popular way
- 渗透测试 ( 3 ) --- Metasploit Framework ( MSF )
- Raspberry pie csi/usb camera uses mjpg to realize web camera monitoring
猜你喜欢
树莓派4B安装opencv3.4.0
Nodejs+vue online fresh flower shop sales information system express+mysql
渗透测试 ( 3 ) --- Metasploit Framework ( MSF )
Information security - threat detection engine - common rule engine base performance comparison
MySQL import database error [err] 1273 - unknown collation: 'utf8mb4_ 0900_ ai_ ci’
Penetration test 2 --- XSS, CSRF, file upload, file inclusion, deserialization vulnerability
【高老师UML软件建模基础】20级云班课习题答案合集
信息安全-威胁检测-NAT日志接入威胁检测平台详细设计
【高老师软件需求分析】20级云班课习题答案合集
Ball Dropping
随机推荐
Penetration test 2 --- XSS, CSRF, file upload, file inclusion, deserialization vulnerability
Truck History
C language is the watershed between low-level and high-level
Interesting drink
快速转 TypeScript 指南
想应聘程序员,您的简历就该这样写【精华总结】
Hdu-6025-prime sequence (girls' competition)
Shell Scripting
Research Report on surgical fluid treatment industry - market status analysis and development prospect prediction
渗透测试 2 --- XSS、CSRF、文件上传、文件包含、反序列化漏洞
【高老师软件需求分析】20级云班课习题答案合集
Pyside6 signal, slot
Quick to typescript Guide
信息安全-安全专业名称|CVE|RCE|POC|VUL|0DAY
Borg maze (bfs+ minimum spanning tree) (problem solving report)
【高老师UML软件建模基础】20级云班课习题答案合集
China's peripheral catheter market trend report, technological innovation and market forecast
Information security - threat detection - Flink broadcast stream broadcaststate dual stream merging application in filtering security logs
Interval sum ----- discretization
Information security - Epic vulnerability log4j vulnerability mechanism and preventive measures