【拆位法 决策包容性 位运算】2871. 将数组分割成最多数目的子数组
本文涉及知识点
拆位法 贪心 位运算 决策包容性
位运算、状态压缩、子集状态压缩汇总
LeetCode2871. 将数组分割成最多数目的子数组
给你一个只包含 非负 整数的数组 nums 。
我们定义满足 l <= r 的子数组 nums[l…r] 的分数为 nums[l] AND nums[l + 1] AND … AND nums[r] ,其中 AND 是按位与运算。
请你将数组分割成一个或者更多子数组,满足:
每个 元素都 只 属于一个子数组。
子数组分数之和尽可能 小 。
请你在满足以上要求的条件下,返回 最多 可以得到多少个子数组。
一个 子数组 是一个数组中一段连续的元素。
示例 1:
输入:nums = [1,0,2,0,1,2]
输出:3
解释:我们可以将数组分割成以下子数组:
- [1,0] 。子数组分数为 1 AND 0 = 0 。
- [2,0] 。子数组分数为 2 AND 0 = 0 。
- [1,2] 。子数组分数为 1 AND 2 = 0 。
分数之和为 0 + 0 + 0 = 0 ,是我们可以得到的最小分数之和。
在分数之和为 0 的前提下,最多可以将数组分割成 3 个子数组。所以返回 3 。
示例 2:
输入:nums = [5,7,1,3]
输出:1
解释:我们可以将数组分割成一个子数组:[5,7,1,3] ,分数为 1 ,这是可以得到的最小总分数。
在总分数为 1 的前提下,最多可以将数组分割成 1 个子数组。所以返回 1 。
提示:
1 <= nums.length <= 105
0 <= nums[i] <= 106
位运算、贪心
因为 x&y <= x+y ,所以只分成一个子数组,一定分数和最小。
拆位法,如果某个二进制位全部为1,则分成一个子数组,结果为1。分成两个或更大,结果一定大于1。
如果任何一个二进制位全部是1,则只能分成一个子数组。
如果所有二进制位不全为1,则结果一定为0。即所有子数组的分数必须为0。
决策包容性
假定nums[l…r1]积分为0,nums[l…r2]积分也为0,r1 < r2。那么选择nums[l…r1]。
假定后者:nums[l…r2] ,nums[r2+1…r3] ⋯ \cdots ⋯ 则nums[l…r1] ,nums[r1+1,r3] ⋯ \cdots ⋯也符合。x&y 的结果 不会大于x或y。
代码
核心代码
class Solution {
public:int maxSubarrays(vector<int>& nums) {int iRet = 0 ;int iAnd = -1;for (int i = 0; i < nums.size();i++ ) {iAnd &= nums[i];if (0 == iAnd) {iRet++;iAnd = -1;}}if (0 == iRet) { return 1; }return iRet ;}
};
测试用例
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){assert(v1[i] == v2[i]);}
}template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}int main()
{vector<int> nums;{Solution slu;nums = { 1,0,2,0,1,2 };auto res = slu.maxSubarrays(nums);Assert(3, res);}{Solution slu;nums = { 5,7,1,3 };auto res = slu.maxSubarrays(nums);Assert(1, res);}
}

扩展阅读
视频课程
有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
|---|
| 闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
| 子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙,那算法就是他的是睛 |
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

