1253. 重构 2 行二进制矩阵(力扣)

  • 题目
  • 第一种方式
    • 分析
    • 测试代码
    • 运行结果
  • 第二种方式
    • 测试代码
    • 运行结果

题目

给你一个 2 行 n 列的二进制数组:

矩阵是一个二进制矩阵,这意味着矩阵中的每个元素不是 0 就是 1。
第 0 行的元素之和为 upper。
第 1 行的元素之和为 lower。
第 i 列(从 0 开始编号)的元素之和为 colsum[i],colsum 是一个长度为 n 的整数数组。
你需要利用 upper,lower 和 colsum 来重构这个矩阵,并以二维整数数组的形式返回它。

如果有多个不同的答案,那么任意一个都可以通过本题。

如果不存在符合要求的答案,就请返回一个空的二维数组。

输入: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

第一种方式

分析

遍历到的元素colsum[i],我们有以下几种情况:
如果colsum[j]=2,那么我们将ans[0][j]和ans[1][j]都置为1。
如果colsum[j]=0,那么我们将ans[0][i]和ans[1][j]都置为0。
如果colsumli]= 1,先满足第一行为1,满足完后剩下的都是另一行的。

之后需要判断, 计算每一行的总和,看是否满足条件与upper和lower相等。

测试代码

class Solution {public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {int length=colsum.length;//声明数组,来表示两行length列int ans[][]=new int [2][length];int sum=0;//colsum为2那么当前列数字都为1,colsum为0当前列数字都为为0for (int i = 0; i <length ; i++) {if (colsum[i]==2){ans[0][i]=1;ans[1][i]=1;sum++;}else if (colsum[i]==0){ans[0][i]=0;ans[1][i]=0;}}//colsum为1的列先满足使第一行为1int count=upper-sum;for (int i = 0; i <length ; i++) {if (colsum[i]==1&&count>0){ans[0][i]=1;ans[1][i]=0;--count;}}//剩下colsum为1的列再使第二行为1for (int i = 0; i <length ; i++) {if (colsum[i]==1&&ans[0][i]!=1){ans[1][i]=1;ans[0][i]=0;}}List<Integer> list;List<List<Integer>> lists=new ArrayList<>();//计算每一行的总和,看是否满足条件int num1=0,num2=0;for (int i = 0; i <length ; i++) {num1+=ans[0][i];num2+=ans[1][i];}//不满足条件if (num2!=lower||num1!=upper){return lists;}//满足条件for (int i = 0; i <2 ; i++) {list=new ArrayList<>();for (int j = 0; j < length; j++) {list.add(ans[i][j]);}lists.add(list);}return lists;}}

运行结果

第二种方式

大致思想是一样的
这里是挨个,遍历元素colsum[i],我们有以下几种情况:
如果colsum[j]=2,那么我们将ans[0][j]和ans[1][j]都置为1,此时upper都lower 减去1。
如果colsum[j]=0,那么我们将ans[0][i]和ans[1][j]都置为0。
如果colsum[i]= 1,那么我们将ans[0][i]或ans[1][j]置为1。判断upper和lower谁大,谁就为1,此时upper或lower 减去1。
如果upper <0或lower <0,那么说明无法构造出满足要求的矩阵,跳出循环,遍历结束。

然后判断是否满足条件。

测试代码

class Solution {public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {int length = colsum.length;List<Integer> ans1 = new ArrayList<>();List<Integer> ans2 = new ArrayList<>();for (int j = 0; j < length; ++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;}ans1.add(a);ans2.add(b);}List<List<Integer>> lists = new ArrayList<>(); if (upper !=0 || lower !=0) {return lists;} else {lists.add(ans1);lists.add(ans2);return lists;}}}

运行结果