Minimales Array-Ende

3133. Minimales Array-Ende

Schwierigkeit:Mittel

Themen:Bit-Manipulation

Sie erhalten zwei ganze Zahlen n und x. Sie müssen ein Array von positiven ganzen Zahlen der Größe n erstellen, wobei für jede 0 <= i < n - 1, nums[i 1] ist größer als nums[i] und das Ergebnis der bitweisen UND-Verknüpfung zwischen allen Elementen von nums ist x.

Gib den minimalsten möglichen Wert von nums[n - 1] zurück.

Beispiel 1:

• Eingabe: n = 3, x = 4
• Ausgabe: 6
• Erklärung: Zahlen können [4,5,6] sein und ihr letztes Element ist 6.

Beispiel 2:

• Eingabe: n = 2, x = 7
• Ausgabe: 15
• Erklärung: Zahlen können [7,15] sein und ihr letztes Element ist 15.

Beispiel 3:

• Eingabe: Kosten = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8] ]
• Ausgabe: 10

Einschränkungen:

• 1 <= n, x <= 10⁸

Hinweis:

1. Jedes Element des Arrays sollte durch „Zusammenführen“ von x und v erhalten werden, wobei v = 0, 1, 2, … (n - 1).
2. Um x mit einer anderen Zahl v zu verschmelzen, lassen Sie die gesetzten Bits von x unberührt. Füllen Sie für alle anderen Bits die gesetzten Bits von v von rechts nach links der Reihe nach auf.
3. Die endgültige Antwort ist also die „Verschmelzung“ von x und n - 1.

Lösung:

Wir müssen ein Array aus positiven ganzen Zahlen der Größe n erstellen, wobei jedes nachfolgende Element größer als das vorherige ist. Das bitweise UND aller Elemente in Nums sollte x ergeben. Wir werden gebeten, den minimal möglichen Wert von nums[n-1] zu finden.

Hier ist die Aufschlüsselung:

1. Bit Manipulation Insight: Wir können beobachten, dass nums[i] durch Zusammenführen von x mit ganzen Zahlen 0, 1, ..., n-1 erstellt werden sollte. Dadurch wird sichergestellt, dass das bitweise AND-Ergebnis x ergibt, da wir mit einer Basis von x beginnen.

2. Aufbau der Array-Elemente: Jedes Element kann als mit einer ganzen Zahl verschmolzenes x betrachtet werden, und unser Ziel ist es, die Bits von x intakt zu halten. Wir füllen zusätzliche Bits aus der Ganzzahl aus, um steigende Zahlen zu erhalten, während das UND-Ergebnis als x beibehalten wird.

3. Zusammenführungsstrategie: Um die Mindestanzahl[n-1] zu finden, müssen wir nur x mit n-1 zusammenführen. Zusammenführen bedeutet in diesem Zusammenhang, dass, wenn irgendein Bit in x 1 ist, es 1 bleibt. Wir verwenden Bits von n-1, um alle erforderlichen zusätzlichen Bits hinzuzufügen, ohne die in x gesetzten Bits zu ändern.

Lassen Sie uns diese Lösung in PHP implementieren: 3133. Minimales Array-Ende

  
  
  Erläuterung:




Bitprüfung und -einstellung:


Wir überprüfen jedes Bit von ans (beginnend mit x) und wenn ein Bit in ans 0 ist, suchen wir nach dem entsprechenden Bit in k (das ist n-1).
Wenn das Bit in k 1 ist, setzen wir das Bit in ans auf 1. Dieser Prozess stellt die minimale Werterhöhung sicher und behält gleichzeitig die in x gesetzten Bits bei.



Schleifenbeschränkungen:


Wir durchlaufen jede Bitposition bis zu einem berechneten Maximum (kMaxBit) und stellen so sicher, dass wir die erforderlichen Bits sowohl von x als auch n abdecken.



Ergebnis:


Der Endwert von ans ist der minimal mögliche Wert für nums[n-1], der die Bedingungen erfüllt.





  
  
  Komplexität:



Der Algorithmus arbeitet in konstanter Zeit, da die Anzahl der Bits in jeder Ganzzahl in diesem Bereich durch 32 begrenzt ist, was diesen Ansatz auch für große Werte von n und x effizient macht.


Diese Lösung liefert die gewünschte Mindestanzahl[n-1] unter Beibehaltung der erforderlichen Eigenschaften.

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 vonMinimales Array-Ende. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!