南京响应式网站建设,一个网站用多个域名,做运营必看的网站,临海市建设局官网站【LetMeFly】1253.重构 2 行二进制矩阵
力扣题目链接#xff1a;https://leetcode.cn/problems/reconstruct-a-2-row-binary-matrix/
给你一个 2 行 n 列的二进制数组#xff1a;
矩阵是一个二进制矩阵#xff0c;这意味着矩阵中的每个元素不是 0 就是 1。第 0 行的元素之…【LetMeFly】1253.重构 2 行二进制矩阵
力扣题目链接https://leetcode.cn/problems/reconstruct-a-2-row-binary-matrix/
给你一个 2 行 n 列的二进制数组
矩阵是一个二进制矩阵这意味着矩阵中的每个元素不是 0 就是 1。第 0 行的元素之和为 upper。第 1 行的元素之和为 lower。第 i 列从 0 开始编号的元素之和为 colsum[i]colsum 是一个长度为 n 的整数数组。
你需要利用 upperlower 和 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^50 upper, lower colsum.length0 colsum[i] 2
方法一、方法二分配或贪心
首先
如果colsum[i]为0那么ans[0][i]和ans[1][i]必须为0如果colsum[i]为0那么ans[0][i]和ans[1][i]必须为1
因此问题的关键就在于colsum[i]为1时如何分配是令ans[0][i]为1还是ans[1][i]为1
有两种方法
对于所有colsum[i]为2的i令ans[0][i] ans[1][i] 1并统计upper和lower现在值为多少。接着对于colsum[i]为1的i如果upper还没达到就分配给ans[0][i]否则分配给ans[1][i]最终判断upper和lower是否同时满足统计upper和lower还分别缺少多少个当colsum[i]为2时lower和upper都分配当colsum[i]为1时分配给upper和lower中所需数量更大的那个
即可。
时间复杂度 O ( l e n ( c o l s u m ) ) O(len(colsum)) O(len(colsum))空间复杂度 O ( 1 ) O(1) O(1) 或 O ( l e n ( c o l s u m ) ) O(len(colsum)) O(len(colsum))所返回答案的不计入算法空间复杂度
AC代码
C
class Solution {
public:vectorvectorint reconstructMatrix(int upper, int lower, vectorint colsum) {vectorvectorint ans(2, vectorint(colsum.size(), 0));int cntUpper 0, cntLower 0;for (int i 0; i colsum.size(); i) {if (colsum[i] 2) {ans[0][i] ans[1][i] 1;cntUpper, cntLower;}}for (int i 0; i colsum.size(); i) {if (colsum[i] 1) {if (cntUpper upper) {ans[0][i] 1;cntUpper;}else {ans[1][i] 1;cntLower;}}}if (cntUpper upper cntLower lower) {return ans;}else {return {};}}
};Python
from typing import Listclass Solution:def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) - List[List[int]]:ans [[0] * len(colsum) for _ in range(2)]cntUpper, cntLower 0, 0for i in range(len(colsum)):if colsum[i] 2:ans[0][i] ans[1][i] 1cntUpper 1cntLower 1for i in range(len(colsum)):if colsum[i] 1:if cntUpper upper:ans[0][i] 1cntUpper 1else:ans[1][i] 1cntLower 1return ans if cntUpper upper and cntLower lower else []同步发文于CSDN原创不易转载请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/131448811
