1253-重构 2 行二进制矩阵(Reconstruct a 2-Row Binary Matrix)

原文链接: https://leetcode-cn.com/problems/reconstruct-a-2-row-binary-matrix

英文原文

Given the following details of a matrix with n columns and 2 rows :

The matrix is a binary matrix, which means each element in the matrix can be 0 or 1.
The sum of elements of the 0-th(upper) row is given as upper.
The sum of elements of the 1-st(lower) row is given as lower.
The sum of elements in the i-th column(0-indexed) is colsum[i], where colsum is given as an integer array with length n.

Your task is to reconstruct the matrix with upper, lower and colsum.

Return it as a 2-D integer array.

If there are more than one valid solution, any of them will be accepted.

If no valid solution exists, return an empty 2-D array.

Example 1:

Input: upper = 2, lower = 1, colsum = [1,1,1]
Output: [[1,1,0],[0,0,1]]
Explanation: [[1,0,1],[0,1,0]], and [[0,1,1],[1,0,0]] are also correct answers.

Example 2:

Input: upper = 2, lower = 3, colsum = [2,2,1,1]
Output: []

Example 3:

Input: upper = 5, lower = 5, colsum = [2,1,2,0,1,0,1,2,0,1]
Output: [[1,1,1,0,1,0,0,1,0,0],[1,0,1,0,0,0,1,1,0,1]]

Constraints:

1 <= colsum.length <= 10^5
0 <= upper, lower <= colsum.length
0 <= colsum[i] <= 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

通过代码

高赞题解

一、题目分析

本题使用 DFS 求解，有 TLE 的可能
本题应使用贪心算法，大致思路为：
- 若 $colsum[i]=2$，则 一定上下均为 1
- 若 $colsum[i]=0$，则 一定上下均为 0
- 若 $colsum[i]=1$，则 上下一个 1 一个 0
- 唯一需要讨论的只有 $colsum[i]=1$ 的情形，我们可以规定：先分配上为 1，再分配下为 1
无解的情形与解决方案：
- 行元素之和（$upper+lower$）与列元素之和（$\sum colsum$）不相等
  - 解决方案：一次循环，求出 $\sum colsum$，与 $upper+lower$ 比较
- 行元素之和不够
  - 解决方案 1：排除所有 $0$ 的项与 $2$ 的项，观察此时 $upper$ 与 $lower$ 是否为负值
  - 解决方案 2：直接分配，分配完成后，观察此时 $upper$ 与 $lower$ 是否为负值

下面通过一个例子简单说明。

二、例子

例 1：$upper = 2, lower = 3, colsum = [2,2,1,1]$
- 分析：
  - $upper+lower=5$，$\sum colsum=6$，两者不相等，故无解
- 答案：$[]$
例 2：$upper = 5, lower = 5, colsum = [2,1,2,0,1,0,1,2,0,1]$
- 分析：
  - $upper+lower=10$，$\sum colsum=10$，故可能有解
  - 所有 $0$ 与 $2$ 的项排除掉，此时 $upper = 2, lower = 2, colsum = [1,1,1,1]$
  - $upper, lower$ 均大于 $0$，故一定有解。将 $colsum$ 的前两个 $1$ 用 $upper$，后两个 $1$ 用 $lower$ 即可
- 答案：$[[1,1,1,0,1,0,0,1,0,0],[1,0,1,0,0,0,1,1,0,1]]$
例 3：$upper = 9, lower = 2, colsum = [0,1,2,0,0,0,0,0,2,1,2,1,2]$
- 分析：
  - $upper+lower=11$，$\sum colsum=11$，故可能有解
  - 所有 $0$ 与 $2$ 的项排除掉，此时 $upper = 5, lower = -2, colsum = [1,1,1]$
  - $lower<0$，说明 $lower$ 不够分配，故无解
- 答案：$[]$

三、Coding

解决方案1的代码：

[-Java]
public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
    // up记录第0行可分配的1个数，lo记录第1行可分配的1个数
    int up = upper, lo = lower, sum = 0, len = colsum.length;
    List<List<Integer>> list = new ArrayList<>();
    for(int i = 0; i < len; i ++){
        if(colsum[i] == 2){
            up --;
            lo --;
        }
        else if(colsum[i] == 1){
            sum++;
        }
    }
    // 如果行列元素之和不相等，或行元素之和不够分配
    if(up + lo != sum || up < 0 || lo < 0){
        return list;
    }
    List<Integer> upl = new ArrayList<>();
    List<Integer> lol = new ArrayList<>();
    for(int i = 0; i < len; i ++){
        if(colsum[i] == 2){
            upl.add(1);
            lol.add(1);
        }
        else if(colsum[i] == 0){
            upl.add(0);
            lol.add(0);
        }
        else {
            // 先分配上
            if(up-- > 0){
                upl.add(1);
                lol.add(0);
            }
            // 再分配下
            else {
                lol.add(1);
                upl.add(0);
            }
        }
    }
    list.add(upl);
    list.add(lol);
    return list;
}

解决方案2的代码：

[-Java]
public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
    int sum = 0, len = colsum.length;
    List<List<Integer>> list = new ArrayList<>();
    for(int i = 0; i < len; i ++){
        sum += colsum[i];
    }
    // 如果行列元素之和不相等
    if(upper + lower != sum){
        return list;
    }
    List<Integer> upl = new ArrayList<>();
    List<Integer> lol = new ArrayList<>();
    for(int i = 0; i < len; i ++){
        if(colsum[i] == 2){
            upl.add(1);
            lol.add(1);
            upper --;
            lower --;
        }
        else if(colsum[i] == 0){
            upl.add(0);
            lol.add(0);
        }
        else {
            if(upper > lower){
                upl.add(1);
                lol.add(0);
                upper --;
            }
            else {
                lol.add(1);
                upl.add(0);
                lower --;
            }
        }
        // 如果行元素不够分配
        if(upper < 0 || lower < 0){
            return list;
        }
    }
    list.add(upl);
    list.add(lol);
    return list;
}

时间复杂度：$O(n)$，空间复杂度：$O(n)$

统计信息

通过次数	提交次数	AC比率
5438	13780	39.5%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途