C++で設定された最大N個の数字

ソートされた数字のセットDが1つあり、{'1'、 '2'、 '3'、 '4'、 '5'、 '6'、 '7'、 '8'、'の空でないサブセットがあるとします。 9'} 0を除く。ここで、これらの数字を使用して、各数字を必要な回数だけ使用して、いくつかの数字を書き込みます。したがって、D ={'2'、 '3'、 '7'}の場合、 '23'、 '771'、'2372327'などの数字を書くことができます。

ここで、N以下の書き込み可能な正の整数の数を見つける必要があります。

したがって、入力がD =[2,3,4,7]、N =100の場合、数値は2、3、4、7、22、23、24、27になる可能性があるため、出力は20になります。 、32、33、34、37、42、43、44、47、72、73、74、77。他のすべての数値は100より大きい。

これを解決するには、次の手順に従います-

• n：=Nを文字列に変換

• sz：=nのサイズ、ret：=0

• 初期化i：=1の場合、i

  • ret：=ret +（Dのサイズ）^ i

• 初期化i：=0の場合、i

  • hasSameNum：=false

  • Dの文字列xごとに-

    • x [0]

      • ret：=ret +（Dのサイズ）^（sz-i-1）

    • それ以外の場合、x[0]がn[i]と同じである場合、-

      • hasSameNum：=true

  • hasSameNumがゼロ以外の場合、-

    • retを返す

• ret+1を返す

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int atMostNGivenDigitSet(vector<string> &D, int N) {
      string n = to_string(N);
      int sz = n.size();
      int ret = 0;
      for (int i = 1; i < sz; i++) {
         ret += pow(D.size(), i);
      }
      for (int i = 0; i < sz; i++) {
         bool hasSameNum = false;
         for (string &x : D) {
            if (x[0] < n[i]) {
               ret += pow(D.size(), sz - i - 1);
            } else if (x[0] == n[i]) {
               hasSameNum = true;
            }
         }
         if (!hasSameNum)
         return ret;
      }
      return ret + 1;
   }
};
main(){
   Solution ob;
   vector<string> v = {"2","3","4","7",};
   cout << (ob.atMostNGivenDigitSet(v, 100));
}

入力

{"2","3","4","7"}, 100

出力

20