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]
-
説明: クエリは次のように回答されます。
- 1stst クエリ: nums = [0,1,1,3]、k = 0 because 0 XOR 1 XOR 1 XOR 3 XOR 0 = 3.
- 2nd クエリ: nums = [0,1,1], k = 3 because 0 XOR 1 XOR 1 XOR 3 = 3.
- 3rd クエリ: 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]
-
説明: クエリは次のように回答されます。
- 1stst クエリ: nums = [2,3,4,7]、2 XOR 3 XOR 4 XOR 7 XOR 5 = 7 であるため、k = 5。
- 2nd クエリ: nums = [2,3,4]、k = 2 because 2 XOR 3 XOR 4 XOR 2 = 7.
- 3rd クエリ: 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 合計から「削除」します。
-
答えを返す:
- リストを逆に処理したため、回答には逆順の値が含まれるため、最終的なリストはすでに要件に合わせて正しく配置されています。
複雑さの分析
-
時間計算量: O(n)。O(n) で初期 XOR を計算するため、各クエリは一定時間で処理されます。
-
空間複雑度: O(n)、答えを保存するため。
このコードは効率的であり、制約の上限を適切に処理する必要があります。
連絡先リンク
このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!
このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:
以上が各クエリの最大 XORの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。