相关文章:
【拆位法 决策包容性 位运算】2871. 将数组分割成最多数目的子数组
本文涉及知识点 拆位法 贪心 位运算 决策包容性 位运算、状态压缩、子集状态压缩汇总 LeetCode2871. 将数组分割成最多数目的子数组 给你一个只包含 非负 整数的数组 nums 。 我们定义满足 l < r 的子数组 nums[l…r] 的分数为 nums[l] AND nums[l 1] AND … AND nums[r…...
Java 线程池 ( Thread Pool )的简单介绍
想象一下,你正指挥着一支超级英雄团队,面对蜂拥而至的敌人(任务),不是每次都召唤新英雄(创建线程),而是精心调配现有成员,高效应对。这就是Java线程池的魔力,…...
鸿蒙内核源码分析(时间管理篇) | 谁是内核基本时间单位
时间概念太重要了,在鸿蒙内核又是如何管理和使用时间的呢? 时间管理以系统时钟 g_sysClock 为基础,给应用程序提供所有和时间有关的服务。 用户以秒、毫秒为单位计时.操作系统以Tick为单位计时,这个认识很重要. 每秒的tick大小很大程度上决…...
安装numpy遇到的问题
安装numpy的时候提示无法安装如下: (venv) E:\works\AI\venv\Scripts>pip install numpy pandas matplotlib jupyter -i https://pypi.douban.com/simple Looking in indexes: https://pypi.douban.com/simple WARNING: Retrying (Retry(total4, connectNone, r…...
页面嵌套,界面套娃,除了用iframe,还有其他方式吗?
UIOTOS可以了解下,uiotos.net,通过连线来代替脚本逻辑开发,复杂的交互界面,通过页面嵌套轻松解决,是个很新颖的思路,前端零代码! 蓝图连线尤其是独创的页面嵌套和属性继承技术,好家…...
上传文件至linux服务器失败
目录 前言异常排查使用df -h命令查看磁盘使用情况使用du -h --max-depth1命令查找占用空间最大的文件夹 原因解决补充:删除文件后,磁盘空间无法得到释放 前言 使用XFTP工具上传文件至CentOS服务器失败 异常 排查 使用df -h命令查看磁盘使用情况 发现磁盘…...
渗透 如何防御ARP欺骗,LLMNR-MDNS-NBNS等协议的作用
一. 如何防御ARP欺骗? 1.使用双向IP/MAC绑定; 2.使用静态ARP缓存表; 3.使用ARP服务器,通过服务器来查找ARP转换表来响应其他机器的广播; 4.使用ARP欺骗防护软件; 5.在网关设备上部署防ARP欺骗攻击功能…...
【C++ 所有STL容器简介】
【C 所有STL容器简介】 1. vector2. list3. deque4. set / multiset5. map / multimap6. unordered_set / unordered_multiset7. unordered_map / unordered_multimap8. stack9. queue10. priority_queue C 标准模板库(STL)提供了一系列常用的容器&#…...
Django调用SECRET_KEY对数据进行加密
对数据进行加密 在Django中进行加密可以直接调用django配置文件中的SECRET_KEY , 同时还需要导入itsdangerous模块中的TimedJSONWebSignatureSerializer进行加密 1. 实现加密方法 , 生成用户加密链接 # 生成用户加密链接 def generate_verify_email_url(user):# 调研加密方法…...
芸众商城电商专业版400+插件源码+搭建教程
介绍: 芸众商城社交电商系统SAAS平台前端基于vue开发,后端基于研发积分商城系统源码 php,本文安装芸众商城全插件(400多个)商业版平台源码,可同时支持多端口部署运行;使用宝塔面板一键部署的形…...
【机器学习与实现】线性回归示例——波士顿房价分析
目录 一、创建Pandas对象并查看数据的基本情况二、使用皮尔逊相关系数分析特征之间的相关性三、可视化不同特征与因变量MEDV(房价中值)间的相关性四、划分训练集和测试集并进行回归分析 一、创建Pandas对象并查看数据的基本情况 boston.csv数据集下载&a…...
Redis核心数据结构——跳表(生成数据到文件和从文件中读取数据、模块合并、)
生成文件和从文件中读取数据。 需求如下: 你的任务是实现 SkipList 类中的数据持久化成员函数和数据加载成员函数。 持久化数据成员函数签名:void dump_file(); 该成员函数负责将存储引擎内的数据持久化到文件中。数据的持久化格式是将每个键值对写入文…...
微信小程序下载文件详解
在微信小程序中,下载文件通常涉及使用 wx.downloadFile API。这个 API 可以将网络资源下载到本地临时文件路径,然后你可以使用 wx.saveFile 将临时文件保存到本地持久存储位置。下面是一个下载文件的详细过程: 使用 wx.downloadFile 下载文件…...
2024 概率论和数理统计/专业考试/本科考研/论文/重点公式考点汇总
## 列表http://www.deepnlp.org/equation/category/statistics ## 均匀分布http://www.deepnlp.org/equation/uniform-distribution ## t-分布http://www.deepnlp.org/equation/student-t-distribution ## 伯努利分布http://www.deepnlp.org/equation/bernoulli-distributio…...
四川易点慧电子商务抖音小店:潜力无限的新零售风口
在当今数字化浪潮中,电子商务已经成为推动经济发展的重要引擎。四川易点慧电子商务有限公司凭借其敏锐的市场洞察力和创新精神,成功在抖音小店这一新兴平台上开辟出一片新天地。本文将探讨四川易点慧电子商务抖音小店的潜力及其在新零售领域的影响力。 一…...
Seal^_^【送书活动第3期】——《Hadoop大数据分析技术》
Seal^_^【送书活动第3期】——《Hadoop大数据分析技术》 一、参与方式二、作者荐语三、图书简介四、本期推荐图书4.1 前 言4.2 本书内容4.3 本书目的4.4 本书适合的读者4.5 配套源码、PPT课件等资源下载 五、目 录六、🛒 链接直达 Hadoop框架入门书,可当…...
win10下,svn上传.so文件失败
问题:win10下使用TortoiseSVN,svn上传.so文件失败 解决:右键,选择Settings,Global ignore pattern中删除*.so,保存即可。...
ubuntu20安装colmap
系统环境 ubuntu20 ,cuda11.8 ,也安装了anaconda。因为根据colmap的官方文档说的,如果根据apt-get安装的话,默认是非cuda版本的,而我觉得既然都安装了cuda11.8了,自然也要安装cuda版本的colmap。 安装步骤…...
kubeflow简单记录
kubeflow 13.7k star 1、Training Operator 包括PytorchJob和XGboostJob,支持部署pytorch的分布式训练 2、KFServing快捷的部署推理服务 3、Jupyter Notebook 基于Web的交互式工具 4、Katib做超参数优化 5、Pipeline 基于Argo Workflow提供机器学习流程的创建、编排…...
ARM的工作模式
ARM处理器设计有七种工作模式,这些模式允许处理器在不同的情境下以不同的权限级别执行任务,下面是这七大工作模式的概述: 用户模式(User,USR): 这是非特权模式,大多数应用程序在此…...
Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...
Unity中的transform.up
2025年6月8日,周日下午 在Unity中,transform.up是Transform组件的一个属性,表示游戏对象在世界空间中的“上”方向(Y轴正方向),且会随对象旋转动态变化。以下是关键点解析: 基本定义 transfor…...
AxureRP-Pro-Beta-Setup_114413.exe (6.0.0.2887)
Name:3ddown Serial:FiCGEezgdGoYILo8U/2MFyCWj0jZoJc/sziRRj2/ENvtEq7w1RH97k5MWctqVHA 注册用户名:Axure 序列号:8t3Yk/zu4cX601/seX6wBZgYRVj/lkC2PICCdO4sFKCCLx8mcCnccoylVb40lP...
React从基础入门到高级实战:React 实战项目 - 项目五:微前端与模块化架构
React 实战项目:微前端与模块化架构 欢迎来到 React 开发教程专栏 的第 30 篇!在前 29 篇文章中,我们从 React 的基础概念逐步深入到高级技巧,涵盖了组件设计、状态管理、路由配置、性能优化和企业级应用等核心内容。这一次&…...
aardio 自动识别验证码输入
技术尝试 上周在发学习日志时有网友提议“在网页上识别验证码”,于是尝试整合图像识别与网页自动化技术,完成了这套模拟登录流程。核心思路是:截图验证码→OCR识别→自动填充表单→提交并验证结果。 代码在这里 import soImage; import we…...
