Mindestanzahl benachbarter Swaps, die erforderlich sind, um eine Zeichenfolge umzukehren

Bei einer gegebenen Zeichenfolge str können wir die Zeichenfolge umkehren, indem wir einfach benachbarte Zeichen austauschen. Wir müssen die Mindestanzahl an Zügen ermitteln, die erforderlich sind, um die Zeichenfolge umzukehren, indem wir einfach benachbarte Zeichen vertauschen. Wir werden zwei Methoden implementieren, um die erforderliche Lösung zu finden und eine Erklärung und Implementierung des Codes bereitzustellen.

Beispiel Beispiel

Input1: string str1 = “shkej”

Output: 10

Die chinesische Übersetzung von

Erklärung

lautet:

Erklärung

Zuerst verschieben wir das letzte Zeichen an die erste Position, was 4 Swaps erfordert, und dann wird die Zeichenfolge zu „jshke“. Dann verschieben wir das „e“ an die zweite Position, was drei Tauschvorgänge erfordert. Ebenso benötigen wir für „k“ zwei Swaps, während für „h“ nur 1 Swap erforderlich ist und die endgültige Antwort 10 ist.

Input2: string str1 = “abace”

Output: 6

Die chinesische Übersetzung von

Erklärung

lautet:

Erklärung

Zuerst tauschen wir das Zeichen am 2. Index aus und verschieben es zum letzten Index. Dies erfordert 2 Tauschvorgänge und die Zeichenfolge wird zu „abcea“. Dann tauschen wir „b“ gegen „e“, es sind 2 Tauschvorgänge erforderlich und die Zeichenfolge wird zu „aceba“. Führen Sie dann zwei weitere Austausche durch, um die endgültige umgekehrte Zeichenfolge zu erhalten, was insgesamt 6 Austausche erfordert.

Die chinesische Übersetzung von „Naiver Ansatz“ lautet: „Naiver Ansatz“.

Wir haben uns das obige Beispiel angesehen. Schauen wir uns nun die Schritte an, die zur Implementierung des richtigen Codes erforderlich sind.

Zunächst erstellen wir eine Funktion, die die angegebene Zeichenfolge als Parameter verwendet und die erforderliche Mindestanzahl an Schritten als Rückgabewert zurückgibt.

• In dieser Funktion erstellen wir eine Kopie der Zeichenfolge und kehren sie dann um, um sie mit der Originalzeichenfolge zu vergleichen.

• Wir werden drei Variablen erstellen, die ersten beiden werden zum Durchlaufen der Zeichenfolge verwendet und die letzte wird zum Speichern der erforderlichen Anzahl von Schritten verwendet.

• Mithilfe einer While-Schleife durchlaufen wir die angegebene Zeichenfolge und überspringen weiterhin so viele Iterationen wie der aktuelle Indexwert, um die Zeichenfolge umzukehren.

• Dann verwenden wir eine While-Schleife, um benachbarte Zeichen auszutauschen, bis „j“ „i“ erreicht, und erhöhen die Anzahl bei jedem Austausch.

• Abschließend geben wir den Wert der Zählung zurück und geben ihn in der Hauptfunktion aus.

• Beispiel

  #include <bits/stdc++.h>
  using namespace std;
  // function to get the minimum number of swaps 
  int minSwaps(string str){
     string temp = str;
     reverse(temp.begin(), temp.end()); // reversing the string 
     int i = 0, j = 0;
     int ans = 0;
     int len = str.size();
     while (i <len) {
        j = i;		
        // find the character that is equal to the current element 
        while (str[j] != temp[i]) {
           j++;
        }
        // iterating util the current i is equal to j
        while (i < j) {
           char tempc = str[j];
           str[j] = str[j - 1];
           str[j - 1] = tempc;
           j--;
           ans++;
        }
        i++;
     }
     return ans;
  }
  int main(){
     string str = "efabc"; // given string     
     // calling the function to find the minimum number of steps required 
     cout<<"The minimum number of steps required to reverse the given string by swapping the adjacent characters is "<<minSwaps(str)<<endl;
     return 0;
  }
  

Ausgabe

The minimum number of steps required to reverse the given string by swapping the adjacent characters is 10

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität des obigen Codes beträgt O(N^2), wobei N die Länge der angegebenen Zeichenfolge ist. Wir verwenden verschachtelte While-Schleifen, um während der Iteration Faktoren von N anzugeben. Die räumliche Komplexität des obigen Codes beträgt O(N), da wir dort eine zusätzliche Zeichenfolge erstellen, um die Inversion der angegebenen Zeichenfolge zu speichern.

Hinweis

– Ein alternativer Ansatz ist hier möglich, erfordert jedoch die Verwendung sehr fortgeschrittener Datenstrukturen. Das Konzept dieser Methode besteht darin, dass wir beim letzten Zeichen beginnen und prüfen können, bis das erste Zeichen die Bedingung erfüllt. Dann könnten wir theoretisch dieses Zeichen an die letzte Position verschieben, diese Position als abgeschlossen markieren und diesen Wert in einer Datenstruktur auf hoher Ebene speichern.

Dann finden wir für jedes Zeichen das gleiche Zeichen, das von hinten kommt und noch nicht markiert wurde, und erhöhen dann die Anzahl auf die Gesamtzahl der darauf folgenden Elemente abzüglich der Anzahl der markierten Elemente. Fazit

In diesem Tutorial haben wir einen Code implementiert, um die Mindestanzahl an Schritten zu ermitteln, die zum Umkehren einer bestimmten Zeichenfolge erforderlich sind, indem nur benachbarte Zeichen ausgetauscht werden. Wir haben verschachtelte While-Schleifen verwendet und die Kopie der angegebenen Zeichenfolge umgekehrt, um die Lösung zu finden. Die zeitliche Komplexität des obigen Codes beträgt O(N^2), wobei N die Größe der Zeichenfolge ist und die räumliche Komplexität O(N) ist.

Das obige ist der detaillierte Inhalt vonMindestanzahl benachbarter Swaps, die erforderlich sind, um eine Zeichenfolge umzukehren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!