【位运算】3097. 或值至少为 K 的最短子数组-阿里云开发者社区

【位运算】3097. 或值至少为 K 的最短子数组

2024-05-07 16

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【位运算】3097. 或值至少为 K 的最短子数组

本文涉及知识点

位运算

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<

以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++**实现。