LeeCode 1605 解空间贪心

题意

传送门 LeeCode 1605. 给定行和列的和求可行矩阵

题解

首先考虑构造任意矩阵的问题，将方程写作 $Ax=b$，则系数矩阵 $A$ 为 $(r+c)\times rc$ 矩阵，经过初等行变换可以证明解空间基的维数为 $$dimK(A)=n-r(A)=rc-(r+c-1)$$ 那么选择 $dimK(A)$ 个自由变量任意赋值即可。

此处多了非负整数矩阵的限制，考虑到矩阵元素仅对当前行与列的和产生影响，那么采用贪心的思路，为每个元素赋值为元素对应行与列的和的最小值；赋值后将对应值从两个和中删除。

class Solution { public: vector<vector<int>> restoreMatrix(vector<int> &rowSum, vector<int> &colSum) { int r = rowSum.size(), c = colSum.size(); vector<vector<int>> mat(r, vector<int>(c, 0)); for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { int tmp = min(rowSum[i], colSum[j]); mat[i][j] = tmp; rowSum[i] -= tmp, colSum[j] -= tmp; } } return mat; } };