Die größte Zahl, die N nicht überschreitet und keine Zahl in S enthält

Die Herausforderung, die größte Zahl zu finden, die eine bestimmte Zahl N nicht überschreitet und keine der Ziffern in einer Zeichenfolge S enthält, ist ein Problem, das Zeichenfolgenmanipulation und Zahlentheorie erfordert. Das Ziel besteht darin, die größtmögliche Zahl zu bestimmen kleiner oder gleich N, wobei auch alle in der Zeichenfolge S.

gefundenen Ziffern ausgeschlossen werden

Stellen Sie sich zum Beispiel ein Szenario vor, in dem N gleich 1000 und S gleich „42“ ist. In diesem Fall ist die größte Zahl, die N nicht überschreitet und keine Ziffern in S enthält, 999. Dies liegt daran, dass 999 die größtmögliche Zahl ist, die aus den Ziffern 0, 1, 3, 5, 6, 7, 8 und 9 gebildet wird, mit Ausnahme der Ziffern 4 und 2 in der Zeichenfolge S.

Verschiedene Ansätze können verwendet werden, um dieses Problem zu lösen, z. B. das Durchlaufen aller Zahlen bis N und das Überprüfen, ob ihre Ziffern nicht in S vorhanden sind, oder die Verwendung komplexerer Methoden wie dynamische Programmierung oder Backtracking.

Algorithmus

Schritt 1 − Wir werden in der Funktion main() zwei String-Variablen mit den Namen „N“ und „S“ deklarieren.

Schritt 2 – Wir übergeben diese beiden Variablen als Parameter an die Funktion LargestNumberFinder().

Schritt 3 - Wir werden die Zeichenfolgennummern N und S implizit in Ganzzahlen umwandeln, um mathematische Operationen wie Vergleiche durchzuführen.

Schritt 4 – Wir entfernen die führenden Nullen aus den in N gespeicherten Zahlen, entweder manuell oder indem wir eine Funktion erstellen, die jedes Mal das Gleiche tut.

Schritt 5 - Dann beginnen wir mit dem Vergleichen der Ziffern beider Zeichenfolgen und finden heraus, welche die größte Zahl ist, die nicht mehr als „N“ bildet und keine Ziffer aus der Zeichenfolge „S“ enthält.

Ansatz 1: - Naiver Ansatz

Der grundlegende Weg, die größte Zahl in einer bestimmten Zeichenfolge mithilfe aller Zahlen in einer anderen Zeichenfolge zu finden, ist wie folgt. Die Hauptfunktion deklariert Variablen und ruft die LargestNumberFinder-Funktion auf. Diese Funktion verwendet zwei Zeichenfolgen als Eingabe und prüft jeden Wert kleiner als N, der alle Ziffern in Zeichenfolge S enthält. Wenn die Bedingung erfüllt ist, wird der Wert im String-Format zurückgegeben. Die Anwesenheitsfunktion wird verwendet, um zu bestimmen, ob der in „i“ gespeicherte Wert Teil einer Zeichenfolge S ist, während S in einen ganzzahligen Datentyp konvertiert wird. Die Eingabezeichenfolge wird in eine Ganzzahl umgewandelt und eine Schleife wird verwendet, um die Bedingung auszuwerten. Der Code gibt den Maximalwert aller Zahlen in einem bestimmten String aus, der auch in einem anderen String vorhanden ist.

Beispiel

wird übersetzt als:

Beispiel

Dieser Code ist eine Lösung, die die größte Zahl kleiner als N (in Ganzzahl umgewandelte Eingabezeichenfolge) findet, die aus den Ziffern in der Zeichenfolge S besteht. Der Code verwendet zwei Funktionen, „attendance“ und „LargestNumberFinder“, um die größte Zahl zu ermitteln und zurückzugeben. Die Anwesenheitsfunktion nimmt als Eingabe eine Ganzzahl „i“ und eine Zeichenfolge „s“, prüft, ob der in „i“ gespeicherte Wert Teil der Zeichenfolge „s“ ist, und konvertiert „s“ in einen ganzzahligen Datentyp. Die LargestNumberFinder-Funktion verwendet zwei Zeichenfolgen „x“ und „s“ als Eingabe, wandelt „x“ in eine Ganzzahl um und verwendet dann die Anwesenheitsfunktion, um alle Werte zu überprüfen, die kleiner als N sind und alle Zahlen in „s“ vorliegen. Die Hauptfunktion deklariert die Variable und ruft die LargestNumberFinder-Funktion auf, die die größte Zahl als Zeichenfolge zurückgibt.

#include <iostream>
#include <string>
#include <vector>

// function to check whether value stored in ‘i’ is part of string S while also converting S into integer data type.
bool attendance(int i, std::string s) {
   while (i) {
      int first_digit = i % 10;
      i /= 10;
      int t = std::stoi(s);
      bool found = false;
      while (t) {
         int second_digit = t % 10;
         t /= 10;
         if (second_digit == first_digit) {
            found = true;
            break;
         }
      }
      if (!found)
         return false;
   }
   return true;
}

