配列の最小端

3133。最小配列の終わり

難易度: 中

トピック: ビット操作

2 つの整数 n と x が与えられます。サイズ n の 正 整数の配列を構築する必要があります。ここで、すべての 0 大きく であり、nums のすべての要素間のビット単位の AND 演算の結果は x.

です。

nums[n - 1] の 最小値を 返します。

例 1:

• 入力: n = 3、x = 4
• 出力: 6
• 説明: nums は [4,5,6] で、最後の要素は 6 です。

例 2:

• 入力: n = 2、x = 7
• 出力: 15
• 説明: nums は [7,15] で、最後の要素は 15 です。

例 3:

• 入力: コスト = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8] ]
• 出力: 10

制約:

• 1 8

ヒント:

1. 配列の各要素は、x と v を「マージ」することによって取得する必要があります (v = 0、1、2、…(n - 1))。
2. x を別の数値 v とマージするには、x の設定ビットをそのままにし、他のすべてのビットについては、v の設定ビットを右から左に順番に 1 つずつ埋めます。
3. したがって、最終的な答えは、x と n - 1 の「マージ」です。

解決策:

サイズ n の正の整数の配列 nums を構築する必要があります。ここで、連続する各要素は前の要素よりも大きくなります。 nums 内のすべての要素のビット単位の AND は x を生成する必要があります。 nums[n-1] の最小値を見つけるように求められます。

内訳は次のとおりです:

1. ビット操作の洞察: nums[i] は、x と整数 0、1、...、n-1 を結合することによって構築される必要があることがわかります。これは、x の底から開始するため、ビットごとの AND 結果が x を確実に生成するのに役立ちます。

2. 配列要素の構築: 各要素は、x と整数が結合されたものと考えることができ、x のビットをそのまま維持することを目指します。整数から追加のビットを埋めて、AND の結果を x に維持しながら増加する数値を取得します。

3. マージ戦略: 最小の nums[n-1] を見つけるには、x を n-1 とマージするだけで済みます。このコンテキストでのマージは、x 内のビットが 1 の場合、それは 1 のままであることを意味します。n-1 のビットを使用して、x に設定されたビットを変更せずに、必要な追加ビットを追加します。

このソリューションを PHP で実装してみましょう: 3133。最小配列の終わり

<?php
/**
 * @param Integer $n
 * @param Integer $x
 * @return Integer
 */
function minEnd($n, $x) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
echo minimumArrayEnd(3, 4) . "\n";  // Output: 6

// Example 2
echo minimumArrayEnd(2, 7) . "\n";  // Output: 15
?>

説明：

1. ビットのチェックと設定:

   • ans の各ビット (x から開始) をチェックし、ans のビットが 0 の場合は、k (n-1) の対応するビットを調べます。
   • k のビットが 1 の場合、ans のビットを 1 に設定します。このプロセスにより、x に設定されたビットを維持しながら値の最小増分が保証されます。

2. ループ制約:

   • 計算された最大値 (kMaxBit) まで各ビット位置を反復処理し、x と n の両方から必要なビットを確実にカバーします。

3. 結果:

   • ans の最終値は、条件を満たす nums[n-1] の最小値です。

複雑：

• この範囲内の整数のビット数は 32 で制限されるため、アルゴリズムは一定時間で動作し、n と x の値が大きい場合でもこのアプローチは効率的になります。

このソリューションは、必要なプロパティを維持しながら、必要な最小の nums[n-1] を生成します。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上が配列の最小端の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。