不超過N且不包含S中任何數字的最大數字

The challenge of finding the largest number not exceeding a given number N and not containing any of the digits in a string S is a problem that involves string manipulation and number theory. The goal isblem that involves string manipulation and number theory. The goal is to determine the greatest possible number that is less than or equal to N while also excluding all of the digits found in the string S.

例如，考慮一個情景，其中N等於1000，S等於"42"。在這種情況下，最大的不超過N且不包含S中任何數字的數是999。這是因為999是使用數字0、1、3、5、6、7、8和9組成的最大可能數，而不包括字串S中的數字4和2。

Different approaches can be used to solve this problem, such as iterating through all numbers up to N and verifying if their digits are not present in S, or by utilizing more complex method

Algorithm

步驟 1 − 我們將在main()函數中宣告兩個名為‘N’和‘S’的字串變數。

第二步 - 我們將這兩個變數當作參數傳遞給LargestNumberFinder()函數。

Step 3 − We will convert the string number N and S into integer implicitly to do mathematical operations such as comparision.

步驟 4 - 我們將手動刪除儲存在 N 中的數字中的前導 0，或透過建立一個每次都會執行相同操作的函數來刪除它們。

Step 5 − Then, we will start comparing the digits of the both the strings and finding out which is the largest number formed not more than 'N' that doesn't contain any digit from string ' S'.

Approach 1: - Naïve Approach

使用另一個字串中的所有數字來尋找給定字串中最大的數字的基本方法如下。主函數宣告變數並呼叫LargestNumberFinder函數。函數以兩個字串作為輸入，檢查每個小於N的值，該值在字串S中具有所有的數字。如果滿足條件，則以字串格式傳回該值。 attendance函數用於確定儲存在'i'中的值是否為字串S的一部分，同時將S轉換為整數資料類型。輸入字串被轉換為整數，並使用循環來評估條件。程式碼輸出在給定字串中具有所有數字的最大數值，該數值在另一個字串中也存在。

Example

的翻譯為：

範例

該程式碼是一個解決方案，它找到比N（輸入字串轉換為整數）小的最大數字，該數字由字串S中的數字組成。該程式碼利用兩個函數，'attendance'和'LargestNumberFinder'來確定並返回最大數字。 attendance函數以整數'i'和字串's'作為輸入，檢查儲存在'i'中的值是否為字串's'的一部分，並將's'轉換為整數資料型別。 LargestNumberFinder函數以兩個字串'x'和's'作為輸入，將'x'轉換為整數，然後使用attendance函數檢查所有小於N且所有數字都在's'中的值。主函數宣告變數並呼叫LargestNumberFinder函數，該函數將最大數字作為字串傳回。

#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);
}

Output

#

77777

方法2：高效方法

對於問題2的解決方案，即透過將給定數字字串N的數字替換為給定字串S的數字，得到最大可能的數字，這是一種高效的方法。此方法首先檢查S中是否存在N的每個數字，並以S中不在N中的最大數字取代第一個在S中找到的數字。然後，其餘的數字將被替換為S中不在N中的最大數字。然後去掉前導零，並將結果作為最大可能的數字回傳。這種方法比之前的方法更有效率，因為它不需要對字串進行排序。

Example

的翻譯為：

範例

The code solves a problem of finding the greatest number that can be formed from a given string "N" by replacing a digit with the highest digit not present in the string "S". The code utilizes highest digit not present in the string "S"。 problem. The LargestNumberFinder function takes two string inputs, "num" and "s", and returns the largest possible number. The vector "vis_s" is utilized to store the values of string "s". The code first identifies the first diifies the first git string "num" that is part of string "s". Then it swaps that digit with the highest digit not present in string "s". The code then finds the highest digit not found in string "s" and replaces the rest of theplaces the rest of the digits in string "num" with that digit. The leading zeros are removed from the final string, and if the string is empty, the function returns "0". The code outputs the result by calling the function with inputs "N" and " 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

结论

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

以上是不超過N且不包含S中任何數字的最大數字的詳細內容。更多資訊請關注PHP中文網其他相關文章！