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

【拆位法 决策包容性 位运算】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 )的简单介绍

想象一下&#xff0c;你正指挥着一支超级英雄团队&#xff0c;面对蜂拥而至的敌人&#xff08;任务&#xff09;&#xff0c;不是每次都召唤新英雄&#xff08;创建线程&#xff09;&#xff0c;而是精心调配现有成员&#xff0c;高效应对。这就是Java线程池的魔力&#xff0c;…...

鸿蒙内核源码分析(时间管理篇) | 谁是内核基本时间单位

时间概念太重要了&#xff0c;在鸿蒙内核又是如何管理和使用时间的呢? 时间管理以系统时钟 g_sysClock 为基础&#xff0c;给应用程序提供所有和时间有关的服务。 用户以秒、毫秒为单位计时.操作系统以Tick为单位计时&#xff0c;这个认识很重要. 每秒的tick大小很大程度上决…...

安装numpy遇到的问题

安装numpy的时候提示无法安装如下&#xff1a; (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可以了解下&#xff0c;uiotos.net&#xff0c;通过连线来代替脚本逻辑开发&#xff0c;复杂的交互界面&#xff0c;通过页面嵌套轻松解决&#xff0c;是个很新颖的思路&#xff0c;前端零代码&#xff01; 蓝图连线尤其是独创的页面嵌套和属性继承技术&#xff0c;好家…...

上传文件至linux服务器失败

目录 前言异常排查使用df -h命令查看磁盘使用情况使用du -h --max-depth1命令查找占用空间最大的文件夹 原因解决补充&#xff1a;删除文件后&#xff0c;磁盘空间无法得到释放 前言 使用XFTP工具上传文件至CentOS服务器失败 异常 排查 使用df -h命令查看磁盘使用情况 发现磁盘…...

渗透 如何防御ARP欺骗,LLMNR-MDNS-NBNS等协议的作用

一. 如何防御ARP欺骗&#xff1f; 1.使用双向IP/MAC绑定&#xff1b; 2.使用静态ARP缓存表&#xff1b; 3.使用ARP服务器&#xff0c;通过服务器来查找ARP转换表来响应其他机器的广播&#xff1b; 4.使用ARP欺骗防护软件&#xff1b; 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 标准模板库&#xff08;STL&#xff09;提供了一系列常用的容器&#…...

Django调用SECRET_KEY对数据进行加密

对数据进行加密 在Django中进行加密可以直接调用django配置文件中的SECRET_KEY , 同时还需要导入itsdangerous模块中的TimedJSONWebSignatureSerializer进行加密 1. 实现加密方法 , 生成用户加密链接 # 生成用户加密链接 def generate_verify_email_url(user):# 调研加密方法…...

芸众商城电商专业版400+插件源码+搭建教程

介绍&#xff1a; 芸众商城社交电商系统SAAS平台前端基于vue开发&#xff0c;后端基于研发积分商城系统源码 php&#xff0c;本文安装芸众商城全插件&#xff08;400多个&#xff09;商业版平台源码&#xff0c;可同时支持多端口部署运行&#xff1b;使用宝塔面板一键部署的形…...

【机器学习与实现】线性回归示例——波士顿房价分析

目录 一、创建Pandas对象并查看数据的基本情况二、使用皮尔逊相关系数分析特征之间的相关性三、可视化不同特征与因变量MEDV&#xff08;房价中值&#xff09;间的相关性四、划分训练集和测试集并进行回归分析 一、创建Pandas对象并查看数据的基本情况 boston.csv数据集下载&a…...

Redis核心数据结构——跳表(生成数据到文件和从文件中读取数据、模块合并、)

生成文件和从文件中读取数据。 需求如下&#xff1a; 你的任务是实现 SkipList 类中的数据持久化成员函数和数据加载成员函数。 持久化数据成员函数签名&#xff1a;void dump_file(); 该成员函数负责将存储引擎内的数据持久化到文件中。数据的持久化格式是将每个键值对写入文…...

