ホームページ  >  記事  >  バックエンド開発  >  サブ配列の XOR クエリ

サブ配列の XOR クエリ

DDD
DDDオリジナル
2024-09-13 22:17:42999ブラウズ

XOR Queries of a Subarray

1310。サブ配列の XOR クエリ

難易度:

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

正の整数の配列 arr が与えられます。また、queries[i] = [lefti, righti].

となる配列クエリも与えられます。

クエリごとに、要素の XOR を左i から右i まで計算します (つまり、arr[lefti] XOR arr[lefti 1] XOR ... XOR arr[righti] ).

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

例 1:

  • 入力: arr = [1,3,4,8]、クエリ = [[0,1],[1,2],[0,3],[3,3]]
  • 出力: [2,7,14,8]
  • 説明: 配列内の要素のバイナリ表現は次のとおりです。
  1 = 0001
  3 = 0011
  4 = 0100
  8 = 1000

クエリの XOR 値は次のとおりです:

  [0,1] = 1 xor 3 = 2
  [1,2] = 3 xor 4 = 7
  [0,3] = 1 xor 3 xor 4 xor 8 = 14
  [3,3] = 8

例 2:

  • 入力: arr = [4,8,2,10]、クエリ = [[2,3],[1,3],[0,0],[0,3]]
  • 出力: [8,0,4,4]

制約:

  • 1 4
  • 1 9
  • クエリ[i].length == 2
  • 0 i <= 右i <配列の長さ

ヒント:

  1. x ^ y ^ x の結果は何ですか?
  2. XOR のプレフィックス合計を計算します。
  3. プレフィックス合計値を使用してクエリを処理します。

解決策:

プレフィックス XOR テクニックを利用できます。仕組みは次のとおりです:

アプローチ:

  1. プレフィックス XOR 配列: プレフィックス XOR 配列を計算します。ここで、prefix[i] は、配列の先頭からインデックス i までのすべての要素の XOR を表します。これにより、任意の部分配列の XOR を定数時間で計算できるようになります。

  2. 部分配列の XOR:

    • 左右のインデックス間の要素の XOR を計算するには:
      • 放置の場合> 0 の場合、prefix[right] ^ prefix[left - 1] として左から右に XOR を計算できます。
      • left == 0 の場合、結果は単に prefix[right] になります。

これにより、プレフィックス XOR 配列を構築した後、一定時間内に各クエリに答えることができます。

プラン:

  1. プレフィックス XOR 配列を構築します。
  2. クエリごとに、プレフィックス XOR 配列を使用して範囲 [left_i, right_i] の XOR を計算します。

このソリューションを PHP で実装してみましょう: 1310。サブ配列の XOR クエリ






説明:

  1. プレフィックス XOR 構築:

    • 配列プレフィックスは、prefix[i] に arr[0] から arr[i] までのすべての要素の XOR が含まれるように構築されます。
    • たとえば、arr = [1, 3, 4, 8] の場合、プレフィックス配列は [1, 1^3, 1^3^4, 1^3^4^8] または [1, 2] になります。 、6、14].
  2. クエリへの回答:

    • 各クエリ [left, right] について、次を使用して部分配列 arr[left] から arr[right] の XOR を計算します。
      • 接頭辞[右] ^ 接頭辞[左 - 1] (左> 0の場合)
      • prefix[right] (左 == 0 の場合)

時間計算量:

  • プレフィックス配列の構築: O(n)、n は arr の長さです。
  • クエリの処理: O(q)、q はクエリの数です。
  • 全体の時間計算量: O(n q)。指定された制約に対して効率的です。

このアプローチにより、最大 30,000 のサイズの配列に対する最大 30,000 のクエリを効率的に処理できるようになります。

連絡先リンク

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

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

  • LinkedIn
  • GitHub

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

声明:
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。