class Solution {
public:
vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
}
};
1253. 重构 2 行二进制矩阵
给你一个 2 行 n 列的二进制数组：
0 就是 1。0 行的元素之和为 upper。1 行的元素之和为 lower。i 列（从 0 开始编号）的元素之和为 colsum[i]，colsum 是一个长度为 n 的整数数组。你需要利用 upper，lower 和 colsum 来重构这个矩阵，并以二维整数数组的形式返回它。
如果有多个不同的答案，那么任意一个都可以通过本题。
如果不存在符合要求的答案，就请返回一个空的二维数组。
示例 1：
输入：upper = 2, lower = 1, colsum = [1,1,1] 输出：[[1,1,0],[0,0,1]] 解释：[[1,0,1],[0,1,0]] 和 [[0,1,1],[1,0,0]] 也是正确答案。
示例 2：
输入：upper = 2, lower = 3, colsum = [2,2,1,1] 输出：[]
示例 3：
输入：upper = 5, lower = 5, colsum = [2,1,2,0,1,0,1,2,0,1] 输出：[[1,1,1,0,1,0,0,1,0,0],[1,0,1,0,0,0,1,1,0,1]]
提示：
1 <= colsum.length <= 10^50 <= upper, lower <= colsum.length0 <= colsum[i] <= 2原站题解
javascript 解法, 执行用时: 140 ms, 内存消耗: 59.3 MB, 提交时间: 2023-06-29 09:24:43
/**
* @param {number} upper
* @param {number} lower
* @param {number[]} colsum
* @return {number[][]}
*/
var reconstructMatrix = function(upper, lower, colsum) {
let n = colsum.length;
let sumVal = 0;
let twoNum = 0;
for (let i = 0; i < n; i++) {
if (colsum[i] == 2) {
twoNum++;
}
sumVal += colsum[i];
}
if (sumVal != upper + lower || Math.min(upper, lower) < twoNum) {
return [];
}
upper -= twoNum;
lower -= twoNum;
let res = Array.from({ length: 2 }, () => new Array(n).fill(0));
for (let i = 0; i < n; i++) {
if (colsum[i] == 2) {
res[0][i] = res[1][i] = 1;
} else if (colsum[i] == 1) {
if (upper > 0) {
res[0][i] = 1;
upper--;
} else {
res[1][i] = 1;
}
}
}
return res;
}
golang 解法, 执行用时: 68 ms, 内存消耗: 8.3 MB, 提交时间: 2023-06-29 09:23:52
func reconstructMatrix(upper int, lower int, colsum []int) [][]int {
n := len(colsum)
ans := make([][]int, 2)
for i := range ans {
ans[i] = make([]int, n)
}
for j, v := range colsum {
if v == 2 {
ans[0][j], ans[1][j] = 1, 1
upper--
lower--
}
if v == 1 {
if upper > lower {
upper--
ans[0][j] = 1
} else {
lower--
ans[1][j] = 1
}
}
if upper < 0 || lower < 0 {
break
}
}
if upper != 0 || lower != 0 {
return [][]int{}
}
return ans
}
cpp 解法, 执行用时: 68 ms, 内存消耗: 61.1 MB, 提交时间: 2023-06-29 09:23:38
class Solution {
public:
vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
int n = colsum.size();
vector<vector<int>> ans(2, vector<int>(n));
for (int j = 0; j < n; ++j) {
if (colsum[j] == 2) {
ans[0][j] = ans[1][j] = 1;
upper--;
lower--;
}
if (colsum[j] == 1) {
if (upper > lower) {
upper--;
ans[0][j] = 1;
} else {
lower--;
ans[1][j] = 1;
}
}
if (upper < 0 || lower < 0) {
break;
}
}
return upper || lower ? vector<vector<int>>() : ans;
}
};
java 解法, 执行用时: 12 ms, 内存消耗: 59.7 MB, 提交时间: 2023-06-29 09:23:23
class Solution {
public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
int n = colsum.length;
List<Integer> first = new ArrayList<>();
List<Integer> second = new ArrayList<>();
for (int j = 0; j < n; ++j) {
int a = 0, b = 0;
if (colsum[j] == 2) {
a = b = 1;
upper--;
lower--;
} else if (colsum[j] == 1) {
if (upper > lower) {
upper--;
a = 1;
} else {
lower--;
b = 1;
}
}
if (upper < 0 || lower < 0) {
break;
}
first.add(a);
second.add(b);
}
return upper == 0 && lower == 0 ? List.of(first, second) : List.of();
}
}
python3 解法, 执行用时: 100 ms, 内存消耗: 22.4 MB, 提交时间: 2023-06-29 09:22:59
'''
贪心
'''
class Solution:
def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:
n = len(colsum)
ans = [[0] * n for _ in range(2)]
for j, v in enumerate(colsum):
if v == 2: # 列之和为2，则两个数都是1
ans[0][j] = ans[1][j] = 1
upper, lower = upper - 1, lower - 1
if v == 1: # 列之和为1
if upper > lower: # 第0行之和大于第二行之和，则给第一行对应元素赋1
upper -= 1
ans[0][j] = 1
else:
lower -= 1
ans[1][j] = 1
if upper < 0 or lower < 0: # 超出范围，不存在符合要求的
return []
return ans if lower == upper == 0 else []