LeetCode 1253. Reconstruct a 2-Row Binary Matrix【贪心,数组】中等

news/2024/10/31 7:35:18/

本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,还会用多种编程语言实现题解,涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件,我还建立了相关的仓库:https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中,你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等,还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解,还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动,欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

给你一个 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^5
  • 0 <= upper, lower <= colsum.length
  • 0 <= colsum[i] <= 2

解法 贪心

我们要求得任意一个 2 2 2 n n n 列的二进制数组(其中行和列的序号从 0 0 0 开始),满足数组中的每一个元素不是 0 0 0 就是 1 1 1 ,并且第 0 0 0 行的元素和为 upper \textit{upper} upper ,第 1 1 1 行的元素和为 lower \textit{lower} lower ,第 i i i 列的元素之和为 c o l s u m [ i ] colsum[i] colsum[i] ,若不存在直接返回一个空的二维数组即可。

s u m sum sum 为数组 c o l s u m colsum colsum 的元素和, t w o two two 为数组 c o l s u m colsum colsum 2 2 2 的个数。明显 s u m ≠ u p p e r + l o w e r sum≠upper+lower sum=upper+lower 时,一定不存在满足题意的矩阵。然后当第 i i i c o l s u m [ i ] = 2 colsum[i]=2 colsum[i]=2 时,第 i i i 列的两个元素只能都为 1 1 1 。那么如果 two > min ⁡ { upper , lower } \textit{two} > \min\{\textit{upper}, \textit{lower}\} two>min{upper,lower} 时,此时同样不存在满足题意的矩阵

否则,一定可以通过下述的方案,构造一个符合题目要求的矩阵。设结果矩阵为 ans [ 2 ] [ n ] \textit{ans}[2][n] ans[2][n] 。当第 i i i c o l s u m [ i ] colsum[i] colsum[i] 等于 0 0 0 或者 2 2 2 时只有一种情况:

  • c o l s u m [ i ] = 0 colsum[i]=0 colsum[i]=0 时: a n s [ 0 ] [ i ] = a n s [ 1 ] [ i ] = 0 ans[0][i]=ans[1][i]=0 ans[0][i]=ans[1][i]=0
  • c o l s u m [ i ] = 2 colsum[i]=2 colsum[i]=2 时: ans [ 0 ] [ i ] = ans [ 1 ] [ i ] = 1 \textit{ans}[0][i] = \textit{ans}[1][i] = 1 ans[0][i]=ans[1][i]=1

所以,现在只关注 c o l s u m [ i ] = 1 colsum[i]=1 colsum[i]=1 的情况。首先将初始的 upper \textit{upper} upper lower \textit{lower} lower 减去数组 c o l s u m colsum colsum 2 2 2 的个数 t w o two two相当于先贪心地处理 c o l s u m [ i ] = 2 colsum[i]=2 colsum[i]=2 的情况),那么现在 u p p e r + l o w e r upper+lower upper+lower 为数组 c o l s u m colsum colsum 1 1 1 的个数。那么从左到右遍历 c o l s u m colsum colsum 中的每一列,若第 i i i c o l s u m [ i ] colsum[i] colsum[i] 等于 1 1 1

  • u p p e r > 0 upper>0 upper>0 ,则我们在该列的第一行放置 1 1 1 ,第二行放置 0 0 0 a n s [ 0 ] [ i ] = 1 ans[0][i]=1 ans[0][i]=1 a n s [ 1 ] [ i ] = 0 ans[1][i]=0 ans[1][i]=0 ,并且 upper \textit{upper} upper 减一。
  • 否则在该列的第一行放置 0 0 0 ,第二行放置 1 1 1 a n s [ 0 ] [ i ] = 0 ans[0][i]=0 ans[0][i]=0 ans [ 1 ] [ i ] = 1 \textit{ans}[1][i] = 1 ans[1][i]=1

当遍历完成后,就得到了符合题目要求的矩阵 a n s [ 2 ] [ n ] ans[2][n] ans[2][n]

现在给出该方案的正确性证明:从上述的构造过程可得,整个数组中除了 1 1 1 0 0 0 ,每一列中 1 1 1 的个数完全符合数组 c o l s u m colsum colsum 描述,且在第一行中我们共放置了 u p p e r upper upper 1 1 1 ,第二行共放置了 lower \textit{lower} lower 1 1 1 。因此这样构造的矩阵 a n s [ 2 ] [ n ] ans[2][n] ans[2][n] 为满足题意的二进制矩阵,正确性得证。

下面是我写的先贪心处理 2 2 2 的情况的代码:

