力扣2397.被列覆盖的最多行数,二进制枚举

借用评论区一位哥们的说法就是:假设有一个m*n的草坪,每块草坪分为有僵尸(1)和每僵尸(0)的情况,现在有numslect个竖排生效的火爆辣椒,问在哪几竖排使用火爆辣椒可以保住最多的小推车

思路:根据提示知道范围不大,可以暴力求解,首先将每一行的情况作为一个二进制数保存起来,例如:

如图所示,每位数的二进制位都对应则数组中一行的1和0分布情况,这样就可以使用一个一维数组来存储数组中的每行

那么该如何枚举所有情况呢?假设对应二进制为1则代表此列被选中,假设我们的数组有n列,那么只需要在1<<n之内遍历每个数,就可以列举出n列之内所有选中列的情况了

显然,这样穷举所有情况并不会或者说大多数时候选中的列数都不符合题目规定的要求,此时只需考虑选中列数 == 题目要求选中列数的情况,因为二进制位中为1则代表该列被选中,所以只需要判断该数二进制位1的个数是否等于题目要求就行了

__builtin_popcount()函数,功能为返回括号中的数的二进制位1的个数

那么就只剩最后一个问题,遍历每种情况时,如何判断当前情况被覆盖的行(该行没有僵尸即视为为被覆盖)的数量

假设使用了rows[]数组用二进制方式存储了数组的每一行,那么我们只需要逐个遍历rows[]中的数,并与当前遍历到的代表选中行的情况的数做对比,判断该行是否被覆盖就ok了,至于如何判断,只需要将rows[i]与代表当前选中情况的数做一个&运算然后再比较rows[i]是否发生变化就解决了

准备一个变量来记录当前被覆盖行数,再准备一个变量记录最大被覆盖行数然后返回即可

代码:

