OR 至少 K II 的最短子数组

3097。 OR 至少 K II 的最短子数组

难度：中等

主题：数组、位操作、滑动窗口

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

如果一个数组的所有元素按位或至少 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 5
• 0 9
• 0 9

提示：

1. 对于每个nums[i]，我们可以维护以它结尾的每个子数组的按位或结果。
2. 按位或的特性是它永远不会取消设置任何位，而只会设置新位
3. 因此每个 nums[i] 的不同结果数最多为 32 位。

解决方案：

我们可以使用滑动窗口方法结合位操作来跟踪窗口中元素的 OR。

计划：

1. 滑动窗口方法：使用两个指针迭代数组，维护一个检查 OR 值的子数组。
2. 按位或：OR 运算累加值。它永远不会减少结果（即，一旦某个位设置为 1，就无法取消设置）。这意味着当我们扩展窗口时，OR 值只会增加或保持不变。
3. 效率：我们可以使用deque（双端队列）来维护子数组的索引。这使我们能够有效地滑动窗口，同时跟踪最小子数组长度。

步骤：

1. 遍历数组，对于每个元素，维护一个运行的OR。
2. 对于每个元素，检查 OR 是否超过或等于 k。如果是这样，请尝试从左侧缩小窗口。
3. 应该通过跟踪双端队列结构中的 OR 值来有效地移动滑动窗口，以允许恒定时间滑动和收缩。

让我们用 PHP 实现这个解决方案：3097。 OR 至少 K II 的最短子数组

<?php
class Solution {
    const K_MAX_BIT = 30; // Maximum bit position we will check

    /**
     * @param Integer[] $nums
     * @param Integer $k
     * @return Integer
     */
    function minimumSubarrayLength($nums, $k) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * @param $ors
     * @param $num
     * @param $count
     * @return int
     */
    private function orNum($ors, $num, &$count) {
        // Update the ors value and count bits that are set
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * @param $ors
     * @param $num
     * @param $count
     * @return int
     */
    private function undoOrNum($ors, $num, &$count) {
        // Reverse the update on ors and count bits that are reset
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}

// Example usage
$solution = new Solution();
$nums1 = [1, 2, 3];
$k1 = 2;
echo $solution->minimumSubarrayLength($nums1, $k1) . "\n"; // Output: 1

$nums2 = [2, 1, 8];
$k2 = 10;
echo $solution->minimumSubarrayLength($nums2, $k2) . "\n"; // Output: 3

$nums3 = [1, 2];
$k3 = 0;
echo $solution->minimumSubarrayLength($nums3, $k3) . "\n"; // Output: 1
?>

解释：

1. 最小子数组长度方法:

   • 将 ans 初始化为不可能的高值 ($n 1)。
   • 使用两个指针l（左）和r（右）来扩大和缩小窗口。
   • 在扩展窗口时使用 orNum 计算子数组的 OR，在缩小窗口时使用 undoOrNum 计算子数组的 OR。
   • 每当OR结果满足或超过k时，检查当前窗口大小是否小于ans。

2. orNum 和 undoOrNum 方法:

   • orNum 方法：通过更新计数数组将位添加到累积 OR 中。如果在窗口中新设置了一位（意味着 count[i] 变为 1），则该位将添加到 ors 中。
   • undoOrNum 方法：向左滑动窗口时，从累积 OR 中删除位。如果窗口中的任何数字中不再设置某个位（意味着 count[i] 变为 0），则该位将从 ors 中删除。

3. 时间复杂度:

   • 时间复杂度为 O(n)，因为每个索引最多在双端队列中添加和删除一次。
   • n 是输入数组的长度。

4*时间复杂度*:

• 存储前缀OR数组和双端队列的空间复杂度为O(n)。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

1. 子数组：子数组是数组中连续的非空元素序列。 ↩

以上是OR 至少 K II 的最短子数组的详细内容。更多信息请关注PHP中文网其他相关文章！