当前位置: 首页 > 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;大多数应用程序在此…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...