当前位置: 首页 > news >正文

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就好了。
  • 技巧:递归

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. 被列覆盖的最多行数

通过万岁&#xff01;&#xff01;&#xff01; 题目&#xff1a;给你一个二维数组&#xff0c;然后里面是0和1&#xff0c;然后让你从里面选择numSelect列&#xff0c;使得去掉选择的列以后不存在1的行的数量最少。思路&#xff1a; 看到这个题目&#xff0c;本来以为是每一列…...

java通过HttpClient方式实现https请求的工具类(绕过证书验证)

目录 一、引入依赖包二、HttpClient方式实现的https请求工具类三、测试类 一、引入依赖包 引入相关依赖包 <!--lombok用于简化实体类开发--><dependency><groupId>org.projectlombok</groupId><artifactId>lombok</artifactId><option…...

【自学笔记】01Java基础-07面向对象基础-04接口与内部类详解

记录学习Java基础中有关接口类和内部类的知识。 1 接口 interface 关键字用于定义接口类&#xff0c;接口类是一系列方法的声明&#xff0c;一般只有方法的特征没有方法的实现&#xff0c;因此可以被不同的类接入实现&#xff0c;而这些实现可以具有不同的行为&#xff08;功…...

【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将输入文档按照指定的表达式和边界进行分组&#xff0c;每个分组为一个文档&#xff0c;称为“桶”&#xff0c;每个桶都有一个唯一的_id&#xff0c;其值为文件桶的下线。每个桶中至少要包含一个输入文档&#xff0c;也就是没有空桶。 使用 语法 {$bucket: {groupBy…...

从优化设计到智能制造:生成式AI在可持续性3D打印中的潜力和应用

可持续性是现代工业中一个紧迫的问题&#xff0c;包括 3D 打印领域。为了满足环保制造实践日益增长的需求&#xff0c;3D 打印已成为一种有前景的解决方案。然而&#xff0c;要使 3D 打印更具可持续性&#xff0c;还存在一些需要解决的挑战。生成式人工智能作为一股强大的力量&…...

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(数据操作语言)&#xff0c;用来对数据库中表的数据记录进行增、删、改操作。 添加数据&#xff08;INSERT&#xff09;修改数据…...

Web前端篇——ElementUI之el-scrollbar + el-backtop + el-timeline实现时间轴触底刷新和一键返回页面顶部

ElementUI之el-scrollbar el-backtop el-timeline实现时间轴触底刷新和一键返回页面顶部。 背景&#xff1a;ElementUI的版本&#xff08;vue.global.js 3.2.36&#xff0c; index.css 2.4.4&#xff0c; index.full.js 2.4.4&#xff09; 废话不多说&#xff0c;先看动…...

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 常用进阶指令

我是南城余&#xff01;阿里云开发者平台专家博士证书获得者&#xff01; 欢迎关注我的博客&#xff01;一同成长&#xff01; 一名从事运维开发的worker&#xff0c;记录分享学习。 专注于AI&#xff0c;运维开发&#xff0c;windows Linux 系统领域的分享&#xff01; 其他…...

windows通过ssh连接Liunx服务器并实现上传下载文件

连接ssh 输入&#xff1a;ssh空格用户名ip地址&#xff0c;然后按Enter 有可能出现下图提示&#xff0c;输入yes 回车即可 输入 password &#xff0c;注意密码是不显示的&#xff0c;输入完&#xff0c;再按回车就行了 以上是端口默认22情况下ssh连接&#xff0c;有些公司它…...

【K8S 存储卷】K8S的存储卷+PV/PVC

目录 一、K8S的存储卷 1、概念&#xff1a; 2、挂载的方式&#xff1a; 2.1、emptyDir&#xff1a; 2.2、hostPath&#xff1a; 2.3、NFS共享存储&#xff1a; 二、PV和PVC&#xff1a; 1、概念 2、请求方式 3、静态请求流程图&#xff1a; 4、PV和PVC的生命周期 5、…...

工业智能网关如何保障数据通信安全

工业智能网关是组成工业物联网的重要设备&#xff0c;不仅可以起到数据交换、通信、边缘计算的功能&#xff0c;还可以发挥数据安全保障功能&#xff0c;保障工业物联网稳定、可持续。本篇就为大家简单介绍一下工业智能网关增强和确保数据通信安全的几种措施&#xff1a; 1、软…...

基于Springboot的课程答疑系统(有报告)。Javaee项目,springboot项目。

演示视频&#xff1a; 基于Springboot的课程答疑系统&#xff08;有报告&#xff09;。Javaee项目&#xff0c;springboot项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构&…...

操作系统 内存相关

0 内存 cpu和内存的关系 内存覆盖 内存的覆盖是一种在程序运行时将部分程序和数据分为固定区和覆盖区的技术。这种技术的主要目的是为了解决程序较大&#xff0c;无法一次性装入内存导致无法运行的问题。 具体来说&#xff0c;内存的覆盖技术将用户空间划分为以下两个部分&…...

【模拟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 的开源实时自动化平台&#xff0c;主要用于控制和自动化行业中的设备。该项目具有以下主要模块&#xff1a; 1. Core&#xff1a;核心模块&#xff0c;提供数据结构和算法实现。 2. Master&#xff1a;主设备模块&#xff0c;实现与从设备通信的接口。…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学&#xff1f;传统医学奠基期&#xff08;远古 - 17 世纪&#xff09;近代医学转型期&#xff08;17 世纪 - 19 世纪末&#xff09;​现代医学成熟期&#xff08;20世纪至今&#xff09; 中医的源远流长和一脉相承远古至…...

Kafka入门-生产者

生产者 生产者发送流程&#xff1a; 延迟时间为0ms时&#xff0c;也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于&#xff1a;异步发送不需要等待结果&#xff0c;同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...

C++实现分布式网络通信框架RPC(2)——rpc发布端

有了上篇文章的项目的基本知识的了解&#xff0c;现在我们就开始构建项目。 目录 一、构建工程目录 二、本地服务发布成RPC服务 2.1理解RPC发布 2.2实现 三、Mprpc框架的基础类设计 3.1框架的初始化类 MprpcApplication 代码实现 3.2读取配置文件类 MprpcConfig 代码实现…...