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

2024.1.4力扣每日一题——被列覆盖的最多行数

2024.1.4

      • 题目来源
      • 我的题解
        • 方法一 回溯+位运算优化

题目来源

力扣每日一题;题序:2397

我的题解

方法一 回溯+位运算优化

这道题一看就会想到使用回溯法,但是采用回溯法后如何判断有多少行被覆盖,直接计算矩阵时间复杂度较高,因此可以将0-1矩阵的每一行抽象为一个整数R,以及将选中列形成的整数L,然后根据位运算计算 R^L 是否等于R本身,若等于本身则表示该行被覆盖,然后在回溯过程中更新最终结果

时间复杂度:O(m× 2 n 2^n 2n)
空间复杂度:O(m)。矩阵的行转换为整数需要的空间

int ans = 0;public int maximumRows(int[][] matrix, int numSelect) {int m = matrix.length, n = matrix[0].length;if (n <= numSelect) return m;int[] nums = new int[m];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (matrix[i][j] == 1) nums[i] |= 1 << j;}}backTrace(n - 1, m, nums, numSelect);return ans;
}public void backTrace(int n, int m, int[] nums, int numSelect) {// 当给定的列数选完或者矩阵的列遍历完,更新结果if (n < 0 || numSelect == 0) {int c = 0;//计算覆盖的行数for (int num : nums) if (num == 0) c++;ans = Math.max(ans, c);return;}//不选择第n列 并缩小列的范围backTrace(n - 1, m, nums, numSelect);// modify表示选中的列的二进制数对应的整数int modify = 0, index = 0;//把对应列上的1去除for (int i = 0; i < m; i++) {if (((nums[i] >> n) & 1) == 1) {nums[i] ^= 1 << n;modify |= 1 << i;}} //选择第n列 并缩小列的范围backTrace(n - 1, m, nums, numSelect - 1);// 回退while (modify > 0 && index < m) {if ((modify & 1) == 1) {nums[index] |= 1 << n;}modify = modify >> 1;index++;}
}

有任何问题,欢迎评论区交流,欢迎评论区提供其它解题思路(代码),也可以点个赞支持一下作者哈😄~

相关文章:

2024.1.4力扣每日一题——被列覆盖的最多行数

2024.1.4 题目来源我的题解方法一 回溯位运算优化 题目来源 力扣每日一题&#xff1b;题序&#xff1a;2397 我的题解 方法一 回溯位运算优化 这道题一看就会想到使用回溯法&#xff0c;但是采用回溯法后如何判断有多少行被覆盖&#xff0c;直接计算矩阵时间复杂度较高&…...

Elasticsearch:Serarch tutorial - 使用 Python 进行搜索 (一)

本实践教程将教你如何使用 Elasticsearch 构建完整的搜索解决方案。 在本教程中你将学习&#xff1a; 如何对数据集执行全文关键字搜索&#xff08;可选使用过滤器&#xff09;如何使用机器学习模型生成、存储和搜索密集向量嵌入如何使用 ELSER 模型生成和搜索稀疏向量如何使用…...

第五讲_css元素显示模式

css元素显示模式 1. 元素的显示模式1.1 块元素1.2 行内元素1.3 行内块元素 2. 元素根据显示模式分类3. 修改元素的显示模式 1. 元素的显示模式 1.1 块元素 块元素的特性&#xff1a; 在页面中独占一行&#xff0c;从上到下排列。默认宽度&#xff0c;撑满父元素。默认高度&a…...

Shell脚本入门实战:探索自动化任务与实用场景

引言 Shell脚本作为一种强大的自动化工具&#xff0c;在现代操作系统中具有广泛的应用。无论是简单的文件操作&#xff0c;还是复杂的系统管理&#xff0c;Shell脚本都能提供高效、快速的解决方案。在本文中&#xff0c;我们将探索Shell脚本的基础知识&#xff0c;并通过实战场…...

【AI视野·今日Sound 声学论文速览 第四十二期】Fri, 5 Jan 2024

AI视野今日CS.Sound 声学论文速览 Fri, 5 Jan 2024 Totally 10 papers &#x1f449;上期速览✈更多精彩请移步主页 Daily Sound Papers PosCUDA: Position based Convolution for Unlearnable Audio Datasets Authors Vignesh Gokul, Shlomo Dubnov深度学习模型需要大量干净的…...

Java中如何使用SQLite数据库

目录 SQLite简介SQLite优势安装 SQLite基本使用Java使用SQLite Springboot使用SQLite1.添加依赖2.配置数据库3.创建实体类 4.创建Repository接口5.创建控制器6.运行应用程序 SQLite简介 SQLite 是一个开源的嵌入式关系数据库&#xff0c;实现了自给自足的、无服务器的、配置无…...

kettle的基本介绍和使用

1、 kettle概述 1.1 什么是kettle Kettle是一款开源的ETL工具&#xff0c;纯java编写&#xff0c;可以在Window、Linux、Unix上运行&#xff0c;绿色无需安装&#xff0c;数据抽取高效稳定。 1.2 Kettle核心知识点 1.2.1 Kettle工程存储方式 以XML形式存储以资源库方式存储…...

数据结构第2章 栈和队列

