【拆位法 决策包容性 位运算】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 <= 10⁵
0 <= nums[i] <= 10⁶

位运算、贪心

因为 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++**实现。