class Solution {
public:
    int maximumRows(vector<vector<int>>& matrix, int numSelect) {
        int col = matrix[0].size();    //数组列数
        int row = matrix.size();    //数组行数
        vector<int> rows(row,0);    //用二进制记录每行情况

        for(int i = 0; i < row; i++)    //记录每行情况
            for(int j = 0; j < col; j++){
                rows[i] <<= 1;    //先左移一位
                if(matrix[i][j]) rows[i] |= 1;    //如果要记录的值为1则|1,也就是对应二进制位赋1,否则为0
            }

        int maxrow = 0;    //记录最大被覆盖行数
        for(int cols = 1; cols < 1 << col; cols++){    //枚举每种情况
            if(__builtin_popcount(cols) == numSelect){    //只有满足题意的选中列数才计算
                int t = 0;    //存储当前情况的被覆盖行数
                for(int r : rows){    //遍历每行
                    t += (r & cols) == r;    //是否被覆盖
                }
                maxrow = max(maxrow,t);    //记录最大被覆盖行数
            }
        }

        return maxrow;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/293108.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Redis (三)

1、redis复制 简单的概括就是主从复制&#xff0c;master以写为主&#xff0c;Slave以读为主&#xff0c;当master数据发生变化的时候&#xff0c;自动将更新的数据异步同步到其他的slave是数据库。 使用这种机制的话&#xff0c;可以做到读写分离&#xff0c;可以减轻主机负担…

conda环境下Could not create share link解决方法

1 问题描述 在运行chatglm-6B项目时&#xff0c;运行python web_demo.py&#xff0c;出现如下错误&#xff1a; (chatglm) [rootlocalhost ChatGLM2-6B]# python web_demo.py Loading checkpoint shards: 100%|██████████████████████████████…

基于AOP实现权限管理系统demo

简介&#xff1a;本文将介绍如何使用面向切面编程&#xff08;AOP&#xff09;技术实现一个简单的权限管理系统demo。我们将使用ssm框架作为基础&#xff0c;通过AOP来拦截和处理权限相关的操作。主要实现拦截操作。&#xff08;如有需要&#xff0c;您可以自行从Gitee仓库中获…

上海亚商投顾:沪指探底回升跌 两市成交跌破7000亿

上海亚商投顾前言&#xff1a;无惧大盘涨跌&#xff0c;解密龙虎榜资金&#xff0c;跟踪一线游资和机构资金动向&#xff0c;识别短期热点和强势个股。 一.市场情绪 沪指昨日震荡调整&#xff0c;盘中一度跌超1%&#xff0c;尾盘跌幅有所收窄&#xff0c;创业板指录得3连阴。露…

5G工业物联网网关:连接未来的智能工业

在当今数字化时代&#xff0c;工业物联网正迅速崛起&#xff0c;并引领着全球工业的数字转型。而5G工业物联网网关作为实现IIoT的关键基础设施&#xff0c;在连接未来的智能工业中发挥着举足轻重的作用。 什么是5G工业物联网网关 5G工业物联网网关是连接工业设备和5G网络的关键…

<HarmonyOS第一课>1~10课后习题汇总

HarmonyOS第一课 1运行Hello World 判断题 main_pages.json存放页面page路径配置信息。&#xff08;正确&#xff09;DevEco Studio是开发HarmonyOS应用的一站式集成开发环境。&#xff08;正确&#xff09; 单选题 在stage模型中&#xff0c;下列配置文件属于AppScope文件…

2024年我国网络安全发展形势展望

2023年&#xff0c;我国网络安全政策法规陆续出台&#xff0c;网络安全与数据安全产业发展势头强劲&#xff0c;网络安全形势整体向好。展望2024年&#xff0c;世界各国在网络空间中的竞争将变得愈发激烈&#xff0c;我国网络安全领域的法律法规将不断完善&#xff0c;数据安全…

scratch给数据清单排序 2023年12月中国电子学会图形化编程 少儿编程 scratch编程等级考试四级真题和答案解析

目录 scratch给数据清单排序 一、题目要求 1、准备工作 2、功能实现 二、案例分析

MySQL数据库设置主键自增、自增主键为什么不能保证连续递增

文章目录 一、设置主键自增1.1、建表时设置主键自增1.2、建表后设置主键自增1.3、删除自增约束 二、自增列&#xff1a;AUTO_INCREMENT2.1、自增起始值和自增步长2.2、自增主键存储策略2.3、自增值修改机制2.3、特点和要求 三、自增字段值不连续3.1、自增不连续的示例3.1.1、示…

福建科立讯通信 指挥调度管理平台 多处文件上传漏洞复现

0x01 产品简介 福建科立讯通信指挥调度管理平台是一个专门针对通信行业的管理平台。该产品旨在提供高效的指挥调度和管理解决方案,以帮助通信运营商或相关机构实现更好的运营效率和服务质量。该平台提供强大的指挥调度功能,可以实时监控和管理通信网络设备、维护人员和工作任…

逻辑回归简单案例分析--鸢尾花数据集

文章目录 1. IRIS数据集介绍2. 具体步骤2.1 手动将数据转化为numpy矩阵2.1.1 从csv文件数据构建Numpy数据2.1.2 模型的搭建与训练2.1.3 分类器评估2.1.4 分类器的分类报告总结2.1.5 用交叉验证&#xff08;Cross Validation&#xff09;来验证分类器性能2.1.6 完整代码&#xf…

Kotlin/JS工程构建及编译运行到浏览器

概述 Kotlin/JS 提供了转换 Kotlin 代码、Kotlin 标准库的能力&#xff0c;并且兼容 JavaScript 的任何依赖项。Kotlin/JS 的当前实现以 ES5 为目标。 使用 Kotlin/JS 的推荐方法是通过 kotlin.multiplatform Gradle 插件。它提供了一种集中且便捷的方式来设置与控制以 JavaS…

激光焊接机:塑料产品制造中的革命性优势

随着科技的飞速发展&#xff0c;激光焊接机在塑料产品制造领域的应用越来越广泛。相较于传统的焊接技术&#xff0c;激光焊接机在塑料产品制造中展现出诸多优势&#xff0c;成为现代工业生产中不可或缺的一部分。 一、精确、高效的焊接性能 激光焊接机采用高能激光束作为焊接热…

【React系列】高阶组件

本文来自#React系列教程&#xff1a;https://mp.weixin.qq.com/mp/appmsgalbum?__bizMzg5MDAzNzkwNA&actiongetalbum&album_id1566025152667107329) 一. 高阶组件 1.1. 认识高阶组件 什么是高阶组件呢&#xff1f;相信很多同学都听说过&#xff0c;也用过 高阶函数&…

kafka消息队列安装以及整合springboot使用

文章目录 一、JMS与AMQP二、安装2.1 Java安装2.2 Zookeeper 和 kafka安装2.3 docker-compose 安装【待定&#xff0c;远程连接可能连接不上】 三、Kafka数据存储流程和原理概述和LEOHW讲解四、代码客户端连接kafka五、**ProducerRecord和key的作用**5.1 **如果保证顺序消费&…

C++使用map插入insert数据(二进制数据和非二进制数据)接口封装+读取文件

1、定义编写代码 //生成insert sql语句std::string GetInsertsql(XDATA kv, std::string table);//插入非二进制数据bool Insert(XDATA kv, std::string table);//插入二进制数据bool InsertBin(XDATA kv, std::string table); std::string LXMysql::GetInsertsql(XDATA kv, s…

【四】CocosCreator-修改引擎源码

看源码的过程中&#xff0c;少不了得修修改改源码&#xff0c;做点实验。果断去找找源码在哪里&#xff0c;然后就可以快乐动手改源码了。 CocosCreator引擎源码主要就是js和原生C两类&#xff0c;分别在引擎目录的resources/engine和resources/cocos2d-x下&#xff0c;如图&am…

5600U PVE安装WIN10后直通核显

修改PVE系统配置 请先安装相同版本的PVE系统&#xff0c;其他版本如果存在问题请自行查找。 安装过程比较简单&#xff0c;具体方法请自行百度 1. 修改grub启动参数&#xff1a; 修改文件 /etc/default/grub 中 GRUB_CMDLINE_LINUX_DEFAULT 配置&#xff1a; GRUB_CMDLINE_LI…

自制Java镜像发布到dockerhub公网使用

文章目录 问题现象解决制作Java镜像发布使用 问题现象 书接上回&#xff0c;上周处理了一个docker问题&#xff0c;写了篇博客&#xff1a;自定义docker镜像&#xff0c;ubuntu安装命令并导出我们使用谷歌的jib插件打包&#xff0c;详情可以参考这篇文章&#xff1a;Spring Bo…

【React系列】Redux(一)管理状态

本文来自#React系列教程&#xff1a;https://mp.weixin.qq.com/mp/appmsgalbum?__bizMzg5MDAzNzkwNA&actiongetalbum&album_id1566025152667107329) 在React的开发过程中&#xff0c;Redux对于我们是非常重要的。 但是对于很多人来说&#xff0c;初次接触redux会感觉r…