X

LEETCODE 1253. Reconstruct a 2-Row Binary Matrix 解题思路分析

题目大意:

重构 2 行二进制矩阵

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

  • 矩阵是一个二进制矩阵,这意味着矩阵中的每个元素不是 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-解题思路分析/
Categories: leetcode
kwantong: