各クエリの最大 XOR-PHPチュートリアル-php.cn

各クエリの最大 XOR

Mary-Kate Olsen

リリース： 2024-11-10 17:41:02

オリジナル

341 人が閲覧しました

Maximum XOR for Each Query

1829年。各クエリの最大 XOR

難易度: 中

トピック: 配列、ビット操作、プレフィックス合計

n 個の非負の整数の sorted 配列 nums と整数の minimumBit が与えられます。次のクエリを n 回実行したいとします:

非負の整数 k maximumBit。nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k が 最大化となる。 k は、i^番目クエリに対する答えです。
現在の配列 nums から 最後の 要素を削除します。

配列の回答を返します。ここで、answer[i] は i^番目クエリ に対する回答です。

例 1:

入力: nums = [0,1,1,3]、maximumBit = 2
出力: [0,3,2,3]
説明: クエリは次のように回答されます。
- 1^stst クエリ: nums = [0,1,1,3]、k = 0 because 0 XOR 1 XOR 1 XOR 3 XOR 0 = 3.
- 2^nd クエリ: nums = [0,1,1], k = 3 because 0 XOR 1 XOR 1 XOR 3 = 3.
- 3^rd クエリ: nums = [0,1]、k = 2 because 0 XOR 1 XOR 2 = 3.
- 4^番目クエリ: nums = [0]、k = 3 because 0 XOR 3 = 3.

例 2:

入力: nums = [2,3,4,7]、maximumBit = 3
出力: [5,2,6,5]
説明: クエリは次のように回答されます。
- 1^stst クエリ: nums = [2,3,4,7]、2 XOR 3 XOR 4 XOR 7 XOR 5 = 7 であるため、k = 5。
- 2^nd クエリ: nums = [2,3,4]、k = 2 because 2 XOR 3 XOR 4 XOR 2 = 7.
- 3^rd クエリ: nums = [2,3]、k = 6 because 2 XOR 3 XOR 6 = 7.
- 4^番目クエリ: nums = [2]、2 XOR 5 = 7 なので k = 5。

例 3:

入力: nums = [0,1,2,2,5,7]、maximumBit = 3
出力: [4,3,6,4,6,7]

制約:

nums.length == n
1 5
1
0 最大ビット
nums は昇順順に並べ替えられます。

ヒント:

可能な最大の XOR 結果は常に 2^{(maximumBit) - 1} であることに注意してください。
したがって、プレフィックスの答えは、そのプレフィックスと 2^{(maximumBit)-1} を XOR したものになります。

解決策:

配列内の要素の XOR を効率的に計算し、k が 2^maximumBit 未満になるような値 k を使用して結果を最大化する必要があります。この問題を解決するためのアプローチは次のとおりです:

観察とアプローチ

XOR の最大化:
MaximumBit ビットのプレフィックス合計と XOR できる最大数は ( 2^{text{maximumBit}} - 1 ) です。これは、すべて 1 の数 (つまり、バイナリで 111...1) との XOR 演算が常に結果を最大化するためです。
プレフィックス XOR 計算:
各クエリの XOR を再計算する代わりに、配列全体の累積 XOR を維持できます。 XOR には A XOR B XOR B = A という特性があるため、配列から最後の要素を削除するには、累積 XOR からその要素を XOR 演算することで実現できます。
アルゴリズム:
- 最初に nums 内のすべての要素の XOR を計算します。これを currentXOR と呼びましょう。
- 各クエリについて (最後から最初まで):
  - currentXOR と maxNum の XOR 演算により、そのクエリの k の最適値を計算します (maxNum = 2^maximumBit - 1)。
  - 結果リストに k を追加します。
  - currentXOR から XOR して、nums から最後の要素を削除します。
- 結果リストには逆順で回答が含まれるため、最後に逆にしてください。

このソリューションを PHP で実装してみましょう: 1829。各クエリの最大 XOR

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

// Example usage:
$nums = [0,1,1,3];
$maximumBit = 2;
print_r(getMaximumXor($nums, $maximumBit));  // Output should be [0, 3, 2, 3]
?>

ログイン後にコピー

説明：

maxNum を計算:
- maxNum は 2^maximumBit - 1 として計算されます。これは、指定されたビット長の 2 進数ですべて 1 を含む数値です。
最初の XOR 計算:
- nums 内のすべての要素を XOR して、配列内のすべての数値の XOR を表す累積 XOR (currentXOR) を取得します。
後方への反復:
- nums の最後の要素から開始して、各ステップの最大 XOR を計算します。
  - currentXOR ^ maxNum は、現在の状態の最大 k を与えます。
  - 答えには k を追加します。
- 次に、nums の最後の要素を currentXOR と XOR して、次の反復の XOR 合計から「削除」します。
答えを返す:
- リストを逆に処理したため、回答には逆順の値が含まれるため、最終的なリストはすでに要件に合わせて正しく配置されています。