Maison > Article > développement back-end > Requêtes XOR d'un sous-tableau
1310. Requêtes XOR d'un sous-tableau
Difficulté :Moyen
Sujets : Tableau, manipulation de bits, somme de préfixes
Vous recevez un tableau d'entiers positifs. Vous recevez également les requêtes de tableau où requêtes[i] = [lefti, righti].
Pour chaque requête, je calcule le XOR des éléments de gauchei à droitei (c'est-à-dire arr[lefti] XOR arr[lefti 1] XOR ... XOR arr[righti] ).
Renvoyer un tableau de réponse où réponse[i] est la réponse à la iième requête.
Exemple 1 :
1 = 0001 3 = 0011 4 = 0100 8 = 1000
Les valeurs XOR pour les requêtes sont :
[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
Exemple 2 :
Contraintes :
Indice :
Solution :
On peut utiliser la technique du préfixe XOR. Voici comment cela fonctionne :
Tableau XOR de préfixe : Nous calculons un tableau XOR de préfixe où le préfixe[i] représente le XOR de tous les éléments depuis le début du tableau jusqu'à l'index i. Cela nous permet de calculer le XOR de n'importe quel sous-tableau en temps constant.
XOR d'un sous-tableau :
Cela nous permet de répondre à chaque requête en temps constant après avoir construit le tableau de préfixes XOR.
Implémentons cette solution en PHP : 1310. Requêtes XOR d'un sous-tableau
<?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éfixe XOR Construction :
Répondre aux requêtes :
Cette approche garantit que nous pouvons traiter efficacement jusqu'à 30 000 requêtes sur un tableau d'une taille allant jusqu'à 30 000.
Liens de contact
Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !
Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!