各クエリの最大 XOR

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 は 昇順 順に並べ替えられます。

ヒント:

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

解決策:

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

観察とアプローチ

1. XOR の最大化:
   MaximumBit ビットのプレフィックス合計と XOR できる最大数は ( 2^{text{maximumBit}} - 1 ) です。これは、すべて 1 の数 (つまり、バイナリで 111...1) との XOR 演算が常に結果を最大化するためです。

2. プレフィックス XOR 計算:
   各クエリの XOR を再計算する代わりに、配列全体の累積 XOR を維持できます。 XOR には A XOR B XOR B = A という特性があるため、配列から最後の要素を削除するには、累積 XOR からその要素を XOR 演算することで実現できます。

3. アルゴリズム:

   • 最初に 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]
?>

説明：

1. maxNum を計算:

   • maxNum は 2^maximumBit - 1 として計算されます。これは、指定されたビット長の 2 進数ですべて 1 を含む数値です。

2. 最初の XOR 計算:

   • nums 内のすべての要素を XOR して、配列内のすべての数値の XOR を表す累積 XOR (currentXOR) を取得します。

3. 後方への反復:

   • nums の最後の要素から開始して、各ステップの最大 XOR を計算します。
     • currentXOR ^ maxNum は、現在の状態の最大 k を与えます。
     • 答えには k を追加します。
   • 次に、nums の最後の要素を currentXOR と XOR して、次の反復の XOR 合計から「削除」します。

4. 答えを返す:

   • リストを逆に処理したため、回答には逆順の値が含まれるため、最終的なリストはすでに要件に合わせて正しく配置されています。

複雑さの分析

• 時間計算量: O(n)。O(n) で初期 XOR を計算するため、各クエリは一定時間で処理されます。
• 空間複雑度: O(n)、答えを保存するため。

このコードは効率的であり、制約の上限を適切に処理する必要があります。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上が各クエリの最大 XORの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。