各クエリの最大 XOR

Mary-Kate Olsen
リリース: 2024-11-10 17:41:02
オリジナル
259 人が閲覧しました

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]
  • 説明: クエリは次のように回答されます。
    • 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 は 昇順 順に並べ替えられます。

ヒント:

  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 サイトの他の関連記事を参照してください。

ソース:dev.to
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
著者別の最新記事
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート