Pertanyaan XOR tentang 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] = [kiri_i, kanan_i].

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

Kembalikan jawapan tatasusunan dengan jawapan[i] ialah jawapan kepada pertanyaan i^ke.

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 * 10⁴
• 1 <= arr[i] <= 10⁹
• pertanyaan[i].panjang == 2
• 0 <= kiri_i <= kanan_i < 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]
     ?>
     

     Salin selepas log masuk

     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!