本文涉及知识点
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<
以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); } }
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
