当前位置: 首页 > 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…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...