Mindestanzahl an Zügen, die erforderlich sind, um ein String-Palindrom zu erstellen, indem alle Zeichen des Teilstrings erhöht werden

Im Bereich Informatik und Programmierung ist es sehr wichtig, effiziente Algorithmen zur Lösung von Problemen zu entdecken. Ein interessantes Problem besteht darin, die Mindestanzahl von Operationen zu ermitteln, die erforderlich sind, um eine Zeichenfolge in ein Palindrom umzuwandeln, indem alle Zeichen in der Teilzeichenfolge hinzugefügt werden. In diesem Artikel werden zwei Möglichkeiten zur Lösung dieses Problems mithilfe der Programmiersprache C++ untersucht.

Grammatik

Bevor wir uns mit diesen Methoden befassen, definieren wir die Syntax der Funktionen, die wir verwenden werden −

int minMovesToMakePalindrome(string str);

Algorithmus

• Unser Ziel ist es, die Anzahl der Züge bei der Umwandlung eines Strings in ein Palindrom zu minimieren – dieses Problem wird von unserem Algorithmus durch die folgenden Schlüsselschritte gelöst: −

• Erstellen Sie zunächst zwei Zeigervariablen auf beiden Seiten der Zeichenfolge. Der linke Zeiger beginnt am Anfang der Zeichenfolge und der rechte Zeiger beginnt am Ende der Zeichenfolge.

• Setzen Sie unseren Prozess fort, solange es die Konfigurationsgrenzen zulassen, d. h. sobald einer der Zeiger den anderen Stopp überschreitet −

• Immer wenn die Zeichenwerte gleich sind, bewegen Sie die beiden Zeiger immer näher zusammen. Immer wenn sich die Zeichenwerte unterscheiden, wird der Zeichenwert auf der rechten Seite erhöht (entsprechend ihrer Differenz), bevor weitere Operationen ausgeführt werden. Dieser Anstieg ist proportional zur Differenz zwischen 'a' und 'c'. Wenn also str[right] gleich 'c' und str[left] gleich 'a' ist, erhöhen wir str[right] um 2 (weil 'a '- 'c'=2). Aktualisieren Sie die Anzahl der Bewegungen entsprechend.

• Sobald die linke Seite größer als die rechte Seite ist, wird die Zeichenfolge zu einem Palindrom.

Methode 1: Brute-Force-Cracking

Bei dieser Methode berücksichtigen wir alle möglichen Teilzeichenfolgen und berechnen die minimale Anzahl an Zügen, die für jede Teilzeichenfolge erforderlich sind. Zum Schluss geben wir das Minimum aller berechneten Züge zurück.

Beispiel

#include <iostream>
#include <string>
using namespace std;

int minMovesToMakePalindrome(string str) {
   int moves = 0;
   int length = str.length();

   for (int i = 0; i < length / 2; i++) {
      moves += abs(str[i] - str[length - i - 1]);
   }

   return moves;
}

int main() {
   string str = "abcde";
   int minMoves = minMovesToMakePalindrome(str);
   cout << "Minimum moves to make the string palindrome: " << minMoves << endl;

   return 0;
}

Ausgabe

Minimum moves to make the string palindrome: 6

Erklärung

Erklärung

Es wurde eine Funktion namens minMovesToMakePalindrome erstellt, die die Eingabezeichenfolge str in ein Palindrom mit der minimal erforderlichen Anzahl von Zügen umwandelt. Wie es funktioniert, erklären wir mit einigen Schritt-für-Schritt-Anleitungen:

Wir initialisieren die Moves-Variable auf 0, die für die Verfolgung der Gesamtzahl der erforderlichen Moves verantwortlich ist. - Da die Längenvariable die Länge des Eingabestrings str aufzeichnet, besteht unser nächster Schritt darin, eine for-Schleife zu verwenden, um die Hälfte des Strings zu iterieren, damit sich die symmetrischen Positionen nicht überlappen. - Abschließend berechnet abs(str[i] - str[length - i - 1]) innerhalb dieser Schleife die absolute Differenz zwischen den beiden Endzeichen.

Die berechnete Differenz stellt die Anzahl der Züge dar, die erforderlich sind, um die Charaktere an diesen Positionen gleich zu machen. Wir addieren diese Differenz zur Zuganzahl.

Nachdem wir alle erforderlichen Positionen durchlaufen haben, speichern wir die erforderliche Mindestanzahl an Zügen in der Variablen „moves“. Wir geben diesen Wert zurück.