class Solution {
public:vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {int n = colsum.size();vector<vector<int>> ans(2, vector<int>(n)); for (int j = 0; j < n; ++j) {if (colsum[j] == 2) {if (!upper || !lower) return {}; // 不够组成列ans[0][j] = ans[1][j] = 1;--upper, --lower;}}for (int j = 0; j < n; ++j) { if (colsum[j] == 1) {if (!upper && !lower) return {}; // 不够组成列if (upper) ans[0][j] = 1, --upper;else ans[1][j] = 1, --lower;}} if (!lower && !upper) return ans;return {}; // 不够组成列   }
};

下面是先检查 c o l s u m colsum colsum 是否有解的代码:

class Solution {
public:vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {int n = colsum.size();vector<vector<int>> ans(2, vector<int>(n)); int sum = 0, two = 0; // two为colsum中2的个数for (int j = 0; j < n; ++j) {if (colsum[j] == 2) ++two; sum += colsum[j];}if (sum != upper + lower || min(upper, lower) < two) return {};upper -= two, lower -= two; // 相当于先处理2的情况for (int j = 0; j < n; ++j) { if (colsum[j] == 2) ans[0][j] = ans[1][j] = 1;else if (colsum[j] == 1) { if (upper) ans[0][j] = 1, --upper;else ans[1][j] = 1;}} return ans;}
};

复杂度分析:

  • 时间复杂度: O ( n ) O(n) O(n) ,其中 n n n 为数组 c o l s u m colsum colsum 的长度。
  • 空间复杂度: O ( 1 ) O(1) O(1) ,仅使用常量空间。返回的结果数组不计入空间开销。

http://www.ppmy.cn/news/460635.html

相关文章

python+adb 控制安卓手机拍照并传电脑

觉得USB摄像头拍照的效果太渣&#xff0c;特别是总有色差&#xff0c;也不会自动对焦等问题&#xff0c; 尝试研究运用手机摄像头拍照并传电脑&#xff0c;然后这几天接触了adb&#xff0c;最后顺利达成目标。 记录过程&#xff0c;代码在末尾&#xff1a; 1、安装 android s…

投屏后能在电脑操作手机吗 手机投屏电脑操作手机软件

网上找了很多投屏的软件&#xff0c;但是很多几乎只是投屏不能操作手机&#xff0c;有的很卡电脑上点一下要等好 久手机那边才能接收到&#xff0c;有的就是收费的一个月几十块。 但是我要的是电脑可以实时控制手机还可以一次控制多台手机不卡顿没延迟&#xff0c;主要还是要免…

手机拍照,浏览手机的文件夹,上传照片到服务器

利用J2ME中提供的可选包JSR75提供的功能&#xff0c;浏览手机的文件夹&#xff0c;并且将用户的照片上传到服务器&#xff0c;实现相册的功能。 完全实现了浏览手机的文件系统的功能。但是在浏览文件系统的时候&#xff0c;需要用户确认。我在使用Nokia6233的手机测试的时候&a…

电脑端如何访问手机SD卡中的文件

看到标题&#xff0c;估计各位看官有点懵&#xff0c;访问SD卡中的文件&#xff0c;你连上数据线不就行了&#xff0c;或者说你想要获取一些数据&#xff0c;你用及时通讯&#xff08;微信&#xff0c;钉钉&#xff0c;QQ等等&#xff09;&#xff0c;在线传输不就行了&#xf…

手机拍照保存raw图片,并导出手机拍摄的raw到本地电脑

1&#xff1a;安装adb工具&#xff0c;直接从百度网盘下载里面的两个文件 adb和run.sh脚本下载地址 提取码&#xff1a;mmew 2&#xff1a;其中platform-tools_r30.0.5-windows.zip&#xff0c;文件是adb的安装文件&#xff0c;只需要将其解压到一个特定的目录&#xff0c;比如…

电脑上与android手机文件互传

#在电脑上操作android手机目录文件 安装apk ./adb install *.apk 查看是否连接手机 ./adb devices 进入手机目录 ./adb shell 拷贝电脑文件 a.txt 到手机指定目录下 /data/local/manue/ ./adb push a.txt /data/local/manue/ 拷贝手机文件/data/local/manue/a.txt 到电脑里 ./…

手机访问电脑文件_彻底解决手机-电脑互传大文件的难题 电脑-手机快捷互联互通...

我们现在大多时候&#xff0c;手机和电脑传输数据都有用微信文件传输助手&#xff0c;或者QQ类型的功能。但是用这两个工具有2个问题&#xff0c;都是大于100M就不能传输了&#xff0c;而且传输图片的时候会进行压缩&#xff0c;即使你勾选了上传原图。所以我们需要找到更快捷方…

同样是处理器,为啥机器人不能直接用电脑和手机的CPU?

刚入行的小白&#xff0c;经常会发出这样的灵魂拷问——机器人可以直接用电脑和手机的CPU吗&#xff1f;本文将从生活事例引入&#xff0c;详细回答这个问题&#xff0c;并总结出机器人处理器的实际需求。 前阵子刷到一条有味道的新闻。 一台刚买来的扫地机器人&#xff0c;扫…