配列の最小端-PHPチュートリアル-php.cn

配列の最小端

Linda Hamilton

リリース： 2024-11-14 11:45:02

オリジナル

360 人が閲覧しました

Minimum Array End

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

制約:

ヒント:

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

解決策:

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

内訳は次のとおりです:

ビット操作の洞察: nums[i] は、x と整数 0、1、...、n-1 を結合することによって構築される必要があることがわかります。これは、x の底から開始するため、ビットごとの AND 結果が x を確実に生成するのに役立ちます。
配列要素の構築: 各要素は、x と整数が結合されたものと考えることができ、x のビットをそのまま維持することを目指します。整数から追加のビットを埋めて、AND の結果を x に維持しながら増加する数値を取得します。
マージ戦略: 最小の 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
?>

ログイン後にコピー

説明：

ビットのチェックと設定:
- ans の各ビット (x から開始) をチェックし、ans のビットが 0 の場合は、k (n-1) の対応するビットを調べます。
- k のビットが 1 の場合、ans のビットを 1 に設定します。このプロセスにより、x に設定されたビットを維持しながら値の最小増分が確保されます。
ループ制約:
- 計算された最大値 (kMaxBit) まで各ビット位置を反復処理し、x と n の両方から必要なビットを確実にカバーします。
結果:
- ans の最終値は、条件を満たす nums[n-1] の最小値です。