1. 題目

給你一個 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

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/reconstruct-a-2-row-binary-matrix
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 貪心解題

class Solution { public:vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {int i, n = colsum.size(), sum = 0;for(i = 0; i < n; ++i)sum += colsum[i];if(upper+lower != sum || upper > n || lower > n)return {}; //肯定可以排除的情況vector<vector<int>> ans(2, vector<int> (n,0));for(i = 0; i < n; ++i){if(colsum[i] == 0)continue;if(colsum[i] == 2){ans[0][i] = ans[1][i] = 1;upper--,lower--;}else// colsum[i] == 1，平均著分配（貪心）{ //優先分配多的，后面萬一有2，別一個多，一個少，少的不夠了if(lower >= upper){ans[1][i] = 1;lower--;}else{ans[0][i] = 1;upper--;}}if(lower < 0 || upper < 0)return {}; //不夠了，肯定錯了}return ans;} };

總結

以上是生活随笔為你收集整理的LeetCode 1253. 重构 2 行二进制矩阵（贪心）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。