题目链接：https://leetcode-cn.com/contest/weekly-contest-162/problems/reconstruct-a-2-row-binary-matrix/
给你一个 2 行 n 列的二进制数组：
矩阵是一个二进制矩阵，这意味着矩阵中的每个元素不是 0 就是 1。
第 0 行的元素之和为 upper。
第 1 行的元素之和为 lower。
第 i 列（从 0 开始编号）的元素之和为 colsum[i]，colsum 是一个长度为 n 的整数数组。
你需要利用 upper，lower 和 colsum 来重构这个矩阵，并以二维整数数组的形式返回它。
如果有多个不同的答案，那么任意一个都可以通过本题。
如果不存在符合要求的答案，就请返回一个空的二维数组。
示例 1：
示例 2：
示例 3：
提示：
1 <= colsum.length <= 10^50 <= upper, lower <= colsum.length0 <= colsum[i] <= 2
题解
看了题目之后，我发现可以用回溯来做，然而并非如此。通过提示，我们可以看到数据是非常多的。达到了 \(10^5\)，这说明这种方法是会超时的。仔细读题目后，看到了新的关键字。如果有多个不同的答案，任意一个即可。
数组 colsum 是很特别的，它的和就是我们要得到的矩阵的所有数据的和。而 upper 和 lower 的和也是矩阵的和。
因此，可以先来统计一下 1 和 2 的个数。
如果数据是合法的。再依次将 0 或 1 添加到链表中即可。
Java代码
/**
* Description: Reconstruct a 2-Row Binary Matrix
* Author: wowpH
* Date: 2019-11-11 17:03:33
* From: https://www.cnblogs.com/wowpH/p/11836688.html
*/
class Solution {
public List<List<Integer>> reconstructMatrix(int upper,
int lower,
int[] colsum) {
int n = colsum.length;
List<List<Integer>> ret = new ArrayList<>();
// 统计1，2的个数
int one = 0, two = 0;
for (int i = 0; i < n; ++i) {
if (1 == colsum[i]) {
++one;
} else if (2 == colsum[i]) {
++two;
}
}
// 检查参数是否合法
if (one + (two << 1) != upper + lower) {
return ret;
}
// 提前去掉都是1的个数
upper -= two;
lower -= two;
if (upper < 0 || lower < 0) {
return ret;
}
// 添加0，1到链表中
List<Integer> list1 = new ArrayList<>();
List<Integer> list2 = new ArrayList<>();
for (int i = 0; i < n; ++i) {
if (0 == colsum[i]) {
// 都添加0
list1.add(0);
list2.add(0);
} else if (2 == colsum[i]) {
// 都添加1
list1.add(1);
list2.add(1);
} else {
// 1个0，1个1
if (upper > 0) {
// 链表1还可以添加1，优先满足链表1
list1.add(1);
list2.add(0);
--upper;
} else {
// 链表1已经不能添加1，向链表2添加1
list1.add(0);
list2.add(1);
--lower;
}
}
}
// 添加到结果链表中并返回结果
ret.add(list1);
ret.add(list2);
return ret;
}
}
原文链接：https://www.cnblogs.com/wowpH/p/11836688.html
- End -