Leetcode 3097. Shortest Subarray With OR at Least K II

• Leetcode 3097. Shortest Subarray With OR at Least K II
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3097. Shortest Subarray With OR at Least K II

1. 解题思路

这一题是题目3095的一个进阶版本，但也就是增加了序列的复杂度而已，要求我们能够在$O(N)$的算法复杂度内完成而已。

一个直接的思路就是滑动窗口，我们只需要不断地维护一个滑动窗口即可，逐步移动左边界$i$，然后维护右边界$j$使得滑动窗口内的或值始终大于等于$k$即可。

唯一需要注意的是，由于或操作有叠加效果，因此我们需要记录每一个位上出现的$1$的总的次数，确保删除一个数之后依然可以准确获得后续所有值的或操作结果。

2. 代码实现

给出python代码实现如下：

class Solution:def minimumSubarrayLength(self, nums: List[int], k: int) -> int:def num2digit(num):ret = [0 for _ in range(32)]idx = 31while num > 0:ret[idx] = num % 2num = num // 2idx -= 1return retdef is_greater(digit1, digit2):for i in range(32):if digit1[i] > 0 and digit2[i] == 0:return Trueelif digit1[i] == 0 and digit2[i] > 0:return Falsereturn Truei, j, n = 0, 0, len(nums)ans = n+1dk = num2digit(k)digit = [0 for _ in range(32)]while i < n:while j < n and (j ==i or not is_greater(digit, dk)):dj = num2digit(nums[j])digit = [x+y for x, y in zip(digit, dj)]j += 1if is_greater(digit, dk):ans = min(ans, j-i)else:breakdi = num2digit(nums[i])digit = [x-y for x, y in zip(digit, di)]i += 1return ans if ans != n+1 else -1     

提交代码评测得到：耗时3221ms，占用内存38MB。