数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中具有重复数字的数字
假设我们有一个正整数N，我们必须找到小于或等于N且至少有一个重复数字的正整数的个数。
因此，如果输入是99，则输出将是9，因为我们有11、22、33、44、55、66、77、88、99这样的数字。
为了解决这个问题，我们将遵循以下步骤：
定义一个函数A()，它将接收m, n作为参数：
ret := 1
for i := 0 to n-1 do −
ret := ret * m
m := m - 1
return ret
在主方法中执行以下操作：
定义一个数组arr
for i := N + 1 downto 1 do −
将arr的第一个元素插入到arr的索引i mod 10处
ret := 0
n := arr的长度
for i := 1 to n-1 do −
ret := ret + 9 * A(9, i - 1)
定义一个集合visited
for i := 0 to n-1 do −
digit := arr[i]
for j := (if i == 0 then 1 else 0) to digit -1 do −
if j in visited then −
忽略以下部分，跳到下一次迭代
ret := ret + A(9 - i, n - i - 1)
if digit in visited then −
退出循环
将digit插入到visited中
return 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
更新于：2020年6月4日
573 次浏览
广告