名人说&#xff1a;莫听穿林打叶声&#xff0c;何妨吟啸且徐行。—— 苏轼《定风波莫听穿林打叶声》 本篇笔记整理&#xff1a;Code_流苏(CSDN)&#xff08;一个喜欢古诗词和编程的Coder&#x1f60a;&#xff09; 目录 0、思维导图栈和队列1、栈1&#xff09;特点2&#xff0…...

Axure鲜花商城网站原型图,网上花店订花O2O本地生活电商平台

作品概况 页面数量&#xff1a;共 30 页 兼容软件&#xff1a;仅支持Axure RP 9/10&#xff0c;非程序软件无源代码 应用领域&#xff1a;鲜花网、花店网站、本地生活电商 作品特色 本作品为「鲜花购物商城」网站模板&#xff0c;高保真高交互&#xff0c;属于O2O本地生活电…...

【docker】centos 使用 Nexus Repository 搭建私有仓库

Nexus Repository 是一种流行的软件仓库管理工具&#xff0c;它可以帮助您搭建私有仓库&#xff0c;以便在内部网络或私有云环境中存储、管理和分发各种软件包和组件。 它常被用于搭建Maven的镜像仓库。本文演示如何用Nexus Repository搭建docker 私有仓库。 使用Nexus Repos…...

RabbitMQ(八)消息的序列化

目录 一、为什么需要消息序列化&#xff1f;二、常用的消息序列化方式1&#xff09;Java原生序列化&#xff08;默认&#xff09;2&#xff09;JSON格式3&#xff09;Protobuf 格式4&#xff09;Avro 格式5&#xff09;MessagePack 格式 三、总结 RabbitMQ 是一个强大的消息中间…...

23款奔驰GLC260L升级原厂540全景影像 安装效果分享

嗨 今天给大家介绍一台奔驰GLC260L升级原厂360全景影像 新款GLC升级原厂360全景影像 也只需要安装前面 左右三个摄像头 后面的那个还是正常用的&#xff0c;不过不一样的是 升级完成之后会有多了个功能 那就是新款透明底盘&#xff0c;星骏汇小许Xjh15863 左右两边只需要更换后…...

【CSS】文字描边的三种实现方式

目录 1. 可行的几种方式1.1. text-shadow 描边代码优缺点 1.2. text-stroke 描边实现优缺点 1.3. svg 描边实现优缺点 总结 1. 可行的几种方式 text-shadow–webkit-text-strokesvg 1.1. text-shadow 描边 MDN text-shadow 代码 <div class"text stroke">…...

【事务】事务传播级别

Spring事务定义了7种传播机制&#xff1a; PROPAGATION_REQUIRED&#xff1a;默认的Spring事物传播级别&#xff0c;若当前存在事务&#xff0c;则加入该事务&#xff0c;若不存在事务&#xff0c;则新建一个事务。 PAOPAGATION_REQUIRE_NEW&#xff1a;若当前没有事务&#x…...

Android WiFi 连接

Android WiFi 连接 1、设置中WiFi显示2、WiFi 连接流程2.1 获取PrimaryClientModeManager2.2 ClientModeImpl状态机ConnectableState2.3 ISupplicantStaNetworkCallback 回调监听 3、 简要时序图4、原生低层驱动5、关键日志 1、设置中WiFi显示 Android WiFi基础概览 packages/a…...

PLC与上位机PN通讯时,如何防止连接失败?

连接西门子PLC时失败&#xff0c;或者连接不上PLC&#xff0c;你可能需要做以下几点设置才可以。 一般来说每个PLC都有自己的IP地址&#xff0c;如果你的地址与PLC的地址冲突也就是地址重复是连接不上PLC的&#xff0c;如果地址没有冲突&#xff0c;但是不是在一个网段上也会导…...

LDD学习笔记 -- Linux错误码

LDD学习笔记 -- Linux错误码 EACCES(Permission Denied) 13EEXIST(File Exits) 17EINVAL(Invalid Argument) 22ENOENT(No Such File or Directory)ENOMEM(Out of Memory)EIO(Input/Output Error) 5ENOSPC(No space Left on Device)ENOTTY(Not a Typewrite)EPIPE(Broken Pipe)EI…...

华为交换机入门(六):VLAN的配置

VLAN&#xff08;Virtual Local Area Network&#xff09;即虚拟局域网&#xff0c;是将一个物理的LAN在逻辑上划分成多个广播域的通信技术。VLAN内的主机间可以直接通信&#xff0c;而VLAN间不能直接互通&#xff0c;从而将广播报文限制在一个VLAN内。 VLAN 主要用来解决如何…...

登录验证

目录 会话技术 Cookie Session JWT JWT生成 JWT校验 会话技术 会话 打开浏览器&#xff0c;访问web服务器的资源&#xff0c;会话建立&#xff0c;直到有一方断开连接&#xff0c;会话结束。在一次会话中可以包含多次请求与响应 会话跟踪 一种维护浏览器的方法 服务器需要…...

利用Podman构建基于Fission env/builder的镜像

镜像准备 构建Dockerfile fission的基础环境包括两种&#xff1a;env 以及 builder。如果仅基于code构建function&#xff08;i.e., 只创建deployachive&#xff09;&#xff0c;仅构建env即可&#xff1b;但如果需要构建sourcearchive&#xff0c;则需要同时创建env和builde…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...