. Maximaler Tausch

670. Maximaler Tausch

Schwierigkeit:Mittel

Themen:Mathe, Gierig

Sie erhalten eine ganzzahlige Zahl. Sie können höchstens einmal zwei Ziffern vertauschen, um die höchstwertige Zahl zu erhalten.

Geben Sie die maximale Wertzahl zurück, die Sie erhalten können.

Beispiel 1:

• Eingabe: num = 2736
• Ausgabe: 7236
• Erklärung:Vertauschen Sie die Zahl 2 und die Zahl 7.

Beispiel 2:

• Eingabe: num = 9973
• Ausgabe: 9973
• Erklärung:Kein Tausch.

Einschränkungen:

• 0 <= num <= 10⁸

Lösung:

Wir können einen gierigen Ansatz verfolgen. Hier ist eine Schritt-für-Schritt-Erklärung und die Lösung:

Ansatz:

1. Konvertieren Sie die Zahl in ein Array: Da Ziffern vertauscht werden müssen, erleichtert die Konvertierung der Zahl in ein Ziffern-Array den Zugriff auf und die Bearbeitung einzelner Ziffern.
2. Verfolgen Sie das Vorkommen jeder Ziffer ganz rechts: Speichern Sie die Position ganz rechts jeder Ziffer (0-9) in einem Array.
3. Finden Sie die beste Tauschmöglichkeit: Gehen Sie die Ziffern der Zahl von links nach rechts durch und prüfen Sie für jede Ziffer, ob später eine höhere Ziffer erscheint. Wenn ja, tauschen Sie sie aus, um die Anzahl zu maximieren.
4. Führen Sie den Tausch und die Unterbrechung durch: Sobald der optimale Tausch gefunden wurde, führen Sie den Tausch durch und unterbrechen Sie die Schleife.
5. Konvertieren Sie das Array zurück in eine Zahl: Konvertieren Sie nach dem Austausch das Array aus Ziffern zurück in eine Zahl und geben Sie es zurück.

Lassen Sie uns diese Lösung in PHP implementieren: 670. Maximaler Tausch

  
  
  Erläuterung:




Schritt 1: strval($num) wandelt die Ganzzahl in eine Zeichenfolge um und str_split($numStr) teilt sie in ein Array von Ziffern auf.

Schritt 2: Das letzte Array verfolgt den Index ganz rechts jeder Ziffer von 0 bis 9.

Schritt 3: Wir durchlaufen jede Ziffer und suchen nach einer größeren Ziffer, die ausgetauscht werden kann.

Schritt 4: Wenn eine passende größere Ziffer gefunden wird (die später in der Zahl erscheint), werden die Ziffern vertauscht.

Schritt 5: Das geänderte Array wird mit intval() zurück in einen String und dann in eine Ganzzahl konvertiert.



  
  
  Komplexität:




Zeitkomplexität: O(n), wobei n die Anzahl der Ziffern in num ist. Das liegt daran, dass wir einen Durchlauf durch die Zahl machen, um das letzte Array zu füllen, und einen weiteren Durchlauf, um den optimalen Swap zu finden.

Raumkomplexität: O(1) (ohne Berücksichtigung der Eingabegröße), da das letzte Array auf 10 Elemente festgelegt ist.


Diese Lösung findet den Maximalwert effizient, indem die Ziffern nach Bedarf nur einmal ausgetauscht werden.

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