Minimieren Sie die Ersetzung eines Zeichens durch den nächsten Buchstaben, wodurch die Zeichenfolge ein Palindrom wird

In diesem Artikel werden wir ein interessantes algorithmisches Problem diskutieren: „Minimieren Sie den Ersatz von Zeichen durch ihr nächstgelegenes Alphabet, um ein String-Palindrom zu erstellen.“ Dieses Problem ist interessant, weil es String-Operationen, Palindrom-Prüfung und das Konzept des Zeichens umfasst ASCII-Werte. Lassen Sie uns näher auf dieses Thema eingehen.

Problemstellung

Bei einer gegebenen Zeichenfolge besteht die Aufgabe darin, sie mit einer minimalen Anzahl von Ersetzungen in ein Palindrom umzuwandeln. Diese Ersetzungen werden dadurch erreicht, dass die Zeichen durch das nächstgelegene Alphabet ersetzt werden.

Das Problem verstehen

Ein Palindrom ist eine Folge von Wörtern, Phrasen, Zahlen oder anderen Zeichen, die rückwärts genauso wie vorwärts gelesen wird. Unser Ziel ist es, die Gesamtzahl der Ersetzungen zu minimieren, die erforderlich sind, um eine bestimmte Zeichenfolge in ein Palindrom umzuwandeln.

Betrachten Sie beispielsweise die Zeichenfolge „abc“. Um es in ein Palindrom umzuwandeln, können wir „c“ durch „a“ ersetzen, was zwei Ersetzungen erfordert („c“ zu „b“ und „b“ zu „a“). Daher beträgt die Mindestanzahl an Ersetzungen 2.

Algorithmusmethode

Um dieses Problem zu lösen, verwenden wir die Zwei-Zeiger-Methode. Hier sind die Schritte -

• Initialisieren Sie zwei Zeiger, einen am Anfang der Zeichenfolge und einen am Ende der Zeichenfolge.

• Vergleichen Sie die Zeichen am Zeiger.

• Wenn gleich, bewegen Sie den Zeiger nach innen.

• Wenn sie nicht gleich sind, ersetzen Sie das Zeichen, das weiter von „a“ entfernt ist, durch das nähere Zeichen und erhöhen Sie die Anzahl der Ersetzungen. Bewegen Sie außerdem den Zeiger nach innen.

• Wiederholen Sie die Schritte 2-4, bis der Startzeiger nicht kleiner als der Endzeiger ist.

Beispiel

Dies ist der C++-Code, der die obige Methode implementiert -

#include<bits/stdc++.h>
using namespace std;

int makePalindrome(string str) {
   int len = str.size();
   int res = 0;
   for (int i = 0, j = len - 1; i < j; i++, j--) {
      res += abs(str[i] - str[j]);
   }
   return res;
}

int main() {
   string str="abcde";
   cout << "Minimum replacements: " << makePalindrome(str);
   return 0;
}

Ausgabe

Minimum replacements: 6

Testfallbeispiel

Lassen Sie uns ein Beispiel ausführen -

Betrachten Sie die Zeichenfolge „abcde“. Das obige Programm gibt „Mindestanzahl an Ersetzungen: 4“ aus. Deshalb -

• Vergleichen Sie „a“ und „e“. Sie sind nicht gleich, also ersetzen Sie „e“ durch „a“. Dies erforderte 4 Austausche. Unsere Zeichenfolge lautet jetzt „abcda“.

• Vergleichen Sie „b“ und „d“. Sie sind nicht gleich, also ersetzen Sie „d“ durch „b“. Dies erfordert 2 Austausche. Unsere Zeichenfolge lautet jetzt „abcba“.

• Jetzt ist die Zeichenfolge ein Palindrom. Daher beträgt die minimale Gesamtzahl der Substitutionen 4 + 2 = 6.

Denken Sie daran, dass die Anzahl der Ersetzungen auf der Grundlage der absoluten Differenz der ASCII-Werte der Zeichen berechnet wird.

Fazit

Diese Frage ist ein gutes Beispiel dafür, wie einfache String-Manipulation und Zwei-Zeiger-Techniken ein relativ komplexes Problem lösen können. Die Kenntnis dieser Fragen hilft nicht nur bei der Kodierung von Vorstellungsgesprächen, sondern verbessert auch Ihre allgemeinen Fähigkeiten zur Problemlösung.

Das obige ist der detaillierte Inhalt vonMinimieren Sie die Ersetzung eines Zeichens durch den nächsten Buchstaben, wodurch die Zeichenfolge ein Palindrom wird. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!