Leetcode3095：或值至少 K 的最短子数组 I

题目描述：

给你一个 非负 整数数组 nums 和一个整数 k 。

如果一个数组中所有元素的按位或运算 OR 的值 至少 为 k ，那么我们称这个数组是 特别的 。

请你返回 nums 中 最短特别非空子数组的长度，如果特别子数组不存在，那么返回 -1 。

代码思路：

1. 检查k是否小于等于数组中的最大值：
   • 如果k小于等于nums中的最大值，直接返回1，因为单个元素就可以满足条件。
   • 这一步的逻辑是合理的，因为题目可能是要求找到至少有一个子数组其“某种特性”达到或超过k，而这里的“某种特性”在原始代码中并不明确（由于使用了位运算|，我们稍后会讨论）。
2. 遍历数组：
   • 遍历数组nums，以每个元素作为子数组的起始点。
   • 对于每个起始点，再次遍历从该起始点开始到数组末尾的所有可能子数组。
3. 计算子数组的“特性”：
   • 使用位运算|来累计子数组中所有元素的“或”结果。
   • 这意味着，如果我们要找的是子数组中至少有一个元素满足某种条件（例如，某个位上为1），这种方法是合理的。但是，如果目标是子数组的和或乘积等，这种方法则不适用。
4. 检查并存储满足条件的子数组长度：
   • 如果当前子数组的“特性”满足条件（即res >= k，这里的>=对于位运算来说可能不太直观，我们稍后讨论），则记录该子数组的长度。
   • 继续遍历直到找到所有可能的子数组或确定不存在满足条件的子数组。
5. 返回结果：
   • 如果存在满足条件的子数组，返回最短长度。
   • 如果不存在，返回-1。

代码实现：

class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        if k <= max(nums):
            return 1
        else:
            l_nums = len(nums)
            cnt = []
            for i in range(l_nums):
                res = nums[i]
                t_cnt = 1
                for j in range(i+1, l_nums):
                    res |= nums[j]
                    t_cnt += 1
                    if res >= k:
                        cnt.append(t_cnt)
                        break
                    else:
                        pass
            if cnt != []:
                return min(cnt)
            else:
                return -1

 

原文地址：https://blog.csdn.net/m0_67598823/article/details/145194835

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！