1253.重构2行二进制矩阵

链接：1253.重构2行二进制矩阵
难度：Medium
标签：贪心、数组、矩阵
简介：给你一个 2 行 n 列的二进制数组。你需要利用 upper，lower 和 colsum 来重构这个矩阵，并以二维整数数组的形式返回它。

题解 1 - cpp

• 编辑时间：2023-06-29
• 执行用时：56ms
• 内存消耗：60.9MB
• 编程语言：cpp
• 解法介绍：贪心，先填充2的列，再依次填充1的列。

class Solution {
public:
    vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
        int n = colsum.size();
        vector<int> list1(n, 0), list2(n, 0);
        for (int i = 0; i < n; i++) {
            if (colsum[i] == 2) {
                list1[i] = list2[i] = 1;
                if (upper <= 0 || lower <= 0) return {};
                upper -= 1;
                lower -= 1;
            }
        }
        for (int i = 0; i < n; i++) {
            if (colsum[i] == 1) {
                if (upper > 0) {
                    list1[i] = 1;
                    upper--;
                } else if (lower > 0) {
                    list2[i] = 1;
                    lower--;
                } else {
                    return {};
                }
            }
        }
        if (upper > 0 || lower > 0) return {};
        return { list1, list2 };
    }
};

题解 2 - python

• 编辑时间：2023-06-29
• 执行用时：132ms
• 内存消耗：22.5MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:
        n = len(colsum)
        list1 = [0 for _ in range(n)]
        list2 = [0 for _ in range(n)]
        for i in range(n):
            if colsum[i] == 2:
                list1[i] = list2[i] = 1
                if upper <= 0 or lower <= 0:
                    return []
                upper -= 1
                lower -= 1
        for i in range(n):
            if colsum[i] == 1:
                if upper > 0:
                    list1[i] = 1
                    upper -= 1
                elif lower > 0:
                    list2[i] = 1
                    lower -= 1
                else:
                    return []
        return [list1, list2] if upper == 0 and lower == 0 else []

题解 3 - rust

• 编辑时间：2023-06-29
• 执行用时：28ms
• 内存消耗：3.6MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn reconstruct_matrix(mut upper: i32, mut lower: i32, colsum: Vec<i32>) -> Vec<Vec<i32>> {
        let n = colsum.len();
        let mut list1 = vec![0; n];
        let mut list2 = vec![0; n];
        for i in 0..n {
            if colsum[i] == 2 {
                list1[i] = 1;
                list2[i] = 1;
                if upper <= 0 || lower <= 0 {
                    return vec![];
                }
                upper -= 1;
                lower -= 1;
            }
        }
        for i in 0..n {
            if colsum[i] == 1 {
                if upper > 0 {
                    list1[i] = 1;
                    upper -= 1;
                } else if lower > 0 {
                    list2[i] = 1;
                    lower -= 1;
                } else {
                    return vec![];
                }
            }
        }
        if upper > 0 || lower > 0 {
            vec![]
        } else {
            vec![list1, list2]
        }
    }
}