不超过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 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 methods like dynamic programming or backtracking.

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 an efficient method to solve the 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 digit of 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 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中文网其它相关文章！