Rumah > Artikel > pembangunan bahagian belakang > 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] = [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:
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:
Kekangan:
Petunjuk:
Penyelesaian:
Kita boleh menggunakan teknik awalan XOR. Begini caranya:
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.
XOR subaray:
Ini membolehkan kami menjawab setiap pertanyaan dalam masa yang tetap selepas membina tatasusunan XOR awalan.
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] ?>
Pembinaan XOR Awalan:
Menjawab Pertanyaan:
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:
Atas ialah kandungan terperinci Pertanyaan XOR tentang Subarray. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!