ゼロより大きいビット単位の AND の最大の組み合わせ

2275。ビットごとの AND がゼロより大きい最大の組み合わせ

難易度: 中

トピック: 配列、ハッシュ テーブル、ビット操作、カウント

配列 nums の ビット単位の AND は、nums 内のすべての整数のビット単位の AND です。

• たとえば、nums = [1, 5, 3] の場合、ビット単位の AND は 1 & 5 & 3 = 1 に等しくなります。
• また、nums = [7] の場合、ビット単位の AND は 7 になります。

正の整数の候補の配列が与えられます。候補数のすべての組み合わせのビット単位のANDを評価します。候補内の各数字は、各組み合わせで 1 回のみ使用できます。

ビットごとの AND 0 より大きいを使用した候補の最大の組み合わせのサイズを返します。

例 1:

• 入力: 候補 = [16,17,71,62,12,24,14]
• 出力: 4
• 説明: 組み合わせ [16,17,62,24] には、16 & 17 & 62 & 24 = 16 > のビット単位の AND があります。 0.
  • 組み合わせのサイズは 4 です。
  • サイズが 4 を超える組み合わせには 0 を超えるビット単位の AND がないことがわかります。
  • 複数の組み合わせが最大サイズになる可能性があることに注意してください。
  • たとえば、[62,12,24,14] の組み合わせには、62 & 12 & 24 & 14 = 8 のビット単位の AND があります。 0.

例 2:

• 入力: 候補 = [8,8]
• 出力: 2
• 説明: 最大の組み合わせ [8,8] には、8 & 8 = 8 > のビット単位の AND があります。 0.
  • 組み合わせのサイズは 2 なので、2 を返します。

制約:

• 1 5
• 1 7

ヒント:

1. ビット単位の AND が 0 より大きくなるためには、組み合わせ内のすべての数値に対して少なくとも 1 つのビットが 1 である必要があります。
2. 候補は 24 ビット長なので、ビット位置ごとに、ビットごとの AND がそのビット位置で 1 になるような最大の組み合わせのサイズを計算できます。

解決策:

組み合わせ内のすべての数値にわたって、バイナリ表現の少なくとも 1 つのビット位置が設定 (1) のままである数値のグループを識別することに重点を置く必要があります。

ソリューションの概要

1. ビット分析: 候補内の各数値は最大 24 ビットの 2 進数で表現できるため (1

2. 各位置でセット ビットを数える: 各ビット位置について、候補内のそのビットが 1 に設定されている数値がいくつあるかを数えます。複数の数値が同じ位置でビットを共有している場合、それらは可能性があります。そのビット位置でゼロより大きいビット単位の AND の組み合わせを形成する可能性があります。

3. 最大数を見つける: ビットごとの AND の結果が次の値より大きい、考えられる最大の組み合わせを表すため、任意の位置に設定されたビットを持つ数値の最大数が答えになります。ゼロ。

例

候補 = [16, 17, 71, 62, 12, 24, 14]:

• 各数値を 2 進数に変換し、ビット位置を分析します。
• すべての数値にわたって各ビットが何回設定されているかを数えます。
• すべてのビット位置にわたる最大カウントを見つけます。

このソリューションを PHP で実装してみましょう: 2275。ビットごとの AND がゼロより大きい最大の組み合わせ

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

// Example usage
$candidates = [16, 17, 71, 62, 12, 24, 14];
echo largestCombination($candidates); // Output: 4
?>

説明：

1. 各ビット位置のループ: 0 から 23 までの各ビット位置を繰り返します。
2. ビットが設定された数字を数える: 各位置について、候補内のその特定のビットが設定されている数字の数を数えます。
3. 最大組み合わせサイズの更新: すべてのビット位置にわたる最大カウントを追跡します。
4. 結果を返す: 結果は、必要に応じて、ゼロより大きいビットごとの AND を使用した最大の組み合わせサイズです。

複雑さの分析

• 時間計算量: O(n x 24) = O(n)、n は、数値ごとに 24 の演算 (ビット位置ごとに 1 つ) を実行するためです。
• スペースの複雑さ: O(1)。固定量の追加スペースのみを使用しているためです。

このアプローチは、入力サイズ制限 (candidates.length 5) を処理するのに十分効率的です。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上がゼロより大きいビット単位の AND の最大の組み合わせの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。