OR 至少 K II 的最短子数组-php教程-PHP中文网

OR 至少 K II 的最短子数组

Barbara Streisand

发布： 2024-11-19 13:10:03

原创

1003 人浏览过

Shortest Subarray With OR at Least 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。

约束：

提示：

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

解决方案：

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

计划：

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

步骤：

遍历数组，对于每个元素，维护一个运行的OR。
对于每个元素，检查 OR 是否超过或等于 k。如果是这样，请尝试从左侧缩小窗口。
应该通过跟踪双端队列结构中的 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
?>

登录后复制

解释：

最小子数组长度方法:
- 将 ans 初始化为不可能的高值 ($n 1)。
- 使用两个指针l（左）和r（右）来扩大和缩小窗口。
- 在扩展窗口时使用 orNum 计算子数组的 OR，在缩小窗口时使用 undoOrNum 计算子数组的 OR。
- 每当OR结果满足或超过k时，检查当前窗口大小是否小于ans。
orNum 和 undoOrNum 方法:
- orNum 方法：通过更新计数数组将位添加到累积 OR 中。如果在窗口中新设置了一位（意味着 count[i] 变为 1），则该位将添加到 ors 中。
- undoOrNum 方法：向左滑动窗口时，从累积 OR 中删除位。如果窗口中的任何数字中不再设置某个位（意味着 count[i] 变为 0），则该位将从 ors 中删除。
时间复杂度:
- 时间复杂度为 O(n)，因为每个索引最多在双端队列中添加和删除一次。
- n 是输入数组的长度。