【算法】Reconstruct a 2-Row Binary Matrix 重构 2 行二进制矩阵-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法】Reconstruct a 2-Row Binary Matrix 重构 2 行二进制矩阵。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

问题描述：

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

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

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

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

$1 <= colsum.length <= 10^5\\ 0 <= upper, lower <= colsum.length\\ 0 <= colsum[i] <= 2$

$k, n u m s . l e n g t h 范围 [1, 16], n u m s . l e n g t h$

分析

目标是构建出一个2行的二进制数组，并且第一行的 $s u m 1 = u pp er$ ,第二行的 $s u m 2 = l o w er$ .并且2行相同位置的加和 $a rr 1 [i] + a rr 2 [i] == co l s u m [i]$ .

当然也可能无法构建符合给定条件的数组。

假设存在这样的目标数组arr，那么必须满足
第一个限制
$\sum_{0<=k<=n}(arr1[k]+arr2[k])= upper+lower.$

此外就要看数据是否能够分配合理，观察可以知道，当 $co l s u m [i] == 0 or 2$ ,可以确定 $a rr [i]$ 的数值，即同0，2.
所以另一个限制就是 $co l s u m$ 中 $2$ 出现的次数.
$cnt2<=\min(upper,lower).$

所以当上述2个条件都满足的情况下，是完全可以构造成功。

策略贪心

把 $u pp er ， l o w er$ 都减掉 $c n t 2$ ，即2出现的次数，剩余的就是各行1出现的次数。
所以当 $co l s u m [i] == 1$ ,可以先放行1，当 $u pp er$ 降低为0，就可以把剩余的都放入行2。

代码

class Solution {
    public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
        int n = colsum.length;
        int sum = 0, two = 0;
        for (int i = 0; i < n; ++i) {
            if (colsum[i] == 2) {
                ++two;
            }
            sum += colsum[i];
        }
        if (sum != upper + lower || Math.min(upper, lower) < two) {
            return new ArrayList<List<Integer>>();
        }
        upper -= two;
        lower -= two;
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        for (int i = 0; i < 2; ++i) {
            res.add(new ArrayList<Integer>());
        }
        for (int i = 0; i < n; ++i) {
            if (colsum[i] == 2) {
                res.get(0).add(1);
                res.get(1).add(1);
            } else if (colsum[i] == 1) {
                if (upper > 0) {
                    res.get(0).add(1);
                    res.get(1).add(0);
                    --upper;
                } else {
                    res.get(0).add(0);
                    res.get(1).add(1);
                }
            } else {
                res.get(0).add(0);
                res.get(1).add(0);
            }
        }
        return res;
    }
}