数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
服装研究
法律研究不大于 N 且不包含 S 中任何数字的最大数字
寻找不大于给定数字 N 且不包含字符串 S 中任何数字的最大数字的挑战是一个涉及字符串操作和数论的问题。目标是确定小于或等于 N 的最大可能数字，同时排除字符串 S 中找到的所有数字。
例如，考虑 N 等于 1000 且 S 等于“42”的情况。在这种情况下，不大于 N 且不包含 S 中任何数字的最大数字将是 999。这是因为 999 是可以使用数字 0、1、3、5、6、7、8 和 9（不包括字符串 S 中的数字 4 和 2）形成的最大可能数字。
可以使用不同的方法来解决此问题，例如遍历直到 N 的所有数字并验证其数字是否不存在于 S 中，或者使用更复杂的方法，例如动态规划或回溯法。
算法
步骤 1 - 我们将在 main() 函数中声明名为“N”和“S”的两个字符串变量。
步骤 2 - 我们将把这两个变量作为参数传递给 LargestNumberFinder() 函数。
步骤 3 - 我们将隐式地将字符串数字 N 和 S 转换为整数，以进行比较等数学运算。
步骤 4 - 我们将手动或通过创建每次都执行相同操作的函数来删除存储在 N 中的数字中的前导 0。
步骤 5 - 然后，我们将开始比较两个字符串的数字，找出不大于“N”且不包含字符串“S”中任何数字的最大数字。
方法 1：- 简单方法
使用另一个字符串中存在的所有数字在给定字符串中查找最大数字的基本方法如下。main 函数声明变量并调用 LargestNumberFinder 函数。此函数以两个字符串作为输入，检查小于 N 的每个值是否在其所有数字都存在于字符串 S 中。如果满足条件，则以字符串格式返回该值。attendance 函数用于确定存储在“i”中的值是否属于字符串 S，同时将 S 转换为整数数据类型。输入字符串转换为整数，并使用循环来评估条件。代码输出给定字符串中具有所有数字都存在于另一个字符串中的最大数字。
示例
该代码是一个解决方案，它查找小于 N（输入字符串转换为整数）的最大数字，该数字由字符串 S 中找到的数字组成。该代码使用两个函数“attendance”和“LargestNumberFinder”来确定和返回最大数字。“attendance”函数以整数“i”和字符串“s”作为输入，检查存储在“i”中的值是否属于字符串“s”，并将“s”转换为整数数据类型。“LargestNumberFinder”函数以两个字符串“x”和“s”作为输入，将“x”转换为整数，然后使用“attendance”函数检查小于 N 的每个值是否所有数字都存在于“s”中。main 函数声明变量并调用 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);
}
输出
77777
方法 2：- 高效方法
查找通过用给定字符串 S 的数字替换给定数字字符串 N 的数字可以形成的最大可能数字的第二种方法是一种高效的方法。这种方法首先检查 S 中是否存在 N 的每个数字，并用 S 中不存在的最大数字替换找到的第一个数字。然后用 S 中不存在的最大数字替换其余的数字。然后删除前导零，并将结果作为最大可能数字返回。这种方法比以前的方法更有效，因为它不需要对字符串进行排序。
示例
该代码解决了查找可以从给定字符串“N”中形成的最大数字的问题，方法是用字符串“S”中不存在的最大数字替换一个数字。该代码使用一种高效的方法来解决该问题。“LargestNumberFinder”函数接受两个字符串输入“num”和“s”，并返回最大可能的数字。向量“vis_s”用于存储字符串“s”的值。代码首先识别字符串“num”的第一个属于字符串“s”的数字。然后它用字符串“s”中不存在的最大数字交换该数字。然后代码查找字符串“s”中找不到的最大数字，并用该数字替换字符串“num”中的其余数字。从最终字符串中删除前导零，如果字符串为空，则函数返回“0”。该代码通过使用输入“N”和“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;
}
输出
149999
结论
通过这篇文章，我们更深入地了解了此类问题背后的原因，并理解了有助于我们将这些基本概念用于文章开头提到的主要现实生活问题的概念。例如，在我们的代码中，我们分别处理每个问题，然后像一件精美的工艺品一样将代码缝合在一起，类似地，我们将使用这个概念并尝试逐一解决问题。我们通常会从简单的方法开始，但我们会敏锐地关注并努力找到更有效的方法。谁知道，在阅读这篇文章之后，你会找到更好、更有效的方法，并进一步简化解决方案。因此，让我们坚持我们对思维和编码能力的信念，同时我们告别。
110 次浏览
