ビットごとの OR サブセットの最大数をカウントする

2044年。最大ビット単位 OR サブセットの数をカウント

難易度: 中

トピック: 配列、バックトラッキング、ビット操作、列挙

整数配列 nums を指定すると、nums のサブセットの ビットごとの OR が可能な最大を見つけ、空でない異なるサブセットの 数 最大ビット単位の OR.

配列 a は、b の一部 (おそらくゼロ) 要素を削除することによって b から a を取得できる場合、配列 b の

サブセット です。選択された要素のインデックスが異なる場合、2 つのサブセットは異なるとみなされます。

配列 a のビット単位の OR は、a[0] OR a[1] OR ... OR a[a.length - 1] (

0-indexed) と等しくなります。

例 1:

• 入力: nums = [3,1]
• 出力: 2
• 説明: サブセットのビットごとの OR の最大値は 3 です。ビットごとの OR が 3 であるサブセットが 2 つあります。
  [3]
  [3,1]

例 2:

• 入力: nums = [2,2,2]
• 出力: 7
• 説明: [2,2,2] の空ではないすべてのサブセットは 2 のビット単位の OR を持ちます。サブセットは合計 23 - 1 = 7 つあります。

例 3:

• 入力: 数値 = [3,2,1,5]
• 出力: 6
• 説明: サブセットのビットごとの OR の最大値は 7 です。ビットごとの OR が 7 であるサブセットは 6 つあります。
  [3,5]
  [3,1,5]
  [3,2,5]
  [3,2,1,5]
  [2,5]
  [2,1,5]

制約:

1 1 5

ヒント:

考えられるすべてのサブセットを列挙できますか?
最大のビットごとの OR は、配列全体のビットごとの OR です。

解決策:

次の手順に従うことができます:

1. 最大ビット単位 OR を計算する: サブセットの最大ビット単位 OR は、配列のすべての要素に対してビット単位 OR 演算を実行することで決定できます。これにより、可能な最大のビット単位の OR が得られます。

2. すべてのサブセットを列挙する

   : 配列のサイズが小さい (最大 16) ため、ビット操作手法を使用して考えられるすべてのサブセットを列挙できます。サイズ n の配列の場合、2^n 個の可能なサブセットがあります。

3. 有効なサブセットの数

   : 各サブセットについて、そのビット単位の OR を計算し、それが最大のビット単位の OR と一致するかどうかを確認します。存在する場合は、カウンターをインクリメントします。

このソリューションを PHP で実装してみましょう: 2044。最大ビット単位 OR サブセットの数をカウント

<?php /**
 * @param Integer[] $nums
 * @return Integer
 */
function countMaxBitwiseORSubsets($nums) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage
$nums1 = [3, 1];
echo countMaxBitwiseORSubsets($nums1) . "\n"; // Output: 2

$nums2 = [2, 2, 2];
echo countMaxBitwiseORSubsets($nums2) . "\n"; // Output: 7

$nums3 = [3, 2, 1, 5];
echo countMaxBitwiseORSubsets($nums3) . "\n"; // Output: 6
?>

説明：

1. 最大ビット単位 OR 計算:

   • ループを使用して、各要素に対してビットごとの OR を実行することで、配列の最大のビットごとの OR を計算します。

2. サブセット列挙:

   • 1 から 2^n - 1 (n は nums の長さ) までのすべての数値をループし、空でないすべてのサブセットを表します。
   • 数値ごとに各ビットをチェックして、サブセットにどの要素が含まれているかを確認します。

3. 有効なサブセット数:

   • 現在のサブセットのビットごとの OR を計算した後、それが maxOR に等しいかどうかを確認します。そうであれば、カウンターをインクリメントします。

このソリューションは制約を考慮すると効率的であり、サイズが 16 までの配列に対して適切に機能するため、最大 65,535 個のサブセットが評価されます。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上がビットごとの OR サブセットの最大数をカウントするの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。