LeetCode——2397. 被列覆盖的最多行数
通过万岁!!!
- 题目:给你一个二维数组,然后里面是0和1,然后让你从里面选择numSelect列,使得去掉选择的列以后不存在1的行的数量最少。
- 思路:
- 看到这个题目,本来以为是每一列求和以后相加然后贪心就完了,但是发现是不对的。也没有更好的思路,就想着暴力一下吧。之前也做过类似的,就是找到所有的可能,找最优解。这里需要用到递归找到所有的可能,我们把所有的可能都记录在一个一维数组中,数组的长度等于给定的二位数组的列。然后如果我们选择在的数量等于numSelect的话,就进行计算行数就好了。然后就是如何递归构造一维数组,
- 首先是退出递归的条件:当选择完毕,也就是选择了numSelect个,或者剩余元素都选也达不到numSelect的时候就可以退出了。
- 然后是递归干的事情:递归需要在一维数组中加入一个点,但是记得要回退。
- 最后是入参:这个其实就根据自己用哪个就传哪个就好了,或者是弄成成员变量。
- 在递归的时候,我们需要通过for来不断的往数组中添加元素,为了不重复出现相同的情况,这个for的起始位置需要进行设定,每次递归这个for的起始位置都+1。并且将剩余元素达不到numSelect的退出条件写在for的判断中。
- 然后就是选择完以后如果统计结果,这里我使用了一个set,我们只需要遍历选择的列数组,统计不选择的列中行是1的行号,最后返回行数减去set的长度即可。其实这里不用set也可以,我们只需要遍历二维数组,如果存在1,并且没有被选中,则num+1,但是记得要退出列的循环,因为这一行只要有一个1就num+1就好了。
- 看到这个题目,本来以为是每一列求和以后相加然后贪心就完了,但是发现是不对的。也没有更好的思路,就想着暴力一下吧。之前也做过类似的,就是找到所有的可能,找最优解。这里需要用到递归找到所有的可能,我们把所有的可能都记录在一个一维数组中,数组的长度等于给定的二位数组的列。然后如果我们选择在的数量等于numSelect的话,就进行计算行数就好了。然后就是如何递归构造一维数组,
- 技巧:递归
java代码——使用set
class Solution {int n, m, max = Integer.MIN_VALUE;int[][] myMatrix;public int maximumRows(int[][] matrix, int numSelect) {myMatrix = matrix;n = matrix.length;m = matrix[0].length;int[] choice = new int[m];fun(choice, numSelect, 0);return max;}public void fun(int[] choice, int numSelect, int begin) {if (numSelect == 0) {max = Math.max(max, computerRowNum(choice));return;}for (int i = begin; i < m && numSelect <= m - i; i++) {if (choice[i] == 1) {continue;}choice[i] = 1;fun(choice, numSelect - 1, i + 1);choice[i] = 0;}}public int computerRowNum(int[] choice) {Set<Integer> existRow = new HashSet<>();// 不选的列中,那些行是1for (int i = 0; i < m; i++) {if (choice[i] == 0) {for (int j = 0; j < n; j++) {if (myMatrix[j][i] == 1) {existRow.add(j);}}}}return n - existRow.size();}
}
java代码——不使用set
class Solution {int n, m, max = Integer.MIN_VALUE;int[][] myMatrix;public int maximumRows(int[][] matrix, int numSelect) {myMatrix = matrix;n = matrix.length;m = matrix[0].length;int[] choice = new int[m];fun(choice, numSelect, 0);return max;}public void fun(int[] choice, int numSelect, int begin) {if (numSelect == 0) {max = Math.max(max, computerRowNum(choice));return;}for (int i = begin; i < m && numSelect <= m - i; i++) {if (choice[i] == 1) {continue;}choice[i] = 1;fun(choice, numSelect - 1, i + 1);choice[i] = 0;}}public int computerRowNum(int[] choice) {int num = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (myMatrix[i][j] == 1 && choice[j] == 0) {num++;break;}}}return n - num;}
}
- 总结:题目还是比较挺有意思的,而且递归的代码写出来以后确实给人一种赏心悦目的感觉。
相关文章:
LeetCode——2397. 被列覆盖的最多行数
通过万岁!!! 题目:给你一个二维数组,然后里面是0和1,然后让你从里面选择numSelect列,使得去掉选择的列以后不存在1的行的数量最少。思路: 看到这个题目,本来以为是每一列…...
java通过HttpClient方式实现https请求的工具类(绕过证书验证)
目录 一、引入依赖包二、HttpClient方式实现的https请求工具类三、测试类 一、引入依赖包 引入相关依赖包 <!--lombok用于简化实体类开发--><dependency><groupId>org.projectlombok</groupId><artifactId>lombok</artifactId><option…...
【自学笔记】01Java基础-07面向对象基础-04接口与内部类详解
记录学习Java基础中有关接口类和内部类的知识。 1 接口 interface 关键字用于定义接口类,接口类是一系列方法的声明,一般只有方法的特征没有方法的实现,因此可以被不同的类接入实现,而这些实现可以具有不同的行为(功…...
【cmu15445c++入门】(5)c++中的模板类
一、template模板类 除了模板方法【cmu15445c入门】(4)c中的模板方法 模板也可以用来实现类 二、代码 /*** file templated_classes.cpp* author Abigale Kim (abigalek)* brief Tutorial code for templated classes.*/// Includes std::cout (printing). #include <io…...
MongoDB聚合:$bucket
$bucket将输入文档按照指定的表达式和边界进行分组,每个分组为一个文档,称为“桶”,每个桶都有一个唯一的_id,其值为文件桶的下线。每个桶中至少要包含一个输入文档,也就是没有空桶。 使用 语法 {$bucket: {groupBy…...
从优化设计到智能制造:生成式AI在可持续性3D打印中的潜力和应用
可持续性是现代工业中一个紧迫的问题,包括 3D 打印领域。为了满足环保制造实践日益增长的需求,3D 打印已成为一种有前景的解决方案。然而,要使 3D 打印更具可持续性,还存在一些需要解决的挑战。生成式人工智能作为一股强大的力量&…...
vue3 响应式api中特殊的api
系列文章目录 TypeScript 从入门到进阶专栏 文章目录 系列文章目录一、shallowRef()二、triggerRef()三、customRef()四、shallowReactive()五、shallowReadonly()六、toRaw()七、markRaw()八、effectScope()九、getCurrentScope() 一、shallowRef() shallowRef()是一个新的响…...
【大厂算法面试冲刺班】day2:合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 递归 class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {if (l1 null) {return l2;}else if (l2 null) {return l1;}else if (l1.val < l2.…...
【JaveWeb教程】(19) MySQL数据库开发之 MySQL数据库操作-DML 详细代码示例讲解
目录 3. 数据库操作-DML3.1 增加(insert)3.2 修改(update)3.3 删除(delete)3.4 总结 3. 数据库操作-DML DML英文全称是Data Manipulation Language(数据操作语言),用来对数据库中表的数据记录进行增、删、改操作。 添加数据(INSERT)修改数据…...
Web前端篇——ElementUI之el-scrollbar + el-backtop + el-timeline实现时间轴触底刷新和一键返回页面顶部
ElementUI之el-scrollbar el-backtop el-timeline实现时间轴触底刷新和一键返回页面顶部。 背景:ElementUI的版本(vue.global.js 3.2.36, index.css 2.4.4, index.full.js 2.4.4) 废话不多说,先看动…...
CAS-ABA问题编码实战
多线程情况下演示AtomicStampedReference解决ABA问题 package com.nanjing.gulimall.zhouyimo.test;import java.util.concurrent.TimeUnit; import java.util.concurrent.atomic.AtomicInteger; import java.util.concurrent.atomic.AtomicStampedReference;/*** @author zho…...
Linux 常用进阶指令
我是南城余!阿里云开发者平台专家博士证书获得者! 欢迎关注我的博客!一同成长! 一名从事运维开发的worker,记录分享学习。 专注于AI,运维开发,windows Linux 系统领域的分享! 其他…...
windows通过ssh连接Liunx服务器并实现上传下载文件
连接ssh 输入:ssh空格用户名ip地址,然后按Enter 有可能出现下图提示,输入yes 回车即可 输入 password ,注意密码是不显示的,输入完,再按回车就行了 以上是端口默认22情况下ssh连接,有些公司它…...
【K8S 存储卷】K8S的存储卷+PV/PVC
目录 一、K8S的存储卷 1、概念: 2、挂载的方式: 2.1、emptyDir: 2.2、hostPath: 2.3、NFS共享存储: 二、PV和PVC: 1、概念 2、请求方式 3、静态请求流程图: 4、PV和PVC的生命周期 5、…...
工业智能网关如何保障数据通信安全
工业智能网关是组成工业物联网的重要设备,不仅可以起到数据交换、通信、边缘计算的功能,还可以发挥数据安全保障功能,保障工业物联网稳定、可持续。本篇就为大家简单介绍一下工业智能网关增强和确保数据通信安全的几种措施: 1、软…...
基于Springboot的课程答疑系统(有报告)。Javaee项目,springboot项目。
演示视频: 基于Springboot的课程答疑系统(有报告)。Javaee项目,springboot项目。 项目介绍: 采用M(model)V(view)C(controller)三层体系结构&…...
操作系统 内存相关
0 内存 cpu和内存的关系 内存覆盖 内存的覆盖是一种在程序运行时将部分程序和数据分为固定区和覆盖区的技术。这种技术的主要目的是为了解决程序较大,无法一次性装入内存导致无法运行的问题。 具体来说,内存的覆盖技术将用户空间划分为以下两个部分&…...
【模拟IC学习笔记】 PSS和Pnoise仿真
目录 PSS Engine Beat frequency Number of harmonics Accuracy Defaults Run tranisent?的3种设置 Pnoise type noise Timeaverage sampled(jitter) Edge Crossing Edge Delay Sampled Phase sample Ratio 离散时间网络(开关电容电路)的噪声仿真方法 PSS PSS…...
IPv6邻居发现协议(NDP)---路由发现
IPv6路由发现(前缀公告) 邻居发现 邻居发现协议NDP(Neighbor Discovery Protocol)是IPv6协议体系中一个重要的基础协议。邻居发现协议替代了IPv4的ARP(Address Resolution Protocol)和ICMP路由器发现(Router Discovery),它定义了使用ICMPv6报文实现地址解析,跟踪邻…...
OpenPLC v3 代码结构
OpenPLC v3 是一个基于 C 的开源实时自动化平台,主要用于控制和自动化行业中的设备。该项目具有以下主要模块: 1. Core:核心模块,提供数据结构和算法实现。 2. Master:主设备模块,实现与从设备通信的接口。…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...
Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
连锁超市冷库节能解决方案:如何实现超市降本增效
在连锁超市冷库运营中,高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术,实现年省电费15%-60%,且不改动原有装备、安装快捷、…...
如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用
文章目录 一、背景知识:什么是 B-Tree 和 BTree? B-Tree(平衡多路查找树) BTree(B-Tree 的变种) 二、结构对比:一张图看懂 三、为什么 MySQL InnoDB 选择 BTree? 1. 范围查询更快 2…...
tomcat入门
1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效,稳定,易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...
前端工具库lodash与lodash-es区别详解
lodash 和 lodash-es 是同一工具库的两个不同版本,核心功能完全一致,主要区别在于模块化格式和优化方式,适合不同的开发环境。以下是详细对比: 1. 模块化格式 lodash 使用 CommonJS 模块格式(require/module.exports&a…...
理想汽车5月交付40856辆,同比增长16.7%
6月1日,理想汽车官方宣布,5月交付新车40856辆,同比增长16.7%。截至2025年5月31日,理想汽车历史累计交付量为1301531辆。 官方表示,理想L系列智能焕新版在5月正式发布,全系产品力有显著的提升,每…...
ABB馈线保护 REJ601 BD446NN1XG
配电网基本量程数字继电器 REJ601是一种专用馈线保护继电器,用于保护一次和二次配电网络中的公用事业和工业电力系统。该继电器在一个单元中提供了保护和监控功能的优化组合,具有同类产品中最佳的性能和可用性。 REJ601是一种专用馈线保护继电器…...
