有flash的网站,北京门户网站制作费用,网站描述在哪里写,小说网站开发成本Leetcode 3097. Shortest Subarray With OR at Least K II 1. 解题思路2. 代码实现 题目链接#xff1a;3097. Shortest Subarray With OR at Least K II
1. 解题思路
这一题是题目3095的一个进阶版本#xff0c;但也就是增加了序列的复杂度而已#xff0c;要求我们能够在…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 ) O(N) O(N)的算法复杂度内完成而已。
一个直接的思路就是滑动窗口我们只需要不断地维护一个滑动窗口即可逐步移动左边界 i i i然后维护右边界 j j j使得滑动窗口内的或值始终大于等于 k k k即可。
唯一需要注意的是由于或操作有叠加效果因此我们需要记录每一个位上出现的 1 1 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 n1dk 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 [xy 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 ! n1 else -1 提交代码评测得到耗时3221ms占用内存38MB。
