Heim > Artikel > Backend-Entwicklung > XOR-Abfragen eines Subarrays
1310. XOR-Abfragen eines Subarrays
Schwierigkeit:Mittel
Themen: Array, Bitmanipulation, Präfixsumme
Sie erhalten ein Array arr positiver Ganzzahlen. Sie erhalten auch die Array-Abfragen, wobei query[i] = [lefti, righti].
istFür jede Abfrage berechne ich das XOR von Elementen von linksi nach rechtsi (das heißt, arr[lefti] XOR arr[lefti 1] XOR ... XOR arr[righti] ).
Gib eine Array-Antwort zurück, wobei Antwort[i] die Antwort auf die iteAbfrage ist.
Beispiel 1:
1 = 0001 3 = 0011 4 = 0100 8 = 1000
Die XOR-Werte für Abfragen sind:
[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
Beispiel 2:
Einschränkungen:
Hinweis:
Lösung:
Wir können die Präfix-XOR-Technik verwenden. So funktioniert es:
Präfix-XOR-Array: Wir berechnen ein Präfix-XOR-Array, wobei prefix[i] das XOR aller Elemente vom Anfang des Arrays bis zum Index i darstellt. Dadurch können wir das XOR eines beliebigen Subarrays in konstanter Zeit berechnen.
XOR eines Subarrays:
Dadurch können wir jede Anfrage in konstanter Zeit beantworten, nachdem wir das Präfix-XOR-Array erstellt haben.
Lassen Sie uns diese Lösung in PHP implementieren: 1310. XOR-Abfragen eines Subarrays
<?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] ?>
Präfix-XOR-Konstruktion:
Anfragen beantworten:
Dieser Ansatz stellt sicher, dass wir bis zu 30.000 Abfragen auf einem Array mit einer Größe von bis zu 30.000 effizient bearbeiten können.
Kontaktlinks
Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!
Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:
Das obige ist der detaillierte Inhalt vonXOR-Abfragen eines Subarrays. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!