少なくとも K II の OR を持つ最短のサブアレイ

3097。少なくとも K II

の OR を持つ最短のサブ配列

難易度: 中

トピック: 配列、ビット操作、スライディング ウィンドウ

非負の整数の配列 nums と整数 k が与えられます。

配列のすべての要素のビット単位の OR が 少なくとも k である場合、配列は 特別 と呼ばれます。

数値の空ではない最も短い特殊なサブ配列1^の長さを返します。特殊なサブ配列が存在しない場合は、-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 2 * 105
• ^{0 9}
• ^{0 9}

ヒント:

各 nums[i] について、それで終わる各部分配列のビットごとの OR 結果を維持できます。
ビットごとの OR の特性は、どのビットも設定解除されず、新しいビットのみを設定することです
したがって、各 nums[i] の異なる結果の数は最大でもビット数 32 です。

解決策:

ビット操作と組み合わせたスライディング ウィンドウ アプローチを使用して、ウィンドウ内の要素の OR を追跡できます。

プラン：

1. スライディング ウィンドウ アプローチ: OR 値がチェックされるサブ配列を維持しながら、2 つのポインターを使用して配列を反復処理します。
2. ビットごとの OR: OR 演算は値を累積します。結果が減少することはありません (つまり、ビットが 1 に設定されると、設定を解除することはできません)。これは、ウィンドウを拡張しても、OR 値は増加するか、同じままであることを意味します。
3. 効率: デキュー (両端キュー) を使用して、部分配列のインデックスを維持できます。これにより、サブ配列の最小長を追跡しながら、ウィンドウを効率的にスライドさせることができます。

手順:

1. 要素ごとに配列を走査し、実行中の OR を維持します。
2. 各要素について、OR が k を超えるか、k と等しいかどうかを確認します。その場合は、左側からウィンドウを縮小してみてください。
3. スライディング ウィンドウは、一定時間のスライドと縮小を可能にするために、deque 構造内の OR 値を追跡することによって効率的に移動する必要があります。

このソリューションを PHP で実装してみましょう: 3097。少なくとも K II
の OR を持つ最短のサブ配列

<?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. minimumSubarrayLength メソッド:

   • ans をありえない高い値 ($n 1) に初期化します。
   • 2 つのポインター l (左) と r (右) を使用して、ウィンドウを拡大または縮小します。
   • orNum を使用してウィンドウを拡大し、縮小する場合は undoOrNum を使用してウィンドウを縮小しながら、部分配列の OR を計算します。
   • OR の結果が k を満たすか超える場合は常に、現在のウィンドウ サイズが ans より小さいかどうかを確認します。

2. orNum メソッドと undoOrNum メソッド:

   • orNum メソッド: count 配列を更新することで、累積 OR にビットを追加します。ウィンドウにビットが新しく設定されると (つまり、count[i] が 1 になると)、そのビットが ors に追加されます。
   • undoOrNum メソッド: ウィンドウを左にスライドするときに累積 OR からビットを削除します。ウィンドウ内のどの数値にもビットが設定されなくなった場合 (つまり、count[i] が 0 になった場合)、そのビットは ors から削除されます。

3. 時間計算量:

   • 各インデックスは両端キューに追加され、両端キューから削除されるのは最大 1 回であるため、時間計算量は O(n) です。
   • n は入力配列の長さです。

4*時間計算量*:

• プレフィックス OR 配列と両端キューを格納する場合の空間複雑さは O(n) です。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

---

1. サブ配列 : サブ配列は、配列内の要素の連続した空でないシーケンスです。 ↩

以上が少なくとも K II の OR を持つ最短のサブアレイの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。