// function to input two strings and check for each value less than N with all digits present in S.
std::string LargestNumberFinder(std::string x, std::string s) {
   int N = std::stoi(x);
   for (int i = N; i >= 1; i--) {
      if (attendance(i, s)) {
         return std::to_string(i);
      }
   }
   return "-1";
}

// main function to declare the variables and call the function.
int main() {
   std::string N = "100709";
   std::string S = "70";
   std::cout << LargestNumberFinder(N, S);
}

Ausgabe

77777

Methode 2: Effiziente Methode

Die Lösung für Problem 2, die darin besteht, die größtmögliche Zahl zu erhalten, indem die Ziffern der gegebenen numerischen Zeichenfolge N durch die Ziffern der gegebenen Zeichenfolge S ersetzt werden, ist ein effizienter Ansatz. Die Methode prüft zunächst, ob jede Zahl von N in S vorhanden ist, und ersetzt die erste in S gefundene Zahl durch die größte Zahl in S, die nicht in N enthalten ist. Die restlichen Zahlen werden dann durch die größte Zahl in S ersetzt, die nicht in N liegt. Anschließend werden führende Nullen entfernt und das Ergebnis als größtmögliche Zahl zurückgegeben. Diese Methode ist effizienter als die vorherige Methode, da die Zeichenfolge nicht sortiert werden muss.

Beispiel

wird übersetzt als:

Beispiel

Der Code löst das Problem, die Zahl zu finden, die aus einer gegebenen Zeichenfolge „N“ gebildet werden kann, indem er die größte Ziffer durch die höchste Ziffer ersetzt, die in der Zeichenfolge „S“ nicht vorhanden ist. Der Code verwendet eine effiziente Methode, um das Problem zu lösen. Die LargestNumberFinder-Funktion nimmt zwei Zeichenfolgeneingaben entgegen, „num“ und „s“, und gibt die größtmögliche Zahl zurück. Der Vektor „vis_s“ wird verwendet, um die Werte der Zeichenfolge „s“ zu speichern Zeichenfolge „num“, die Teil der Zeichenfolge „s“ ist, tauscht dann die höchste Ziffer aus, die in der Zeichenfolge „s“ nicht vorhanden ist, und ersetzt den Rest Ziffern in der Zeichenfolge „num“ mit dieser Ziffer. Die führenden Nullen werden aus der endgültigen Zeichenfolge entfernt. Wenn die Zeichenfolge leer ist, gibt der Code das Ergebnis aus, indem er die Funktion mit den Eingaben „N“ und „ S" .

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// function to check for all values of String N with String S and replacing the digit if found same with the largest possible digit not present in S.
string LargestNumberFinder(string num, string s) {
   vector<bool> vis_s(10, false);
   for (int i = 0; i < (int)s.size(); i++) {
      vis_s[int(s[i]) - 48] = true;
   }
   int n = num.size();
   int in = -1;
   for (int i = 0; i < n; i++) {
      if (vis_s[(int)num[i] - '0']) {
         in = i;
         break;
      }
   }
   if (in == -1) {
      return num;
   }
   for (char dig = num[in]; dig >= '0'; dig--) {
      if (vis_s[(int)dig - '0'] == 0) {
         num[in] = dig;
         break;
      }
   }
   char LargestDig = '0';
   for (char dig = '9'; dig >= '0'; dig--) {
      if (vis_s[dig - '0'] == false) {
         LargestDig = dig;
         break;
      }
   }
   for (int i = in + 1; i < n; i++) {
      num[i] = LargestDig;
   }
   int Count = 0;
   for (int i = 0; i < n; i++) {
      if (num[i] == '0')
         Count++;
      else
         break;
   }
   num.erase(0, Count);
   if ((int)num.size() == 0)
      return "0";
   return num;
}
int main() {
   string N = "161516";
   string S = "756";
   cout << LargestNumberFinder(N, S);
   return 0;
}

Output

149999

结论

通过这篇文章，我们更接近理解这些问题背后的原因，并理解了这些概念，这些概念将帮助我们在之前提到的重大实际问题中使用这些基本概念。就像在我们的代码中，我们分别解决每个问题，然后像制作美丽的手工品一样将代码缝合在一起，同样，我们将使用这个概念，尝试逐个解决问题。我们通常会从朴素的方法开始，但通过敏锐的眼光和努力，我们会找到更高效的方法。谁知道在阅读完这篇文章后，你会找到更好、更高效的方法，并进一步简化解决方案。所以，让我们坚持我们的信念和对思维和编码的信任，同时告别。

Das obige ist der detaillierte Inhalt vonDie größte Zahl, die N nicht überschreitet und keine Zahl in S enthält. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!