安全联盟可信任网站认证 网站,可信赖的手机网站建设,云服务器 部署网站,做仿网站的书本文涉及知识点
位运算、状态压缩、枚举子集汇总
LeetCode3209. 子数组按位与值为 K 的数目
给你一个整数数组 nums 和一个整数 k #xff0c;请你返回 nums 中有多少个子数组 满足#xff1a;子数组中所有元素按位 AND 的结果为 k 。 示例 1#xff1a; 输入#xff1a…本文涉及知识点
位运算、状态压缩、枚举子集汇总
LeetCode3209. 子数组按位与值为 K 的数目
给你一个整数数组 nums 和一个整数 k 请你返回 nums 中有多少个子数组 满足子数组中所有元素按位 AND 的结果为 k 。 示例 1 输入nums [1,1,1], k 1 输出6 解释 所有子数组都只含有元素 1 。 示例 2 输入nums [1,1,2], k 1 输出3 解释 按位 AND 值为 1 的子数组包括[1,1,2], [1,1,2], [1,1,2] 。 示例 3 输入nums [1,2,3], k 2 输出2 解释 按位 AND 值为 2 的子数组包括[1,2,3], [1,2,3] 。 提示 1 nums.length 105 0 nums[i], k 109
代码
核心代码
class CRangCal {
public:templateclass _Pr, class T intstatic vectorvectorpairT, int RangCal(const vectorT nums, _Pr pr) {vectorvectorpairint, int vNumIndex(nums.size());for (int i 0; i nums.size(); i) {if (i) {for (const auto [preNum, preIndex] : vNumIndex[i - 1]) {auto iNew pr(preNum, nums[i]);if (vNumIndex[i].empty() || (vNumIndex[i].back().first ! iNew)) {vNumIndex[i].emplace_back(make_pair(iNew, preIndex));}else {vNumIndex[i].back().second preIndex;}}}if (vNumIndex[i].empty() || (vNumIndex[i].back().first ! nums[i])) {vNumIndex[i].emplace_back(make_pair(nums[i], i));}else {vNumIndex[i].back().second i;}}return vNumIndex;}
};class Solution {public:long long countSubarrays(vectorint nums, int k) {auto res CRangCal::RangCal(nums, [](int n1, int n2) {return n1 n2; });long long ans 0;int i -1;for (const auto v : res) {i;for (int j 0; j v.size(); j) {if (v[j].first k) { const int begin (0 j) ? -1 : v[j - 1].second;ans (v[j].second-begin);}}}return ans;}};单元测试
vectorint nums;int k;TEST_METHOD(TestMethod11){nums { 1, 1, 1 }, k 1;auto res Solution().countSubarrays(nums, k);AssertEx(6LL, res);}TEST_METHOD(TestMethod12){nums { 1, 1, 2 }, k 1;auto res Solution().countSubarrays(nums, k);AssertEx(3LL, res);}TEST_METHOD(TestMethod13){nums { 1, 2, 3 }, k 2;auto res Solution().countSubarrays(nums, k);AssertEx(2LL, res);}扩展阅读
我想对大家说的话工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《
算法与数据汇总》。| 学习算法
按章节学习《喜缺全书算法册》大量
的题目和测试用例打包下载。重
视操作| 有效学习明确的目标 及时的反馈 拉伸区难度合适 专注 |闻缺陷则喜(喜缺)是一个美好的
愿望早发现问题早修改问题给老板节约钱。| | 子墨子言之事无终始无务多业。也就是我们
常说的专业的人做专业的事。 | |如果程序是一条龙那算法就是他的是睛| |失败反思成功 成功反
思成功|
视频课程
先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771 如何你
想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
测试环境
操作系
统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特
殊说明本算法用**C**实现。
