【位运算】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 * 10⁵
0 <= nums[i] <= 10⁹
0 <= k <= 10⁹

位运算

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

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