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

Elasticsearch:Serarch tutorial - 使用 Python 进行搜索 (一)
本实践教程将教你如何使用 Elasticsearch 构建完整的搜索解决方案。 在本教程中你将学习: 如何对数据集执行全文关键字搜索(可选使用过滤器)如何使用机器学习模型生成、存储和搜索密集向量嵌入如何使用 ELSER 模型生成和搜索稀疏向量如何使用…...
第五讲_css元素显示模式
css元素显示模式 1. 元素的显示模式1.1 块元素1.2 行内元素1.3 行内块元素 2. 元素根据显示模式分类3. 修改元素的显示模式 1. 元素的显示模式 1.1 块元素 块元素的特性: 在页面中独占一行,从上到下排列。默认宽度,撑满父元素。默认高度&a…...
Shell脚本入门实战:探索自动化任务与实用场景
引言 Shell脚本作为一种强大的自动化工具,在现代操作系统中具有广泛的应用。无论是简单的文件操作,还是复杂的系统管理,Shell脚本都能提供高效、快速的解决方案。在本文中,我们将探索Shell脚本的基础知识,并通过实战场…...

【AI视野·今日Sound 声学论文速览 第四十二期】Fri, 5 Jan 2024
AI视野今日CS.Sound 声学论文速览 Fri, 5 Jan 2024 Totally 10 papers 👉上期速览✈更多精彩请移步主页 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 是一个开源的嵌入式关系数据库,实现了自给自足的、无服务器的、配置无…...

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

数据结构第2章 栈和队列
名人说:莫听穿林打叶声,何妨吟啸且徐行。—— 苏轼《定风波莫听穿林打叶声》 本篇笔记整理:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 目录 0、思维导图栈和队列1、栈1)特点2࿰…...

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

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

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

23款奔驰GLC260L升级原厂540全景影像 安装效果分享
嗨 今天给大家介绍一台奔驰GLC260L升级原厂360全景影像 新款GLC升级原厂360全景影像 也只需要安装前面 左右三个摄像头 后面的那个还是正常用的,不过不一样的是 升级完成之后会有多了个功能 那就是新款透明底盘,星骏汇小许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种传播机制: PROPAGATION_REQUIRED:默认的Spring事物传播级别,若当前存在事务,则加入该事务,若不存在事务,则新建一个事务。 PAOPAGATION_REQUIRE_NEW:若当前没有事务&#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时失败,或者连接不上PLC,你可能需要做以下几点设置才可以。 一般来说每个PLC都有自己的IP地址,如果你的地址与PLC的地址冲突也就是地址重复是连接不上PLC的,如果地址没有冲突,但是不是在一个网段上也会导…...
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(Virtual Local Area Network)即虚拟局域网,是将一个物理的LAN在逻辑上划分成多个广播域的通信技术。VLAN内的主机间可以直接通信,而VLAN间不能直接互通,从而将广播报文限制在一个VLAN内。 VLAN 主要用来解决如何…...

登录验证
目录 会话技术 Cookie Session JWT JWT生成 JWT校验 会话技术 会话 打开浏览器,访问web服务器的资源,会话建立,直到有一方断开连接,会话结束。在一次会话中可以包含多次请求与响应 会话跟踪 一种维护浏览器的方法 服务器需要…...
利用Podman构建基于Fission env/builder的镜像
镜像准备 构建Dockerfile fission的基础环境包括两种:env 以及 builder。如果仅基于code构建function(i.e., 只创建deployachive),仅构建env即可;但如果需要构建sourcearchive,则需要同时创建env和builde…...

python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)
船舶制造装配管理现状:装配工作依赖人工经验,装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书,但在实际执行中,工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...

保姆级【快数学会Android端“动画“】+ 实现补间动画和逐帧动画!!!
目录 补间动画 1.创建资源文件夹 2.设置文件夹类型 3.创建.xml文件 4.样式设计 5.动画设置 6.动画的实现 内容拓展 7.在原基础上继续添加.xml文件 8.xml代码编写 (1)rotate_anim (2)scale_anim (3)translate_anim 9.MainActivity.java代码汇总 10.效果展示 逐帧…...
跨平台商品数据接口的标准化与规范化发展路径:淘宝京东拼多多的最新实践
在电商行业蓬勃发展的当下,多平台运营已成为众多商家的必然选择。然而,不同电商平台在商品数据接口方面存在差异,导致商家在跨平台运营时面临诸多挑战,如数据对接困难、运营效率低下、用户体验不一致等。跨平台商品数据接口的标准…...
iOS 项目怎么构建稳定性保障机制?一次系统性防错经验分享(含 KeyMob 工具应用)
崩溃、内存飙升、后台任务未释放、页面卡顿、日志丢失——稳定性问题,不一定会立刻崩,但一旦积累,就是“上线后救不回来的代价”。 稳定性保障不是某个工具的功能,而是一套贯穿开发、测试、上线全流程的“观测分析防范”机制。 …...

华为云Flexus+DeepSeek征文 | 基于Dify构建具备联网搜索能力的知识库问答助手
华为云FlexusDeepSeek征文 | 基于Dify构建具备联网搜索能力的知识库问答助手 一、构建知识库问答助手引言二、构建知识库问答助手环境2.1 基于FlexusX实例的Dify平台2.2 基于MaaS的模型API商用服务 三、构建知识库问答助手实战3.1 配置Dify环境3.2 创建知识库问答助手3.3 使用知…...

【靶场】XXE-Lab xxe漏洞
前言 学习xxe漏洞,搭了个XXE-Lab的靶场 一、搭建靶场 现在需要登录,不知道用户名密码,先随便试试抓包 二、判断是否存在xxe漏洞 1.首先登录抓包 看到xml数据解析,由此判断和xxe漏洞有关,但还不确定xxe漏洞是否存在。 2.尝试xxe 漏洞 判断是否存在xxe漏洞 A.send to …...

浅谈未来汽车电子电气架构发展趋势中的通信部分
目录 一、引入 1.1市场占比演化 1.2未来发展趋势 二、纯电动汽车与传统汽车的区别 2.1 纯电车和燃油车的架构(干货) 2.2 新能源汽车的分类 ⚡ 1. 纯电动汽车(BEV) 🔋 2. 插电式混合动力(PHEV&#…...