Rumah  >  Artikel  >  pembangunan bahagian belakang  >  Pertanyaan XOR tentang Subarray

Pertanyaan XOR tentang Subarray

DDD
DDDasal
2024-09-13 22:17:42991semak imbas

XOR Queries of a Subarray

1310. Pertanyaan XOR tentang Subarray

Kesukaran: Sederhana

Topik: Tatasusunan, Manipulasi Bit, Jumlah Awalan

Anda diberi arr tatasusunan integer positif. Anda juga diberikan pertanyaan tatasusunan di mana pertanyaan[i] = [kirii, kanani].

Untuk setiap pertanyaan saya mengira XOR unsur dari kirii ke kanani (iaitu, arr[kirii] XOR arr[kirii 1] XOR ... XOR arr[kanani] ).

Kembalikan jawapan tatasusunan dengan jawapan[i] ialah jawapan kepada pertanyaan ike.

Contoh 1:

  • Input: arr = [1,3,4,8], pertanyaan = [[0,1],[1,2],[0,3],[3,3]]
  • Output: [2,7,14,8]
  • Penjelasan: Perwakilan binari unsur-unsur dalam tatasusunan ialah:
  1 = 0001
  3 = 0011
  4 = 0100
  8 = 1000

Nilai XOR untuk pertanyaan ialah:

  [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

Contoh 2:

  • Input: arr = [4,8,2,10], pertanyaan = [[2,3],[1,3],[0,0],[0,3]]
  • Output: [8,0,4,4]

Kekangan:

  • 1 <= arr.length, queries.length <= 3 * 104
  • 1 <= arr[i] <= 109
  • pertanyaan[i].panjang == 2
  • 0 <= kirii <= kanani < arr.panjang

Petunjuk:

  1. Apakah keputusan x ^ y ^ x ?
  2. Kira jumlah awalan untuk XOR.
  3. Proses pertanyaan dengan nilai jumlah awalan.

Penyelesaian:

Kita boleh menggunakan teknik awalan XOR. Begini caranya:

Pendekatan:

  1. Awalan Tatasusunan XOR: Kami mengira tatasusunan XOR awalan dengan awalan[i] mewakili XOR semua elemen dari permulaan tatasusunan sehingga indeks i. Ini membolehkan kami mengira XOR mana-mana subarray dalam masa yang tetap.

  2. XOR subaray:

    • Untuk mengira XOR unsur antara indeks kiri dan kanan:
      • Jika dibiarkan > 0, kita boleh mengira XOR dari kiri ke kanan sebagai awalan[kanan] ^ awalan[kiri - 1].
      • Jika dibiarkan == 0, maka hasilnya hanyalah awalan[kanan].

      Ini membolehkan kami menjawab setiap pertanyaan dalam masa yang tetap selepas membina tatasusunan XOR awalan.

      Pelan:

      1. Bina tatasusunan XOR awalan.
      2. Untuk setiap pertanyaan, gunakan tatasusunan awalan XOR untuk mengira XOR bagi julat [left_i, right_i].

      Mari laksanakan penyelesaian ini dalam PHP: 1310. Pertanyaan XOR tentang Subarray

      <?php
      /**
       * @param Integer[] $arr
       * @param Integer[][] $queries
       * @return Integer[]
       */
      function xorQueries($arr, $queries) {
          ...
          ...
          ...
          /**
           * go to ./solution.php
           */
      }
      
      // Example 1
      $arr1 = [1, 3, 4, 8];
      $queries1 = [[0, 1], [1, 2], [0, 3], [3, 3]];
      print_r(xorQueries($arr1, $queries1)); // Output: [2, 7, 14, 8]
      
      // Example 2
      $arr2 = [4, 8, 2, 10];
      $queries2 = [[2, 3], [1, 3], [0, 0], [0, 3]];
      print_r(xorQueries($arr2, $queries2)); // Output: [8, 0, 4, 4]
      ?>
      

      Penjelasan:

      1. Pembinaan XOR Awalan:

        • Awalan tatasusunan dibina sedemikian rupa sehingga awalan[i] mengandungi XOR semua elemen daripada arr[0] hingga arr[i].
        • Sebagai contoh, diberi arr = [1, 3, 4, 8], tatasusunan awalan ialah [1, 1^3, 1^3^4, 1^3^4^8] atau [1, 2 , 6, 14].
      2. Menjawab Pertanyaan:

        • Untuk setiap pertanyaan [kiri, kanan], kami mengira XOR subarray arr[left] kepada arr[kanan] menggunakan:
          • awalan[kanan] ^ awalan[kiri - 1] (jika kiri > 0)
          • awalan[kanan] (jika kiri == 0)

      Kerumitan Masa:

      • Membina tatasusunan awalan: O(n), dengan n ialah panjang arr.
      • Memproses pertanyaan: O(q), dengan q ialah bilangan pertanyaan.
      • Kerumitan Masa Keseluruhan: O(n q), yang cekap untuk kekangan yang diberikan.

      Pendekatan ini memastikan kami boleh mengendalikan sehingga 30,000 pertanyaan pada tatasusunan saiz sehingga 30,000 dengan cekap.

      Pautan Kenalan

      Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

      Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:

      • LinkedIn
      • GitHub

      Atas ialah kandungan terperinci Pertanyaan XOR tentang Subarray. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan:
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn