Ordnen Sie die Zeichen in einer Zeichenfolge neu an, sodass zwei beliebige benachbarte Zeichen unterschiedlich sind. Dies ist in C++ implementiert

Wir erhalten eine Zeichenfolge. Vorausgesetzt, es handelt sich um str, kann die Länge einen beliebigen Wert haben. Die Aufgabe besteht darin, die gegebene Zeichenfolge so umzuordnen, dass in der resultierenden Zeichenfolge keine identischen benachbarten Zeichen aneinandergereiht sind.

Lassen Sie uns verschiedene Eingabe- und Ausgabeszenarien betrachten:

Eingabe − String str = "itinn"

Ausgabe − Ordnen Sie die Zeichen in der Zeichenfolge neu an, sodass zwei benachbarte Zeichen nicht gleich sind. Das Ergebnis für: initn.

Erläuterung − Wir erhalten eine Variable vom Typ String, vorausgesetzt, es ist str. Jetzt werden wir die Zeichen der Eingabezeichenfolge neu anordnen, sodass keine zwei identischen Zeichen an derselben Position erscheinen, d. h. „nn“ an eine nicht benachbarte Position verschieben. Das Endergebnis ist also Die Zeichenfolge wird „initn“ sein.

Eingabe − String str = "abbaabbaa"

Ausgabe − Die Zeichen in der Zeichenfolge werden neu angeordnet, sodass benachbarte Zeichen unterschiedlich sind: ababababa

Erklärung − Wir erhalten eine Variable vom Typ String, vorausgesetzt, es ist str. Jetzt ordnen wir die Zeichen der Eingabezeichenfolge neu an, sodass keine zwei gleichen Zeichen an derselben Position erscheinen, d. h. wir verschieben „bb“, „aa“, „bb“, „aa“, da sie gleich und benachbart sind. Die letzte Zeichenfolge wird also „ababababa“ sein.

Die im folgenden Programm verwendete Methode lautet wie folgt:

• Geben Sie eine Variable vom Typ String ein (angenommen, es handelt sich um str), berechnen Sie die Größe des Strings und speichern Sie ihn in einer Variablen mit dem Namen „length“.

• Überprüfen Sie, ob die Länge 0 ist, und kehren Sie dann zurück.

• Übergeben Sie die Daten an die Funktion Rearrangement(str, length).

• Innerhalb der Funktion Rearrangement(arr, length)

  • setzt die Größe der Zeichenfolge auf (Länge + 1)/2.

  • Deklarieren Sie eine Variable vom Vektortyp vec(26, 0), die Daten vom Typ Integer speichert, und einen Zeiger vom Typ String ptr(length, ‘ ‘). Deklarieren Sie außerdem eine temporäre Variable temp vom Typ Integer und dem Wert 0.

  • Beginnen Sie mit der FOR-Schleife, um str zu iterieren. Setzen Sie innerhalb der Schleife vec[it - ‚a‘]++.

  • Erstellen Sie eine Zeichentypvariable ch und setzen Sie sie auf das Ergebnis des Aufrufs der Maximum(vec)-Funktion.

  • Deklarieren Sie eine Variable total vom Typ Integer und setzen Sie sie auf vec[ch - ‚a‘].

  • Überprüfen Sie, ob die Gesamtsumme größer als die Größe ist, und kehren Sie dann zurück.

  • Beginnen Sie mit der Schleife von WHILE total, setzen Sie dann ptr[temp] auf ch, setzen Sie temp auf temp + 2 und dekrementieren Sie total um 1.

  • Setze vec[ch - 'a'] auf 0. Beginnen Sie mit der FOR-Schleife von i bis 0, bis i kleiner als 26 ist. Starten Sie innerhalb der Schleife die while-Schleife. Wenn vec[i] größer als 0 ist, setzen Sie temp auf (temp >= length) 1: temp, setzen Sie ptr[temp] auf 'a' + i, setzen Sie temp auf temp + 2 und dekrementiere vec[i] um 1.

  • Return ptr

• Innerhalb der Funktion char Maximum(const vector& vec)

  • deklarieren Sie eine Variable vom Typ Integer hoch und setzen Sie sie auf 0 und eine Variable vom Typ Zeichen c.

  • Beginnen Sie mit der FOR-Schleife von i nach 0, bis i kleiner als 26 ist. Überprüfen Sie innerhalb der Schleife, ob vec[i] kleiner als hoch ist, und setzen Sie dann hoch auf vec[i] und c auf „a“ + i.

  • Zurück zu c

• Ergebnisse drucken.

Beispiel

#include <bits/stdc++.h>
using namespace std;
char maximum(const vector<int>& vec){
   int high = 0;
   char c;
   for(int i = 0; i < 26; i++){
      if(vec[i] > high){
         high = vec[i];
         c = &#39;a&#39; + i;
      }
   }
   return c;
}
string Rearrangement(string str, int length){
   int size = (length + 1) / 2;
   vector<int> vec(26, 0);
   string ptr(length, &#39; &#39;);
   int temp = 0;
   for(auto it : str){
      vec[it - &#39;a&#39;]++;
   }
   char ch = maximum(vec);
   int total = vec[ch - &#39;a&#39;];
   if(total > size){
      return "";
   }
   while(total){
      ptr[temp] = ch;
      temp = temp + 2;
      total--;
   }
   vec[ch - &#39;a&#39;] = 0;
   for(int i = 0; i < 26; i++){
      while (vec[i] > 0){
         temp = (temp >= length) ? 1 : temp;
         ptr[temp] = &#39;a&#39; + i;
         temp = temp + 2;
         vec[i]--;
      }
   }
   return ptr;
}
int main(){
   string str = "itinn";
   int length = str.length();
   if(length == 0){
      cout<<"Please enter a valid string";
   }
   string count = Rearrangement(str, length);
   if(count == ""){
      cout<<"Please enter a valid string";
   }
   else{
      cout<<"Rearrangement of characters in a string such that no two adjacent are same is: "<<count;
   }
   return 0;
}

Ausgabe

Wenn wir den obigen Code ausführen, wird die folgende Ausgabe generiert

Rearrangement of characters in a string such that no two adjacent are same is: initn

Das obige ist der detaillierte Inhalt vonOrdnen Sie die Zeichen in einer Zeichenfolge neu an, sodass zwei beliebige benachbarte Zeichen unterschiedlich sind. Dies ist in C++ implementiert. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!