微信小程序下载文件详解

在微信小程序中&#xff0c;下载文件通常涉及使用 wx.downloadFile API。这个 API 可以将网络资源下载到本地临时文件路径&#xff0c;然后你可以使用 wx.saveFile 将临时文件保存到本地持久存储位置。下面是一个下载文件的详细过程&#xff1a; 使用 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…...

四川易点慧电子商务抖音小店:潜力无限的新零售风口

在当今数字化浪潮中&#xff0c;电子商务已经成为推动经济发展的重要引擎。四川易点慧电子商务有限公司凭借其敏锐的市场洞察力和创新精神&#xff0c;成功在抖音小店这一新兴平台上开辟出一片新天地。本文将探讨四川易点慧电子商务抖音小店的潜力及其在新零售领域的影响力。 一…...

Seal^_^【送书活动第3期】——《Hadoop大数据分析技术》

Seal^_^【送书活动第3期】——《Hadoop大数据分析技术》 一、参与方式二、作者荐语三、图书简介四、本期推荐图书4.1 前 言4.2 本书内容4.3 本书目的4.4 本书适合的读者4.5 配套源码、PPT课件等资源下载 五、目 录六、&#x1f6d2; 链接直达 Hadoop框架入门书&#xff0c;可当…...

win10下,svn上传.so文件失败

问题&#xff1a;win10下使用TortoiseSVN&#xff0c;svn上传.so文件失败 解决&#xff1a;右键&#xff0c;选择Settings&#xff0c;Global ignore pattern中删除*.so&#xff0c;保存即可。...

ubuntu20安装colmap

系统环境 ubuntu20 &#xff0c;cuda11.8 &#xff0c;也安装了anaconda。因为根据colmap的官方文档说的&#xff0c;如果根据apt-get安装的话&#xff0c;默认是非cuda版本的&#xff0c;而我觉得既然都安装了cuda11.8了&#xff0c;自然也要安装cuda版本的colmap。 安装步骤…...

kubeflow简单记录

kubeflow 13.7k star 1、Training Operator 包括PytorchJob和XGboostJob&#xff0c;支持部署pytorch的分布式训练 2、KFServing快捷的部署推理服务 3、Jupyter Notebook 基于Web的交互式工具 4、Katib做超参数优化 5、Pipeline 基于Argo Workflow提供机器学习流程的创建、编排…...

ARM的工作模式

ARM处理器设计有七种工作模式&#xff0c;这些模式允许处理器在不同的情境下以不同的权限级别执行任务&#xff0c;下面是这七大工作模式的概述&#xff1a; 用户模式&#xff08;User&#xff0c;USR&#xff09;&#xff1a; 这是非特权模式&#xff0c;大多数应用程序在此…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing

Muffin 论文 现有方法 CRADLE 和 LEMON&#xff0c;依赖模型推理阶段输出进行差分测试&#xff0c;但在训练阶段是不可行的&#xff0c;因为训练阶段直到最后才有固定输出&#xff0c;中间过程是不断变化的。API 库覆盖低&#xff0c;因为各个 API 都是在各种具体场景下使用。…...

Linux基础开发工具——vim工具

文章目录 vim工具什么是vimvim的多模式和使用vim的基础模式vim的三种基础模式三种模式的初步了解 常用模式的详细讲解插入模式命令模式模式转化光标的移动文本的编辑 底行模式替换模式视图模式总结 使用vim的小技巧vim的配置(了解) vim工具 本文章仍然是继续讲解Linux系统下的…...

Spring AI中使用ChatMemory实现会话记忆功能

文章目录 1、需求2、ChatMemory中消息的存储位置3、实现步骤1、引入依赖2、配置Spring AI3、配置chatmemory4、java层传递conversaionId 4、验证5、完整代码6、参考文档 1、需求 我们知道大型语言模型 &#xff08;LLM&#xff09; 是无状态的&#xff0c;这就意味着他们不会保…...