题目大意：
重构 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^5
- 0 <= upper, lower <= colsum.length
- 0 <= colsum[i] <= 2
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1253
解题思路分析：
我开始做这道题时想复杂了，dfs了所有情况，结果超时。然后加了memo数组，又不幸内存超了。。。
其实本题并没有那么难，简单来想一下，数组是2乘n的矩阵，如果当前列的和为0，说明此列上的两个数字一定是2个0，如果当前列的和为2，那么两个数字肯定都为1。关键在于列和是1的情况，这时要么是上1下0，要么是上0下1。至于能把1赋值给谁，取决于该行当前是否还有指标（指标就是题目给出的upper和lower）放下1。
因为列和为2的列必须是上1下1的方式，所以我们先循环一遍数组，当列和为2时，upper和lower的个数分别减一，代表此列上必须要分别放一个1。循环结束后，也就将所有的列和为2的部分删掉了，剩下的upper和lower是应该放在列和为1的部分。
再循环一遍数组，当列和为0时，向返回结果加入2个0，返回结果为2时，向返回结果加入两个1。当列和为1时，只要upper和lower哪个数大于0，就可以将1加入到哪一方（上1下0或下1上0）。加入后，相对应的upper或lower个数减一。
注意，在以上循环中，如果upper和lower都为0了，但是还有没加入的1时，代表无法满足条件，直接返回空list即可。另外，循环结束时，如果upper或lower还剩余，说明也无法找到合理解。
看下实现代码：
public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
Integer[][] res = new Integer[2][colsum.length]; // 构建一个2维数组
for(int sum : colsum){ // 循环colsum
if(sum==2){ // 列和为2时，upper和lower分别减一
// 如果upper或lower小于0，返回空list
if(--upper<0 || --lower<0){
return new ArrayList<>();
}
}
}
for(int i=0;i<colsum.length;i++){ // 循环colsum
int sum = colsum[i]; // 当前列和
if(sum==0){ // 列和为0
res[0][i]=0; // 当前列为上0下0
res[1][i]=0;
}else if(sum==2){ // 列和为2
res[0][i]=1; // 当前列为上1下1
res[1][i]=1;
}else{ // 列和为1
if(--upper>=0){ // 如果还有upper
res[0][i]=1; // 将1加入上行
res[1][i]=0;
}else if(--lower>=0){ // 如果还有lower
res[0][i]=0; // 将1加入下行
res[1][i]=1;
}else{ // upper和lower都没了，返回空list
return new ArrayList<>();
}
}
}
// 如果upper或lower还有剩余，返回空list
if(upper>0 || lower > 0){
return new ArrayList<>();
}
// 构造返回结果
List<List<Integer>> list = new ArrayList<>();
list.add(Arrays.asList(res[0]));
list.add(Arrays.asList(res[1]));
return list;
}本题解法执行时间为8ms。
Runtime: 8 ms, faster than 97.74% of Java online submissions for Reconstruct a 2-Row Binary Matrix.
Memory Usage: 53.2 MB, less than 100.00% of Java online submissions for Reconstruct a 2-Row Binary Matrix.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1253-reconstruct-a-2-row-binary-matrix-解题思路分析/