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

acm网站免费做最新新闻热点事件

news 2026/4/8 21:26:47

acm网站免费做,最新新闻热点事件,怎样查看网站是用什么cms_做的,商务网页设计与制作软件本文涉及知识点拆位法贪心位运算决策包容性位运算、状态压缩、子集状态压缩汇总 LeetCode2871. 将数组分割成最多数目的子数组给你一个只包含非负整数的数组 nums 。我们定义满足 l < r 的子数组 nums[l…r] 的分数为 nums[l] AND nums[l 1] AND … AND nums[r…

本文涉及知识点

拆位法贪心位运算决策包容性
位运算、状态压缩、子集状态压缩汇总

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

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