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:主设备模块,实现与从设备通信的接口。…...
未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
循环冗余码校验CRC码 算法步骤+详细实例计算
通信过程:(白话解释) 我们将原始待发送的消息称为 M M M,依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)(意思就是 G ( x ) G(x) G(x) 是已知的)࿰…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中,新增了一个本地验证码接口 /code,使用函数式路由(RouterFunction)和 Hutool 的 Circle…...
C++ 设计模式 《小明的奶茶加料风波》
👨🎓 模式名称:装饰器模式(Decorator Pattern) 👦 小明最近上线了校园奶茶配送功能,业务火爆,大家都在加料: 有的同学要加波霸 🟤,有的要加椰果…...
Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)
引言 工欲善其事,必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后,我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集,就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...
uniapp 小程序 学习(一)
利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 :开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置,将微信开发者工具放入到Hbuilder中, 打开后出现 如下 bug 解…...
抽象类和接口(全)
一、抽象类 1.概念:如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象,这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法,包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中,⼀个类如果被 abs…...
springboot 日志类切面,接口成功记录日志,失败不记录
springboot 日志类切面,接口成功记录日志,失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...