In der Hauptfunktion initialisieren wir einen String str mit dem Wert „abcde“. Dann rufen wir die Funktion minMovesToMakePalindrome auf und übergeben str als Parameter. Die minimale Anzahl zurückgegebener Züge wird in der Variablen minMoves gespeichert. Abschließend drucken wir die Ergebnisse auf der Konsole aus.

Methode 2: Die optimale Doppelzeigermethode

Diese Methode verwendet zwei Zeiger, um gleichzeitig von beiden Enden der Zeichenfolge aus zu durchlaufen. Aus Effizienzgründen haben wir eine Technik zum Konvertieren einer Zeichenfolge in ein Palindrom verwendet, bei der nach und nach Zeichen von beiden Enden der Eingabe hinzugefügt und abgeglichen werden. Dieser Ansatz minimiert unnötige Vorgänge und ermöglicht schnellere Konvertierungen ohne Kompromisse bei der Genauigkeit oder Funktionalität.

Beispiel

#include <iostream>
#include <string>
using namespace std;

int minMovesToMakePalindrome(string str) {
   int moves = 0;
   int left = 0;
   int right = str.length() - 1;

   while (left <= right) {
      moves += abs(str[right] - str[left]);
      left++;
      right--;
   }

   return moves;
}

int main() {
   string str = "abcde";
   int minMoves = minMovesToMakePalindrome(str);
   cout << "Minimum moves to make the string palindrome: " << minMoves << endl;

   return 0;
}

Ausgabe

Minimum moves to make the string palindrome: 6

Erklärung

Erklärung

Das Ziel des folgenden Codebeispiels besteht darin, den optimalen Zwei-Zeiger-Ansatz zu verwenden, um die minimale Anzahl von Zügen zu bestimmen, die erforderlich sind, um eine bestimmte Zeichenfolge in ein Palindrom umzuwandeln.

Um dies zu erreichen, haben wir eine Funktion namens minMovesToMakePalindrome erstellt. Diese Funktion akzeptiert ein Zeichenfolgenargument und gibt die Gesamtzahl der erforderlichen Züge zurück. Zuerst setzen wir die Variable, die zum Zählen der Anzahl der Bewegungen verwendet wird, auf 0 und initialisieren den linken und rechten Zeiger: Der linke Zeiger beginnt am Anfang der Eingabezeichenfolge (Index 0) und der rechte Zeiger beginnt am Ende (Index str. Länge() - 1).

Unsere while-Schleife iteriert, bis left größer oder gleich right ist, um alle Elemente in der Zeichenfolge abzudecken. In jeder Iteration ermitteln wir den Unterschied zwischen den Zeichen an der linken und rechten Position mithilfe von abs(str[right] - str[left]), das angibt, wie viele Bewegungen erforderlich sind, um diese beiden Zeichen gleich zu machen. Wir addieren diesen Differenzwert zu unserem Laufzähler, um die Gesamtzahl der Züge zu erhalten.

Wenn wir uns der Mitte der Eingabezeichenfolge nähern, erhöhen Sie den linken Zeiger und verringern Sie den rechten Zeiger. Sobald es keine Überlappung zwischen dem linken und dem rechten Zeiger gibt, konvertieren wir die Zeichenfolge in ein Palindrom.

An diesem Punkt geben wir unsere Anzahl der in „moves“ gespeicherten Gesamtbewegungen zurück. In main() werden identische Schritte wie zuvor ausgeführt, wobei wir eine neue Eingabezeichenfolge „abcde“ deklarieren, die minMovesToMakePalindrome mit diesem Argument aufruft, die den Gesamtwert der minimalen Bewegungsanzahl zurückgibt der neuen Variablen „minMoves“ zugewiesen, bevor dieser Wert auf der Konsole ausgegeben wird.

Fazit

Im folgenden Text werden zwei Alternativen vorgestellt, die darauf abzielen, Einblicke und mögliche Antworten auf die Hürde zu geben, die bei der Berechnung der Anzahl der Züge erforderlich ist, um eine bestimmte Zeichenfolge in ein Palindrom in einer Teilzeichenfolge über Zeichenoperationen umzuwandeln. Eine Methode, die sogenannte Brute-Force-Methode, umfasst alle möglichen Teilzeichenfolgen, während die andere Methode, die sogenannte optimale Zwei-Zeiger-Methode, die Anzahl der erforderlichen Bewegungen erheblich reduziert. Programmierer können diese Mechanismen leicht anwenden, um ähnliche Hindernisse zu lösen und ihre Lösungen zu verbessern.

Das obige ist der detaillierte Inhalt vonMindestanzahl an Zügen, die erforderlich sind, um ein String-Palindrom zu erstellen, indem alle Zeichen des Teilstrings erhöht werden. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!