Maximales XOR für jede Abfrage

1829. Maximales XOR für jede Abfrage

Schwierigkeit:Mittel

Themen: Array, Bitmanipulation, Präfixsumme

Sie erhalten ein sortiertes Array mit n nicht negativen Ganzzahlen und einem ganzzahligen MaximumBit. Sie möchten die folgende Abfrage n mal durchführen:

• Finden Sie eine nicht negative ganze Zahl k < 2^maximumBit so dass nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k maximiert ist. k ist die Antwort auf die i^te Frage.
• Entfernen Sie das letzte Element aus den aktuellen Array-Nummern.

Gib eine Array-Antwort zurück, wobei Antwort[i] die Antwort auf die i^teAbfrage ist.

Beispiel 1:

• Eingabe: nums = [0,1,1,3], MaximumBit = 2
• Ausgabe: [0,3,2,3]
• Erklärung: Die Anfragen werden wie folgt beantwortet:
  • 1^stste Abfrage: nums = [0,1,1,3], k = 0 seit 0 XOR 1 XOR 1 XOR 3 XOR 0 = 3.
  • 2^nd Abfrage: nums = [0,1,1], k = 3 da 0 XOR 1 XOR 1 XOR 3 = 3.
  • 3^rd Abfrage: nums = [0,1], k = 2 seit 0 XOR 1 XOR 2 = 3.
  • 4^th Abfrage: nums = [0], k = 3 seit 0 XOR 3 = 3.

Beispiel 2:

• Eingabe: nums = [2,3,4,7], MaximumBit = 3
• Ausgabe: [5,2,6,5]
• Erklärung: Die Anfragen werden wie folgt beantwortet:
  • 1^ersteerste Abfrage: nums = [2,3,4,7], k = 5 da 2 XOR 3 XOR 4 XOR 7 XOR 5 = 7.
  • 2^nd Abfrage: nums = [2,3,4], k = 2 da 2 XOR 3 XOR 4 XOR 2 = 7.
  • 3^rd Abfrage: nums = [2,3], k = 6 da 2 XOR 3 XOR 6 = 7.
  • 4^te Abfrage: nums = [2], k = 5 seit 2 XOR 5 = 7.

Beispiel 3:

• Eingabe: nums = [0,1,2,2,5,7], MaximumBit = 3
• Ausgabe: [4,3,6,4,6,7]

Einschränkungen:

• nums.length == n
• 1 <= n <= 10⁵
• 1 <= MaximumBit <= 20
• 0 <= nums[i] < 2^maximumBit
• nums wird in aufsteigender Reihenfolge sortiert.

Hinweis:

1. Beachten Sie, dass das maximal mögliche XOR-Ergebnis immer 2^{(maximumBit) - 1} ist
2. Die Antwort für ein Präfix ist also die XOR-Verknüpfung dieses Präfixes mit 2^{(maximumBit)-1}

Lösung:

Wir müssen das XOR der Elemente im Array effizient berechnen und das Ergebnis mit einem Wert k maximieren, sodass k kleiner als 2^maximumBit ist. Hier ist der Ansatz zur Lösung dieses Problems:

Beobachtungen und Ansatz

1. XOR maximieren:
   Die maximale Anzahl, die wir mit jeder Präfixsumme für MaximumBit-Bits XOR-verknüpfen können, ist ( 2^{text{maximumBit}} - 1 ). Dies liegt daran, dass die XOR-Verknüpfung mit einer Zahl, die nur aus Einsen besteht (d. h. 111...1 im Binärformat), das Ergebnis immer maximiert.

2. Präfix-XOR-Berechnung:
   Anstatt das XOR für jede Abfrage neu zu berechnen, können wir ein kumulatives XOR für das gesamte Array verwalten. Da XOR die Eigenschaft hat, dass A XOR B

3. Algorithmus

   :

   Berechnen Sie zunächst das XOR aller Elemente in Zahlen. Nennen wir das currentXOR.
   • Für jede Abfrage (von der letzten zur ersten):
   • Berechnen Sie den optimalen Wert von k für diese Abfrage, indem Sie currentXOR mit maxNum XOR-verknüpfen, wobei maxNum = 2^maximumBit - 1.
     • K an die Ergebnisliste anhängen.
     • Entfernen Sie das letzte Element aus Nums, indem Sie es aus currentXOR mit XOR verknüpfen.
     Die Ergebnisliste enthält die Antworten in umgekehrter Reihenfolge, also kehren Sie sie am Ende um.
Lassen Sie uns diese Lösung in PHP implementieren:

MaxNum berechnen
:



maxNum wird als 2^maximumBit - 1 berechnet, was die Zahl mit allen Einsen im Binärformat für die angegebene Bitlänge ist.





Erste XOR-Berechnung
:


Wir XORen alle Elemente in Zahlen, um das kumulative XOR (currentXOR) zu erhalten, das das XOR aller Zahlen im Array darstellt.





Rückwärts iterieren
:


Wir beginnen mit dem letzten Element in Zahlen und berechnen das maximale XOR für jeden Schritt:



currentXOR ^ maxNum gibt das maximale k für den aktuellen Zustand an.

K an die Antwort anhängen.


Wir XORen dann das letzte Element von nums mit currentXOR, um es für die nächste Iteration aus der XOR-Summe zu „entfernen“.




Antwort zurückgeben
:


Da wir die Liste umgekehrt verarbeitet haben, enthält die Antwort die Werte in umgekehrter Reihenfolge, sodass die endgültige Liste bereits korrekt für unsere Anforderungen angeordnet ist.






  
  
  Komplexitätsanalyse




Zeitkomplexität
: O(n), da wir das anfängliche XOR in O(n) berechnen und Jede Anfrage wird in konstanter Zeit verarbeitet.

Raumkomplexität
: O(n), zum Speichern der Antwort.


Dieser Code ist effizient und sollte die Obergrenzen der Einschränkungen gut bewältigen.

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:


LinkedIn
GitHub



          

            
  

            
        


Das obige ist der detaillierte Inhalt vonMaximales XOR für jede Abfrage. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!