【C++前缀和 状态压缩】2588. 统计美丽子数组数目|1696
本文涉及的基础知识点
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
LeetCode2588. 统计美丽子数组数目
给你一个下标从 0 开始的整数数组nums 。每次操作中，你可以：
选择两个满足 0 <= i, j < nums.length 的不同下标 i 和 j 。
选择一个非负整数 k ，满足 nums[i] 和 nums[j] 在二进制下的第 k 位（下标编号从 0 开始）是 1 。
将 nums[i] 和 nums[j] 都减去 2k 。
如果一个子数组内执行上述操作若干次后，该子数组可以变成一个全为 0 的数组，那么我们称它是一个 美丽 的子数组。
请你返回数组 nums 中 美丽子数组 的数目。
子数组是一个数组中一段连续 非空 的元素序列。
示例 1：
输入：nums = [4,3,1,2,4]
输出：2
解释：nums 中有 2 个美丽子数组：[4,3,1,2,4] 和 [4,3,1,2,4] 。
- 按照下述步骤，我们可以将子数组 [3,1,2] 中所有元素变成 0 ：
- 选择 [3, 1, 2] 和 k = 1 。将 2 个数字都减去 21 ，子数组变成 [1, 1, 0] 。
- 选择 [1, 1, 0] 和 k = 0 。将 2 个数字都减去 20 ，子数组变成 [0, 0, 0] 。
- 按照下述步骤，我们可以将子数组 [4,3,1,2,4] 中所有元素变成 0 ：
- 选择 [4, 3, 1, 2, 4] 和 k = 2 。将 2 个数字都减去 22 ，子数组变成 [0, 3, 1, 2, 0] 。
- 选择 [0, 3, 1, 2, 0] 和 k = 0 。将 2 个数字都减去 20 ，子数组变成 [0, 2, 0, 2, 0] 。
- 选择 [0, 2, 0, 2, 0] 和 k = 1 。将 2 个数字都减去 21 ，子数组变成 [0, 0, 0, 0, 0] 。
示例 2：
输入：nums = [1,10,4]
输出：0
解释：nums 中没有任何美丽子数组。
提示：
1 <= nums.length <= 105
0 <= nums[i] <= 106
前缀和
preSum[k][i]记录 nums前i个元素第k位为1的数量。
某个子数组是美丽子数组
⟺
\iff
⟺ 此子数组各位1的数量为偶数。
以子数组nums[i…j-1]为例：
对于任意 k1
∈
\in
∈[0,20] 都符合preSum[k1][j] - preSum[k1][i]是偶数。
由于只关心奇偶性，所以preSum的中元素如果是偶数，用0代码；奇数用1表示。
我们将pre[0…20][i]进行状态压缩。用pre1[i]的第k位表示pre[k][i]。
代码
核心代码
class Solution {
public:
long long beautifulSubarrays(vector<int>& nums) {
vector<int> preSum(1);
for (const auto& n : nums) {
preSum.emplace_back(preSum.back() ^ n);
}
long long ret = 0;
unordered_map<int, int> cnt;
cnt[preSum.back()]++;
for (int i = nums.size() - 1; i >= 0; i--) {
ret += cnt[preSum[i]];
cnt[preSum[i]]++;
}
return ret;
}
};
单元测试
vector<int> nums;
TEST_METHOD(TestMethod11)
{
nums = { 4,3,1,2,4 };
auto res = Solution().beautifulSubarrays(nums);
AssertEx(2LL, res);
}
TEST_METHOD(TestMethod12)
{
nums = { 1,10,4 };
auto res = Solution().beautifulSubarrays(nums);
AssertEx(0LL, res);
}
扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
原文地址：https://blog.csdn.net/he_zhidan/article/details/141786055
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！