Mindestanzahl von Swaps zwischen zwei Strings, sodass ein String unbedingt größer als der andere ist

In diesem Artikel besprechen wir ein interessantes Problem der String-Manipulation: „Die minimale Anzahl von Austauschvorgängen, die zwischen zwei Strings erforderlich sind, sodass ein String unbedingt größer als der andere ist“. Wir werden das Problem verstehen, Lösungsstrategien detailliert beschreiben, es in C++ implementieren und Konzepte anhand eines relevanten Beispiels verdeutlichen.

Die Problemstellung verstehen

Angesichts zweier Zeichenfolgen gleicher Länge besteht unser Ziel darin, die Mindestanzahl an Zeichenaustauschvorgängen zu bestimmen, die erforderlich sind, um eine Zeichenfolge unbedingt größer als die andere zu machen. Zeichen werden zwischen den beiden Zeichenfolgen ausgetauscht, wobei jeder Austausch ein Zeichen aus beiden Zeichenfolgen betrifft. Zeichenfolgen werden lexikografisch verglichen, wobei „a“

Methode

Die Idee ist, einen gierigen Algorithmus zu verwenden. Wir beginnen am Anfang der Zeichenfolge und vertauschen sie für jede Position, wenn das Zeichen in der ersten Zeichenfolge kleiner als das entsprechende Zeichen in der zweiten Zeichenfolge ist. Wenn sie gleich sind, suchen wir nach dem größeren Zeichen in der zweiten Zeichenfolge, das ausgetauscht werden soll. Wenn kein solches Zeichen gefunden wird, fahren wir mit der nächsten Position fort. Wir wiederholen diesen Vorgang, bis alle Zeichen im String verarbeitet wurden.

Beispiel

Lassen Sie uns diesen Ansatz in C++ implementieren -

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

int minSwaps(string &s1, string &s2) {
   int swaps = 0;
   int n = s1.size();
   for(int i=0; i<n; i++) {
      if(s1[i] < s2[i]) {
         swap(s1[i], s2[i]);
         swaps++;
      }
      else if(s1[i] == s2[i]) {
         for(int j=i+1; j<n; j++) {
               if(s2[j] > s1[i]) {
                  swap(s1[i], s2[j]);
                  swaps++;
                  break;
               }
         }
      }
   }
   return (s1 > s2) ? swaps : -1;
}

int main() {
   string s1 = "bbca";
   string s2 = "abbc";
   int swaps = minSwaps(s1, s2);
   if(swaps != -1)
      cout << "Minimum swaps: " << swaps << "\n";
   else
      cout << "Cannot make string 1 greater\n";
   return 0;
}

Ausgabe

Minimum swaps: 2

Testfälle

Betrachten wir die Zeichenfolgen „bbca“ und „abbc“. Der folgende Austausch wird stattfinden: −

• Ersetzen Sie „b“ in der ersten Zeichenfolge durch „a“ in der zweiten Zeichenfolge. Die Zeichenfolgen lauten jetzt „bbac“ und „abbc“.

• Tauschen Sie das „c“ in der ersten Saite mit dem „b“ in der zweiten Saite. Die Zeichenfolgen lauten jetzt „bbcb“ und „abac“.

„bbcb“ ist lexikographisch größer als „abac“. Daher beträgt die erforderliche Mindestanzahl an Swaps 2 und die Ausgabe des Programms lautet „Mindestanzahl an Swaps: 2“.

Fazit

In diesem Artikel untersuchen wir das Problem der Bestimmung der Mindestanzahl an Swaps, die zwischen zwei Zeichenfolgen erforderlich sind, sodass eine Zeichenfolge lexikografisch größer ist als die andere. Wir diskutieren Strategien zur Lösung des Problems, implementieren es in C++ und erläutern das Konzept anhand von Beispielen. Fragen zur String-Manipulation wie diese kommen häufig in Interviews und bei Wettbewerbsprogrammen vor, und das Verständnis dieser Konzepte ist sehr hilfreich.

Das obige ist der detaillierte Inhalt vonMindestanzahl von Swaps zwischen zwei Strings, sodass ein String unbedingt größer als der andere ist. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!