当前位置: 首页 > news >正文

LeetCode 1253. 重构 2 行二进制矩阵

【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^5
  • 0 <= upper, lower <= colsum.length
  • 0 <= 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)

有两种方法:

  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是否同时满足
  2. 统计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:vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {vector<vector<int>> ans(2, vector<int>(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,原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/131448811

相关文章:

LeetCode 1253. 重构 2 行二进制矩阵

【LetMeFly】1253.重构 2 行二进制矩阵 力扣题目链接&#xff1a;https://leetcode.cn/problems/reconstruct-a-2-row-binary-matrix/ 给你一个 2 行 n 列的二进制数组&#xff1a; 矩阵是一个二进制矩阵&#xff0c;这意味着矩阵中的每个元素不是 0 就是 1。第 0 行的元素之…...

【八股】【C++】内存

这里写目录标题 内存空间分配new和delete原理C有几种newmalloc / free 与 new / delete区别malloc和free原理&#xff1f;delete和delete[]区别&#xff1f;C内存泄漏malloc申请的存储空间能用delete释放吗?malloc、calloc函数、realloc函数C中浅拷贝与深拷贝栈和队列的区别C里…...

数据库G等待

> db^Cgbasedbtpc:~$ dbaccess db10 -Database selected.> call insert_t();Routine executed.Elapsed time: 811.630 sec 磁盘逻辑日志,无BUF库> ^Cgbasedbtpc:~$ gbasedbtpc:~$ dbaccess db10 -Database selected.> call insert_t();Routine executed.Elapse…...

PCB封装设计指导(一)基础知识

PCB封装设计指导(一)基础知识 PCB封装是PCB设计的基础,也是PCB最关键的部件之一,尺寸需要非常准确且精确,关系到设计,生产加工,贴片等后续一系列的流程。 下面以Allegro为例介绍封装创建前的一些基础知识 1.各个psm文件代表什么 mechanical symbol 是.bsm Package sy…...

Flask框架之Restful--介绍--下载--基本使用

目录 Restful 概念 架构的主要原则 适用场景 协议 数据传输格式 url链接规则 HTTP请求方式 状态码 Restful的基本使用 介绍 优势 缺点 安装 基本使用 注意 Restful 概念 RESTful&#xff08;Representational State Transfer&#xff09;是一种用于设计网络应用…...

2023年上海市浦东新区网络安全管理员决赛理论题样题

目录 一、判断题 二、单选题 三、多选题 一、判断题 1.等保1.0至等保2.0从信息系统拓展为网络和信息系统。 正确 (1)保护对象改变 等保1.0保护的对象是信息系统,等保2.0增加为网络和信息系统,增加了云计算、大数据、工业控制系统、物联网、移动物联技术、网络基础…...

SQL语言的四大组成部分——DCL(数据控制语言)

1️⃣前言 SQL语言中的DCL&#xff08;Data Control Language&#xff09;是一组用于控制数据库用户访问权限的语言&#xff0c;主要包括GRANT、REVOKE、DENY等关键字。 文章目录 1️⃣前言2️⃣DCL语言3️⃣GRANT关键字4️⃣REVOKE关键字5️⃣DENY关键字6️⃣总结附&#xff1…...

ChatGPT新功能曝光:可记住用户信息、上传文件和工作区

&#x1f989; AI新闻 &#x1f680; ChatGPT新功能曝光&#xff1a;可记住用户信息、上传文件和工作区 摘要&#xff1a;一张神秘截图曝光了ChatGPT新功能&#xff0c;包括可记住用户信息的"My profile"、上传和管理文件的"My files"以及可以让AI使用不…...

【Unity编辑器扩展】(三)PSD转UGUI Prefab, 一键拼UI解放美术/程序(完结)

工具效果&#xff1a; 第一步&#xff0c;把psd图层转换为可编辑的节点树&#xff0c;并自动解析UI类型、自动绑定UI子元素&#xff1a; 第二步, 点击“生成UIForm"按钮生成UI预制体 (若有UI类型遗漏可在下拉菜单手动点选UI类型)&#xff1a; 验证一键生成UI效果: 书接上…...

SpringBoot开发Restful风格的接口实现CRUD功能

基于SpringBoot开发一个Restful接口 前言一、什么是SpringBoot&#xff1f;二、实战---基于SpringBoot开发一个Restful接口1.开发前的准备工作1.1 添加相关依赖 &#xff08;pom文件&#xff09; 1.2 创建相关数据库和表1.3 数据库配置文件 2.实战开发---代码逻辑2.1 实体类2.2…...

【Servlet学习三】实现一个内存版本的简易计算器~

目录 一、方式1&#xff1a;使用form表单的形式&#xff08;不推荐&#xff09; &#x1f308;1、前端代码&#xff1a;HTML文件 &#x1f308;2、后端代码&#xff1a;Calculator_form.java文件 &#x1f308;3、最终效果 二、方式2&#xff1a;使用ajax形式&#xff08;…...

Linux c语言获取本机网关 ip 地址

文章目录 前言一、获取本机网关 ip 地址1.1 代码示例1.2 代码详解介绍 二、使用Netlink套接字实时监控网络事件2.1 简介2.2 示例代码 前言 这篇文章写了获取本机的ip地址和子网掩码&#xff1a;Linux c语言获取本机 ip、子网掩码 一、获取本机网关 ip 地址 使用Netlink套接字…...

nginx部署本地项目如何让异地公网访问?服务器端口映射配置!

接触过IIS或apache的小伙伴们&#xff0c;对nginx是比较容易理解的&#xff0c;nginx有点类似&#xff0c;又有所差异&#xff0c;在选择使用时根据自己本地应用场景来部署使用即可。通过一些对比可能会更加清楚了解&#xff1a; 1.nginx是轻量级&#xff0c;比apache占用更少…...

云时代已至,新一代数据分析平台是如何实现的?

2023 年 5 月&#xff0c;由 Stackoverflow 发起的 2023 年度开发者调查数据显示&#xff0c;PostgreSQL 已经超越 MySQL 位居第一&#xff0c;成为开发人员首选。PostgreSQL 在国内的热度也越来越高。6 月 17 日&#xff0c;PostgreSQL 数据库技术峰会在成都顺利召开。本次大会…...

【C#】简单聊下Framework框架下的事务

框架用的多了&#xff0c;之前版本的事务都忘记了。本次简单聊下.net framework 4.8框架下本身的事务 目录 1、SqlClient2、TransactionScope3、引用 1、SqlClient 在 C# 中&#xff0c;使用 using 块可以方便地实现对资源的自动释放&#xff0c;但它不适用于实现事务处理。为…...

asyncPool并发执行请求函数

asyncPool应用场景 一个不太常见的极端场景&#xff0c;当我们为了某个操作需要发生异步请求的时候&#xff0c;等待所有异步请求都完成时进行某些操作。这个时候我们不在简简单单的发送 1 - 2 个请求而是 5 - 10个&#xff08;其实极端场景式 很多很多个请求&#xff0c;这个…...

Ubuntu 22.04上安装NFS服务

1、使用如下命令安装NFS服务端软件&#xff1a; # 在主机上运行以下命令 orangepiorangepi5:~$ sudo apt install nfs-server 2、在配置NFS时需要使用用户uid和组gid&#xff0c;可以使用id命令查看 # 在主机上运行id命令 orangepiorangepi5:~$ id uid1000(orangepi) gid100…...

数据结构--双链表

数据结构–双链表 单链表 VS 双链表 单链表&#xff1a;无法逆向检索&#xff0c;有时候不太方便 双链表&#xff1a;可进可退&#xff0c;存储密度更低一丢丢 双链表的定义 typedef struct DNode {ElemType data;struct DNode *prior, *next; }DNode, *DLinkList;双链表的初…...

javassist 动态修改 jar 包中 class

Javassist&#xff08;Java Programming Assistant&#xff09;是一个用于在运行时操作字节码的库&#xff0c;它可以用于动态修改和操作Java类。使用Javassist&#xff0c;可以通过修改现有的类或创建新的类来实现动态修改Jar包中的类。 下面是一个简单的示例&#xff0c;展示…...

什么是CC攻击?

CC攻击&#xff1a;DDOS(分布式拒绝服务攻击)的一种。黑客利用代理服务器或者控制的肉鸡&#xff0c;向目标web网页发送大量的请求&#xff0c;致使CPU处理不过来这么多的请求&#xff0c;长期处于100%的状态。造成通过该页面访问的端口堵塞&#xff0c;正常请求进不来。 怎么…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...

高考志愿填报管理系统---开发介绍

高考志愿填报管理系统是一款专为教育机构、学校和教师设计的学生信息管理和志愿填报辅助平台。系统基于Django框架开发&#xff0c;采用现代化的Web技术&#xff0c;为教育工作者提供高效、安全、便捷的学生管理解决方案。 ## &#x1f4cb; 系统概述 ### &#x1f3af; 系统定…...

篇章二 论坛系统——系统设计

目录 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 1. 数据库设计 1.1 数据库名: forum db 1.2 表的设计 1.3 编写SQL 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 通过需求分析获得概念类并结合业务实现过程中的技术需要&#x…...