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:主设备模块,实现与从设备通信的接口。…...

测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...

Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
ip子接口配置及删除
配置永久生效的子接口,2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...

如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...

佰力博科技与您探讨热释电测量的几种方法
热释电的测量主要涉及热释电系数的测定,这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中,积分电荷法最为常用,其原理是通过测量在电容器上积累的热释电电荷,从而确定热释电系数…...
《C++ 模板》
目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板,就像一个模具,里面可以将不同类型的材料做成一个形状,其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式:templa…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖
在Vuzix M400 AR智能眼镜的助力下,卢森堡罗伯特舒曼医院(the Robert Schuman Hospitals, HRS)凭借在无菌制剂生产流程中引入增强现实技术(AR)创新项目,荣获了2024年6月7日由卢森堡医院药剂师协会࿰…...
CSS | transition 和 transform的用处和区别
省流总结: transform用于变换/变形,transition是动画控制器 transform 用来对元素进行变形,常见的操作如下,它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...