C++-Programm: Finden Sie die längste Teilfolge von Zahlen mit der gleichen Links- und Rechtsdrehung

In diesem Problem müssen wir die maximale Länge der Teilsequenz bei gleicher Links- und Rechtsdrehung ermitteln. Linksdrehung bedeutet, dass alle Zeichen in der Zeichenfolge nach links verschoben werden und das erste Zeichen am Ende verschoben wird. Rechtsdrehung bedeutet, dass alle Zeichen der Zeichenfolge nach rechts und das letzte Zeichen an den Anfang verschoben werden.

Problemstellung – Wir erhalten eine Zeichenfolge str mit Zahlen und müssen eine Teilfolge maximaler Länge mit derselben Links- und Rechtsdrehung finden.

Beispiel

Geben Sie -str="323232",

ein

Ausgabe– 6

Erklärung – Die längste Teilsequenz mit der gleichen Links- und Rechtsdrehung ist „323232“. Drehen Sie es nach links auf „232323“ und nach rechts auf „232323“.

Geben Sie -str = ‚00010100‘

ein

Ausgabe– 6

Erklärung – Die längste Teilsequenz mit gleicher Links- und Rechtsdrehung ist „000000“.

Geben Sie -str = ‘092312110431010’

ein

Ausgabe– 6

Erklärung – Es gibt 2 mögliche Teilfolgen der Länge 6 mit gleicher Links- und Rechtsdrehung. Die erste ist „010101“ und die zweite ist „101010“.

Methode 1

In dieser Methode finden wir alle möglichen Teilfolgen der angegebenen Zeichenfolge. Danach prüfen wir, ob die Links- und Rechtsdrehung der Saite gleich ist. Wir werden eine rekursive Methode verwenden, um alle möglichen Teilfolgen zu finden.

Algorithmus

• Initialisieren Sie die globale Variable „maxLen“ auf Null, um die Länge der längsten Teilsequenz mit der gleichen Links- und Rechtsdrehung zu speichern.

• Definieren Sie die Funktion isRightSameLeft(), um zu prüfen, ob die Links- und Rechtsdrehungen der Zeichenfolge gleich sind.

• Verwenden Sie innerhalb der Funktion die Methode substr(), um die Zeichenfolge nach links und rechts zu drehen.

Die Funktion

• getAllSubSeq() wird verwendet, um alle möglichen Teilsequenzen einer bestimmten Zeichenfolge zu finden.

• Basisfall definieren. Wenn str leer ist, erhalten wir die Teilsequenz und führen die Funktion isRightSameLeft() aus, um zu prüfen, ob die Teilsequenz die gleiche Links- und Rechtsdrehung aufweist. Wenn ja, aktualisieren Sie den Wert der Variablen „maxLen“, wenn ihre Länge größer als der aktuelle Wert von „maxLen“ ist.

• Führen Sie einen rekursiven Aufruf durch, nachdem Sie das erste Zeichen aus „str“ entfernt und die Zeichenfolge „out“ angehängt haben.

• Nachdem Sie das erste Zeichen entfernt und die Zeichenfolge „out“ unverändert gelassen haben, führen Sie einen weiteren rekursiven Funktionsaufruf durch. Bei diesem rekursiven Aufruf schließen wir das erste Zeichen von „str“ aus.

Beispiel

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

// Defining global variable to store the length of the longest subsequence according to the given condition
int maxLen = 0;
//  function to check if the string is the same after the left rotation
bool isRightSameLeft(string str) {
   int len = str.length();
   return str.substr(1, len - 1) + str[0] == str[len - 1] + str.substr(0, len - 1);
}
// function to get all subsequences of a string
void getAllSubSeqs(string str, string out) {
   // If the string is empty, we get the subsequences. Check if its left and right rotation is the same
   if (str.empty()) {
      if (isRightSameLeft(out))
          maxLen = max(maxLen, (int)out.length());
      return;
   }
   // Recursive case remove the first character from str, and add it to the output
   getAllSubSeqs(str.substr(1), out + str[0]);
   // remove the first character from str, and drop it
   if (str.length() > 1)
      getAllSubSeqs(str.substr(1), out);
}
int main() {
   string str = "323232";
   string out = "";
   getAllSubSeqs(str, out);
   cout << "The longest subsequence of str having same left and right rotation is " << maxLen;
   return 0;
}

