XOR maximum pour chaque requête

1829. XOR maximum pour chaque requête

Difficulté :Moyen

Sujets : Tableau, manipulation de bits, somme de préfixes

Vous recevez un tableau trié de n nombres entiers non négatifs et un maximumBit entier. Vous souhaitez effectuer la requête suivante n fois :

• Trouver un entier non négatif k < 2^maximumBit tel que nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k est maximisé. k est la réponse à la i^ème requête.
• Supprimez le dernier élément des numéros de tableau actuels.

Renvoyer une réponse de tableau, où réponse[i] est la réponse à la i^ième requête.

Exemple 1 :

• Entrée : nums = [0,1,1,3], maximumBit = 2
• Sortie : [0,3,2,3]
• Explication : Les requêtes reçoivent la réponse suivante :
  • 1^stst requête : nums = [0,1,1,3], k = 0 puisque 0 XOR 1 XOR 1 XOR 3 XOR 0 = 3.
  • 2^nd requête : nums = [0,1,1], k = 3 puisque 0 XOR 1 XOR 1 XOR 3 = 3.
  • 3^rd requête : nums = [0,1], k = 2 puisque 0 XOR 1 XOR 2 = 3.
  • 4^ème requête : nums = [0], k = 3 puisque 0 XOR 3 = 3.

Exemple 2 :

• Entrée : nums = [2,3,4,7], maximumBit = 3
• Sortie : [5,2,6,5]
• Explication : Les requêtes reçoivent la réponse suivante :
  • 1^stst requête : nums = [2,3,4,7], k = 5 puisque 2 XOR 3 XOR 4 XOR 7 XOR 5 = 7.
  • 2^nd requête : nums = [2,3,4], k = 2 puisque 2 XOR 3 XOR 4 XOR 2 = 7.
  • 3^rd requête : nums = [2,3], k = 6 puisque 2 XOR 3 XOR 6 = 7.
  • 4^ème requête : nums = [2], k = 5 puisque 2 XOR 5 = 7.

Exemple 3 :

• Entrée : nums = [0,1,2,2,5,7], maximumBit = 3
• Sortie : [4,3,6,4,6,7]

Contraintes :

• nums.length == n
• 1 <= n <= 10⁵
• 1 <= maximumBit <= 20
• 0 <= nums[i] < 2^{bit maximum}
• nums​​​ est trié par ordre croissant.

Indice :

1. Notez que le résultat XOR maximum possible est toujours 2^{(maximumBit) - 1}
2. Donc, la réponse pour un préfixe est le XOR de ce préfixe XORed avec 2^{(maximumBit)-1}

Solution :

Nous devons calculer efficacement le XOR des éléments du tableau et maximiser le résultat en utilisant une valeur k telle que k soit inférieur à 2^maximumBit. Voici l'approche pour résoudre ce problème :

Observations et approche

1. Maximisation de XOR :
   Le nombre maximum que nous pouvons XOR avec n'importe quelle somme de préfixe pour les bits maximumBit est ( 2^{text{maximumBit}} - 1 ). En effet, le XOR avec un nombre composé uniquement de 1 (c'est-à-dire 111...1 en binaire) maximisera toujours le résultat.

2. Calcul du préfixe XOR :
   Au lieu de recalculer le XOR pour chaque requête, nous pouvons conserver un XOR cumulatif pour l'ensemble du tableau. Puisque XOR a la propriété A XOR B XOR B = A, la suppression du dernier élément du tableau peut être obtenue en retirant cet élément du XOR cumulatif.

3. Algorithme :

   • Calculez initialement le XOR de tous les éléments en nombres. Appelons cela currentXOR.
   • Pour chaque requête (de la dernière à la première) :
     • Calculez la valeur optimale de k pour cette requête en XORing currentXOR avec maxNum où maxNum = 2^maximumBit - 1.
     • Ajouter k à la liste des résultats.
     • Supprimez le dernier élément de nums en le XORant hors de currentXOR.
   • La liste des résultats contiendra les réponses dans l'ordre inverse, donc inversez-la à la fin.

Implémentons cette solution en PHP : 1829. XOR maximum pour chaque requête

  
  
  Explication:




Calculer maxNum :



maxNum est calculé comme 2^maximumBit - 1, qui est le nombre avec tous les 1 en binaire pour la longueur de bits spécifiée.



Calcul XOR initial :


Nous XOR tous les éléments en nombres pour obtenir le XOR cumulatif (currentXOR), représentant le XOR de tous les nombres du tableau.



Itérer à l'envers :


Nous partons du dernier élément en chiffres et calculons le XOR maximum pour chaque étape :



currentXOR ^ maxNum donne le k maximum pour l'état actuel.
Ajoutez k à la réponse.


Nous XOR ensuite le dernier élément de nums avec currentXOR pour le "supprimer" de la somme XOR pour la prochaine itération.



Renvoyer la réponse :


Puisque nous avons traité la liste dans l'ordre inverse, la réponse contiendra les valeurs dans l'ordre inverse, donc la liste finale est déjà organisée correctement pour nos besoins.





  
  
  Analyse de complexité




Complexité temporelle : O(n), puisqu'on calcule le XOR initial en O(n) et chaque requête est traitée en temps constant.

Complexité spatiale : O(n), pour stocker la réponse.


Ce code est efficace et devrait bien gérer les limites supérieures des contraintes.

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 :


LinkedIn
GitHub



          

            
  

            
        
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!