本文主要是介绍【位运算】3097. 或值至少为 K 的最短子数组 II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
本文涉及知识点
位运算
LeetCode3097. 或值至少为 K 的最短子数组 II
给你一个 非负 整数数组 nums 和一个整数 k 。
如果一个数组中所有元素的按位或运算 OR 的值 至少 为 k ,那么我们称这个数组是 特别的 。
请你返回 nums 中 最短特别非空 子数组
的长度,如果特别子数组不存在,那么返回 -1 。
示例 1:
输入:nums = [1,2,3], k = 2
输出:1
解释:
子数组 [3] 的按位 OR 值为 3 ,所以我们返回 1 。
示例 2:
输入:nums = [2,1,8], k = 10
输出:3
解释:
子数组 [2,1,8] 的按位 OR 值为 11 ,所以我们返回 3 。
示例 3:
输入:nums = [1,2], k = 0
输出:1
解释:
子数组 [1] 的按位 OR 值为 1 ,所以我们返回 1 。
提示:
1 <= nums.length <= 2 * 105
0 <= nums[i] <= 109
0 <= k <= 109
位运算
nums[l…x]的异或值,无论x有多少可能,其值最多log(iMax)种,如果值发生变化,至少加一个1,所有的二进制位变成1,就不会变化了。
队列index[i] 记录 升序记录所有( nums[x]&(1<<i)) 的x。
以j开始的子数组,只有结尾为x才方式变化。x 是index[i]中第一个大于j的元素。
代码
核心代码
class Solution {
public:int minimumSubarrayLength(vector<int>& nums, int k) {queue<int> index[31];for (int i = 0; i < nums.size(); i++){for (int j = 0; j <= 30; j++){const bool b = (1 << j) & nums[i];if (b) {index[j].emplace(i);}}}int iRet = nums.size() + 1;for (int i = 0; i < nums.size(); i++){ int cur = nums[i];if (cur >= k) { return 1; };set<int> setNext;for (int j = 0; j <= 30; j++){if (index[j].size()) {setNext.emplace(index[j].front());}}for (const auto& next : setNext) {cur |= nums[next];if (cur >= k) {iRet = min(iRet, next - i + 1);break;}}for (int j = 0; j <= 30; j++){if (index[j].size() && (index[j].front() == i)) {index[j].pop();}}}return (iRet>nums.size())?-1: iRet;}
};
使用模板
class Solution {
public:int minimumSubarrayLength(vector<int>& nums, int k) {//模板代码vector<vector<pair<int, int>>> vNumIndex(nums.size());for (int i = 0; i < nums.size(); i++) {if (i) {for (const auto& [preNum, preIndex] : vNumIndex[i - 1]) {const int iNew = 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;}}int iRet = INT_MAX;for (const auto& v : vNumIndex) {for (int i = 0; i < v.size(); i++) {if (v[v.size() - 1 - i].first >= k) {iRet = min(iRet, v.back().second - v[v.size() - 1 - i].second + 1);break;}}}return (INT_MAX == iRet) ? -1 : iRet;}
};
测试用例
template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}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]);}}int main()
{vector<int> nums;int k;{Solution sln;nums = { 1,2,32,21 }, k = 55;auto res = sln.minimumSubarrayLength(nums, k);Assert(3, res);}{Solution sln;nums = { 1, 2, 3 }, k = 2;auto res = sln.minimumSubarrayLength(nums, k);Assert(1, res);}{Solution sln;nums = { 2,1,8 }, k = 10;auto res = sln.minimumSubarrayLength(nums, k);Assert(3, res);}{Solution sln;nums = { 1,2 }, k = 0;auto res = sln.minimumSubarrayLength(nums, k);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++**实现。
这篇关于【位运算】3097. 或值至少为 K 的最短子数组 II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!