Ausgabe

The longest subsequence of str having same left and right rotation is 6

Zeitkomplexität – O(N*2N). Hier O(N) zum Vergleichen von Links- und Rechtsdrehungen und O(2N) zum Finden aller möglichen Teilfolgen.

Raumkomplexität – O(1), da wir keinen zusätzlichen Raum verbrauchen.

Methode 2

Hier haben wir die obige Methode optimiert. Wir können die Lösung der Beispieleingabe beobachten. Links- und Rechtsdrehungen einer Teilsequenz sind nur dann gleich, wenn die Teilsequenz dasselbe Zeichen oder abwechselnd zwei verschiedene Zeichen enthält und eine gleichmäßige Länge hat.

Algorithmus

• Verwenden Sie zwei verschachtelte Schleifen, um zwei beliebige Zahlen zu kombinieren.

• Definieren Sie die Variable „cnt“, um die Länge einer Teilsequenz zu ermitteln, die abwechselnd zwei Zahlen enthält, und initialisieren Sie sie auf Null.

• Definieren Sie eine boolesche „erste“ Variable, um zu verfolgen, ob das nächste Zeichen das i-te oder j-te Zeichen sein soll.

• Verwenden Sie eine Schleife, um die Zeichenfolge zu durchlaufen.

• Wenn first == true und str[k] - '0' == I, wechseln Sie den Wert von 'first' ab und erhöhen Sie 'cnt' um 1.

• Wenn first == false und str[k] - '0' == j, wechseln Sie den Wert von 'first' erneut und erhöhen Sie 'cnt' um 1.

• Wenn i und j nicht gleich sind und der „cnt“-Wert ungerade ist, dekrementieren Sie ihn um 1.

• Wenn der cnt-Wert größer als „res“ ist, aktualisieren Sie den Wert der Variablen „res“.

Beispiel

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

int getLongSubSeq(string str) {
   // Store the length of the string
   int len = str.size(), res = 0;
   // Traverse the all possible combination of two digits
   for (int i = 0; i < 10; i++) {
      for (int j = 0; j < 10; j++) {
          // to store the length of an alternating sequence of the current combination
          int cnt = 0;
          // to track the turn of the ith or jth digit
          bool first = true;
          // traverse the string
          for (int k = 0; k < len; k++) {
              // If the current digit is equal to I, and the first is true, increment the count
              if (first == true and str[k] - '0' == i) {
                  first = false;
                  cnt++;
              } else if (first == false and str[k] - '0' == j) {
                  // If the current digit is equal to j, and the first is false, increment the count
                  first = true;
                  cnt++;
              }
          }
          // If the sequence is odd and i and j are different, decrement the count
          if (i != j and cnt % 2 == 1)
              cnt--;
          // Update the answer
          res = max(cnt, res);
       }
   }
   return res;
}
int main() {
   string str = "00010100";
   cout << "The longest subsequence of str having same left and right rotation is " << getLongSubSeq(str);
   return 0;
}

Ausgabe

The longest subsequence of str having same left and right rotation is 6

Zeitkomplexität – O(10*10*N), weil wir Teilfolgen aus Zeichenfolgen finden, die Zahlenkombinationen enthalten.

Raumkomplexität – O(1), da wir keinen dynamischen Raum verwenden.

Dieses Tutorial zeigt uns zwei Methoden, um die längste Teilsequenz zu finden, die die gleiche Links- und Rechtsdrehung enthält. Die erste Methode ist die einfache Methode, die sehr zeitaufwändig ist und wir sie nicht für große Eingaben verwenden können.

Die zweite Methode ist optimiert und ihre zeitliche Komplexität entspricht nahezu O(N).

Das obige ist der detaillierte Inhalt vonC++-Programm: Finden Sie die längste Teilfolge von Zahlen mit der gleichen Links- und Rechtsdrehung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!