Nを超えず、Sに数値を含まない最大の数

指定された数値 N を超えず、文字列 S にどの桁も含まれない最大の数値を見つけるという課題は、文字列操作と数論を伴う問題です。目標は次のとおりです。文字列 S.

で見つかったすべての数字を除外しながら、N 以下の可能な最大の数値を決定します。

たとえば、N が 1000、S が「42」であるシナリオを考えてみましょう。この場合、N を超えず、S に桁が含まれない最大の数値は 999 です。これは、999 が、文字列 S の数字 4 と 2 を除く、数字 0、1、3、5、6、7、8、9 を使用して形成される最大の数値であるためです。

この問題を解決するには、N までのすべての数値を反復処理してその桁が S に存在しないかどうかを確認するか、動的プログラミングやバックトラッキングなどのより複雑な方法を利用するなど、さまざまなアプローチを使用できます。

＃＃＃アルゴリズム＃＃＃

ステップ1

- main() 関数で「N」と「S」という名前の2つの文字列変数を宣言します。

ステップ 2

- これら 2 つの変数をパラメータとして LargestNumberFinder() 関数に渡します。

ステップ 3

-文字列番号 N と S を暗黙的に整数に変換して、比較などの数学的演算を実行します。 ステップ 4

- 手動で、または毎回同じことを行う関数を作成して、N に格納されている数値から先頭の 0 を削除します。

ステップ5

-次に、両方の文字列の桁の比較を開始し、文字列「」の桁を含まない「N」以下で形成される最大の数値を見つけます。 S'.

アプローチ 1: - 素朴なアプローチ

別の文字列内のすべての数値を使用して、特定の文字列内の最大の数値を見つける基本的な方法は次のとおりです。 main 関数は変数を宣言し、LargestNumberFinder 関数を呼び出します。この関数は 2 つの文字列を入力として受け取り、文字列 S 内のすべての桁を含む N 未満の値をすべてチェックします。条件が満たされる場合、値は文字列形式で返されます。出席関数は、S を整数データ型に変換する際に、「i」に格納されている値が文字列 S の一部であるかどうかを判断するために使用されます。入力文字列は整数に変換され、ループを使用して条件が評価されます。このコードは、指定された文字列内の、別の文字列にも存在するすべての数値の最大値を出力します。

Example

は次のように翻訳されます:

Example

このコードは、文字列 S の数字から構成される N (整数に変換された入力文字列) より小さい最大の数値を見つけるソリューションです。このコードでは、「attendance」と「LargestNumberFinder」という 2 つの関数を使用して、最大の数値を決定して返します。出席関数は、整数 'i' と文字列 's' を入力として受け取り、'i' に格納されている値が文字列 's' の一部であるかどうかを確認し、's' を整数データ型に変換します。 LargestNumberFinder 関数は、2 つの文字列 'x' と 's' を入力として受け取り、'x' を整数に変換し、出席関数を使用して N 未満のすべての値とすべての数値が 's' に含まれていることを確認します。 main 関数は変数を宣言し、LargestNumberFinder 関数を呼び出します。この関数は最大の数値を文字列として返します。

リーリー ＃＃＃出力＃＃＃ リーリー

方法 2: 効率的な方法

問題 2 の解決策 (指定された数値文字列 N の数値を指定された文字列 S の数値に置き換えることによって最大の数値を取得する) の場合、これは効率的な方法です。このメソッドは、まず N のすべての数値が S に存在するかどうかを確認し、S で見つかった最初の数値を、S 内で N にない最大の数値に置き換えます。残りの数値は、N にない S の最大の数値に置き換えられます。その後、先頭のゼロが削除され、結果が可能な最大の数値として返されます。この方法は文字列を並べ替える必要がないため、前の方法よりも効率的です。

Example

は次のように翻訳されます:

Example

このコードは、文字列「S」に存在しない数字を最も高い数字に置き換えることによって、指定された文字列「N」から形成できる最大の数値を見つける問題を解決します。このコードは、効率的な方法を利用して、問題です。LargestNumberFinder 関数は、2 つの文字列入力 "num" と "s" を受け取り、可能な最大の数値を返します。ベクトル "vis_s" は、文字列 "s" の値を格納するために利用されます。コードは、最初に最初の文字列を識別します。文字列 "s" の一部である文字列 "num" の桁。次に、その桁を文字列 "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;
}

Output

149999

结论

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

以上がNを超えず、Sに数値を含まない最大の数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。