C++-Programm zum Entfernen von Zeichen aus einer numerischen Zeichenfolge, sodass diese durch 8 teilbar ist

Gegeben eine Zahl in Form einer Zeichenfolge, müssen wir herausfinden, wo wir sie nach dem Löschen von null oder mehr Elementen durch acht teilbar machen können. Mit anderen Worten, wir müssen herausfinden, ob es eine Teilfolge der Zeichenfolge gibt ist durch 8 teilbar. Geben Sie die geänderte Zeichenfolge oder -1 zurück, wenn dies nicht möglich ist.

Gemäß der Teilbarkeitsregel ist jede Zahl, deren letzte drei Ziffern durch 8 teilbar sind, auch durch 8 teilbar. Beispielsweise sind 56992992 und 476360 durch 8 teilbar, 2587788 jedoch nicht. Wenn das Ergebnis eine ganze Zahl ist, ist die ursprüngliche Zahl durch 8 teilbar.

Schauen wir uns einige Eingabeszenarien an, die die Methode im Detail erklären −

Wenn die an die Methode übergebene Eingabe eine numerische Zeichenfolge ist, die eine beliebige durch 8 teilbare Teilzeichenfolge enthält, können wir in der Ergebnisliste die durch 8 teilbare Teilzeichenfolge erhalten

Input: 2567992
Result: 56

Wenn die Eingabe in die Methode eine numerische Zeichenfolge ist, die keine durch 8 teilbare Teilzeichenfolge enthält, wird die Ausgabe als −

zurückgegeben

Input: 77777777777
Result: -1

Algorithmus

• Die String-Eingabe wird iteriert und überprüft, ob ein Teilstring ein Vielfaches von 8 ist.

• Wenn in der Eingabe eine Folgeteilzeichenfolge vorhanden ist, wird die Teilzeichenfolge als Ausgabe zurückgegeben.

• Wenn der Teilstring gefunden wird, bricht das Programm ab, andernfalls wiederholen Sie Schritt 2, bis der Teilstring gefunden ist.

• Wenn die Eingabe keinen Teilstring enthält, der durch 8 teilbar ist, ist die zurückgegebene Ausgabe -1.

Beispiel

Im folgenden C++-Programm nehmen wir zwei Zeichenfolgen, eine kann in eine durch 8 teilbare Zeichenfolge konvertiert werden, die andere nicht, und ermitteln jeweils die Ausgabe. Wir können von 0 bis 1000 in Vielfachen von 8 wie 0, 8, 16, 24, 32 ... 1000 iterieren und prüfen, ob diese Zahl als Teilfolge der angegebenen Zeichenfolge existiert.

#include <iostream>
using namespace std;
int checkIfSubstringExist(string req, string given) {
   int index = 0;
   for (char ch : given) {
      if (req[index] == ch) {
         index++;
      }
   }
   return index == (int)req.size();
}
string solve(string s) {
   for (int i = 0; i < 1e3; i += 8) {
      string num = to_string(i);
      if (checkIfSubstringExist(num, s)) {
         return num;
      }
   }
   return "-1";
}
int main() {

   // the string “95256” can be converted to a string divisible by 8
   // the string “74516” cannot be converted to a string divisible by 8
   // let’s run our code to find the output in each case
   string s1 = "95258", s2="74516";
   cout << solve(s1) << "\n" << solve(s2) << endl;
   return 0;
}

Ausgabe

8
16

Wie Sie in der obigen Ausgabe sehen können, wird 9525 von 95258 und 745 von 74516 entfernt, um die linke Zahl durch 8 teilbar zu machen.

Fazit

Wie wir sehen können, müssen wir nach einer einfachen Beobachtung nur prüfen, ob die Teilmenge existiert. Wir prüfen, ob die Zeichenfolge eine Teilsequenz enthält. Im schlimmsten Fall wird die gesamte Zeichenfolge überprüft. Wenn uns also eine numerische Zeichenfolge der Länge n gegeben wird, beträgt die Zeitkomplexität im ungünstigsten Fall O(126*n), was O(n) ist.

Das obige ist der detaillierte Inhalt vonC++-Programm zum Entfernen von Zeichen aus einer numerischen Zeichenfolge, sodass diese durch 8 teilbar ist. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!