重构 2 行二进制矩阵

淡淡的烟草味﹌ 2021-06-22 15:35 310阅读 0赞

给你一个 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时，则先分配下为1，再分配上为1  
    无解的情形与解决方案：
    
     *  行元素之和（upper+lower）与列元素之和（∑colsum）不相等
     *  解决方案：一次循环，求出 ∑colsum，与 upper+lower 比较行元素之和
     *  解决方案 1：排除所有 00 的项与 22 的项，观察此时 upper 与 lower 是否为负值
     *  解决方案 2：直接分配，分配完成后，观察此时 upper 与 lower 是否为负值

class Solution {
        List<List<Integer>> list = new ArrayList<>();
    
        public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
            int sum = 0;
            for (int col : colsum) {
                sum += col;
            }
            if (upper + lower != sum) {
                return list;
            }
            recursion(upper, lower, colsum, new Integer[2][colsum.length], 0);
            return list;
    
        }
    
        public void recursion(int upper, int lower, int[] colunm, Integer[][] res, int n) {
            if (n == colunm.length) {
                if (upper == 0 && lower == 0) {
                    List list1 = new ArrayList(n);
                    List list2 = new ArrayList(n);
                    Collections.addAll(list1, res[0]);
                    Collections.addAll(list2, res[1]);
                    list.add(list1);
                    list.add(list2);
                }
                return;
            }
            if (colunm[n] == 0) {
                res[0][n] = 0;
                res[1][n] = 0;
                recursion(upper, lower, colunm, res, n + 1);
                if (list.size() > 0) {
                    return;
                }
            } else if (colunm[n] == 2) {
                if (upper < 1 || lower < 1) {
                    return;
                }
                res[0][n] = 1;
                res[1][n] = 1;
                recursion(upper - 1, lower - 1, colunm, res, n + 1);
                if (list.size() > 0) {
                    return;
                }
            } else {
                if (upper > lower) {
                    if (upper > 0) {
                        res[0][n] = 1;
                        res[1][n] = 0;
                        recursion(upper - 1, lower, colunm, res, n + 1);
                        if (list.size() > 0) {
                            return;
                        }
                    } else if (lower > 0) {
                        res[0][n] = 0;
                        res[1][n] = 1;
                        recursion(upper, lower - 1, colunm, res, n + 1);
                        if (list.size() > 0) {
                            return;
                        }
                    }
                } else {
                    if (lower > 0) {
                        res[0][n] = 0;
                        res[1][n] = 1;
                        recursion(upper, lower - 1, colunm, res, n + 1);
                        if (list.size() > 0) {
                            return;
                        }
                    } else if (upper > 0) {
                        res[0][n] = 1;
                        res[1][n] = 0;
                        recursion(upper - 1, lower, colunm, res, n + 1);
                        if (list.size() > 0) {
                            return;
                        }
                    }
                }
            }
        }
    }