C++で繰り返される数字の数

正の整数Nがあるとすると、少なくとも1つの繰り返し桁を持つN以下の正の整数の数を見つける必要があります。

したがって、入力が99の場合、出力は9になります。これは、11、22、33、44、55、66、77、88、99のような数値があるためです。

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

• 関数A（）を定義します。これにはm、n、

  が必要です。

  • ret：=1

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

    • ret：=ret * m

    • （mを1減らします）

  • retを返す

• メインの方法から、次のようにします-

• 配列arrを定義する

• 初期化i：=N + 1の場合、i> 0の場合、更新i：=i / 10、do −

  • インデックスimod10のarrの最初の要素をarrに挿入します

• ret：=0

• n：=arrのサイズ

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

  • ret：=ret + 9 * A（9、i-1）

• 訪問した1セットを定義する

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

  • 数字：=arr [i]

  • 初期化j：=（iが0と同じ場合は1、それ以外の場合は0）の場合、j <桁の場合、更新（jを1増やします）、実行-

    • jが訪問中の場合、-

      • 次の部分を無視し、次の反復にスキップします

    • ret：=ret + A（9-i、n-i-1）

  • 数字が訪問されている場合、-

    • ループから出てきます

  • 訪問者に数字を挿入

• Nを返す-ret

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

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int A(int m, int n){
      int ret = 1;
      for (int i = 0; i < n; i++) {
         ret *= m;
         m--;
      }
      return ret;
   }
   int numDupDigitsAtMostN(int N){
      vector<int> arr;
      for (int i = N + 1; i > 0; i /= 10) {
         arr.insert(arr.begin(), i % 10);
      }
      int ret = 0;
      int n = arr.size();
      for (int i = 1; i < n; i++) {
         ret += 9 * A(9, i - 1);
      }
      set<int> visited;
      for (int i = 0; i < n; i++) {
         int digit = arr[i];
         for (int j = i == 0 ? 1 : 0; j < digit; j++) {
            if (visited.count(j))
            continue;
            ret += A(9 - i, n - i - 1);
         }
         if (visited.count(digit))
         break;
         visited.insert(digit);
      }
      return N - ret;
   }
};
main(){
   Solution ob;
   cout << (ob.numDupDigitsAtMostN(99));
}

入力

99

出力

9