C ++中带有重复数字的数字

假设我们有一个正整数N，我们必须找到小于或等于N且具有至少1个重复数字的正整数。

因此，如果输入像99，那么输出将是9，因为我们有数字11、22、33、44、55、66、77、88、99。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个函数A()，它将花费m，n，

• ret：= ret *米

• （将m减1）

• ret：= 1

• 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

• 返回ret

• 从主要方法中执行以下操作-

• 定义数组arr

• 对于初始化i：= N + 1，当i> 0时，更新i：= i / 10，执行-

• 将索引为mod 10的arr的第一个元素插入arr

• ret：= 0

• n：= arr的大小

• 对于初始化i：= 1，当i <n时，更新（将i增加1），-

• ret：= ret + 9 * A(9,i-1)

• 定义一组参观

• 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

• 从循环中出来

• 如果访问了j，则-

• ret：= ret + A(9-i,n-i-1)

• 忽略以下部分，跳至下一个迭代

• digit：= arr [i]

• 对于初始化j：=（如果i与0相同，则为1，否则为0），当j <digit时，更新（将j增加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