Mindestanzahl an Änderungen, um Binärzeichenfolgen schön zu machen

2914. Mindestanzahl an Änderungen, um Binärzeichenfolgen schön zu machen

Schwierigkeit:Mittel

Themen:String

Sie erhalten eine 0-indizierte Binärzeichenfolge s mit gerader Länge.

Ein String ist schön, wenn es möglich ist, ihn in einen oder mehrere Teilstrings zu unterteilen, sodass:

• Jeder Teilstring hat eine gerade Länge.
• Jede Teilzeichenfolge enthält nur Einsen oder nur 0en.

Sie können jedes Zeichen in s in 0 oder 1 ändern.

Gib die Mindestanzahl der Änderungen zurück, die erforderlich sind, um die Zeichenfolge schön zu machen.

Beispiel 1:

• Eingabe: s = "1001"
• Ausgabe: 2
• Erklärung: Wir ändern s[1] auf 1 und s[3] auf 0, um die Zeichenfolge „1100“ zu erhalten.
  • Man sieht, dass die Zeichenfolge „1100“ schön ist, weil wir sie in „11|00“ unterteilen können.
  • Es kann bewiesen werden, dass 2 die Mindestanzahl an Änderungen ist, die erforderlich sind, um die Zeichenfolge schön zu machen.

Beispiel 2:

• Eingabe: s = "10"
• Ausgabe: 1
• Erklärung: Wir ändern s[1] auf 1, um die Zeichenfolge „11“ zu erhalten.
  • Man sieht, dass die Zeichenfolge „11“ schön ist, weil wir sie in „11“ unterteilen können.
  • Es kann bewiesen werden, dass 1 die Mindestanzahl an Änderungen ist, die erforderlich sind, um die Zeichenfolge schön zu machen.

Beispiel 3:

• Eingabe: s = "0000"
• Ausgabe: 0
• Erklärung:Wir müssen keine Änderungen vornehmen, da die Zeichenfolge „0000“ bereits schön ist.

Einschränkungen:

• 2 <= s.length <= 10⁵
• s hat eine gleichmäßige Länge.
• s[i] ist entweder '0' oder '1'.

Hinweis:

1. Da bei jeder gültigen Partition jeder Teil aus einer geraden Anzahl derselben Zeichen besteht, können wir jeden Teil weiter in Längen von genau 2 unterteilen.
2. Nachdem wir den ersten Hinweis bemerkt haben, können wir die gesamte Zeichenfolge in disjunkte Blöcke der Größe 2 zerlegen und die minimale Anzahl von Änderungen ermitteln, die erforderlich sind, um diese Blöcke schön zu machen.

Lösung:

Wir müssen sicherstellen, dass jedes Zeichenpaar in der Binärzeichenfolge s entweder „00“ oder „11“ ist. Wenn ein Paar nicht in einem dieser beiden Muster enthalten ist, müssen wir eines der Zeichen ändern, damit es übereinstimmt.

Hier ist der schrittweise Lösungsansatz:

1. Teilen Sie die Zeichenfolge in Blöcke: Da eine schöne Zeichenfolge aus Blöcken der Länge 2 gebildet werden kann, können wir die Zeichenfolge in 2er-Schritten durchlaufen.

2. Änderungen zählen: Für jeden Block mit 2 Zeichen müssen wir das Mehrheitszeichen bestimmen (entweder 0 oder 1). Wir werden das Minderheitszeichen im Block so ändern, dass es mit dem Mehrheitszeichen übereinstimmt.

3. Mindeständerungen berechnen: Wenn beide Zeichen unterschiedlich sind, benötigen wir für jeden Block 1 Änderung; Wenn sie gleich sind, sind keine Änderungen erforderlich.

Lassen Sie uns diese Lösung in PHP implementieren: 2914. Mindestanzahl an Änderungen, um Binärzeichenfolgen schön zu machen

  
  
  Erläuterung:



Funktionsdefinition: Wir definieren eine Funktion minChanges, die eine Binärzeichenfolge s akzeptiert.
Initialisierung: Wir initialisieren eine Variable $changes, um die Anzahl der erforderlichen Änderungen zu verfolgen.

Über die Zeichenfolge iterieren: Wir durchlaufen die Zeichenfolge und erhöhen jedes Mal um 2, um jeden Block aus zwei Zeichen zu überprüfen:



$first ist das Zeichen an der aktuellen Position.

$second ist das Zeichen an der nächsten Position.


Auf Änderungen prüfen: Wenn die Zeichen im aktuellen Block unterschiedlich sind, erhöhen wir den $changes-Zähler um 1.
Ergebnis zurückgeben: Abschließend geben wir die Gesamtzahl der erforderlichen Änderungen zurück.



  
  
  Komplexität:




Zeitkomplexität: O(n), wobei n die Länge der Zeichenfolge ist, wie bei uns einmal über die Zeichenfolge iterieren.

Raumkomplexität: O(1), da wir konstant viel zusätzlichen Raum nutzen.


Diese Lösung arbeitet mit O(n) Zeitkomplexität, wobei n die Länge der Zeichenfolge ist, was sie für die gegebenen Einschränkungen effizient macht.

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 vonMindestanzahl an Änderungen, um Binärzeichenfolgen schön zu machen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!