题目描述
Given a positive integer N
, return the number of positive integers less than or equal to N
that have at least 1 repeated digit.
Example 1:
Input: 20
Output: 1
Explanation: The only positive number (<= 20) with at least 1 repeated digit is 11.
Example 2:
Input: 100
Output: 10
Explanation: The positive numbers (<= 100) with atleast 1 repeated digit are 11, 22, 33, 44, 55, 66, 77, 88, 99, and 100.
Example 3:
Input: 1000
Output: 262
Note:
1 <= N <= 10^9
题意:给定正整数 N
,返回小于等于 N
且具有至少 1 位重复数字的正整数。
算法1
(数位DP)
题解:首先我们将考虑该问题的反向问题,小于N
的不包含重复数字的正整数有多少?
首先我们使用digit
数组从高到低存储数组的每一位,然后我们可以很简单的找到位数小于N
的不包含重复数字的正整数个数,dp[i]
代表不包含重复数字的i
位正整数的个数:
dp[1] = 9,dp[2] = 81,dp[i] = dp[i - 1] * (11 - i)
。
接下来我们考虑和N
位数相同的合法数字,我们依次考虑和N
有仅有i
位公共前缀的合法数字,从0开始。
我们使用visit
数组记录当前N
中有哪些数字已经遇到过了,一旦我们再次遇到重复数字,说明后续就不用搜索了。
考虑公共前缀有i
位的数字,那么在第i + 1
位可以选择的数要满足两个条件,要小于数字N
中第i + 1
个数字并且在前面i + 1
位没有遇到过。我们从0遍历到digit[i] - 1
,总共有temp
个数字没有使用过,如果i == 0
,需要特判一下减去一个数字,因为不能有前导0。
如果temp > 0
,说明第i + 1
位有temp
种选择,那么对于i + 2
位到len
位,每一位可供选择的个数其实就是10 - (i + 1),10 -(i + 2),…,
。根据乘法计数原理,我们相乘即可并记录到答案中。
这时候我们考虑N
中第i + 1
位的数字是否在之前遇到过了,如果遇到过了,那么直接返回答案,如果没有遇到过,那么更新访问数组。如果始终没有遇到过重复数字,那么最终的答案还需要减去1,因为N
也是不符合条件的。
class Solution {
public:
int numDupDigitsAtMostN(int N) {
if(N <= 10) return 0;
vector<int> digit;
int temp = N ;
while(temp > 0)
{
digit.push_back(temp % 10);
temp = temp / 10;
}
reverse(digit.begin(),digit.end());
int dp[10] = {0,9,81},res = 0,len = digit.size();
// 枚举位数小于N的合法数字
for(int i = 3 ; i < 10 ; i ++)
dp[i] = dp[i - 1] * (11 - i);
for(int i = 0 ; i < len ; i ++)
res += dp[i];
// 枚举和N位数相同,且有i个共同前缀的
vector<bool> visit(10,false);
for(int i = 0 ; i < len ; i ++)
{
//第i + 1位数字可选择的个数
int temp = 0;
for(int j = 0 ; j < digit[i] ; j ++)
if(!visit[j])
temp ++;
//第一个数字不能是0
if(i == 0) temp --;
if(temp > 0)
{
for(int j = (10 - i - 1),k = i + 2 ; k <= len ; k ++,j --)
temp = temp * j;
res += temp;
}
if (visit[digit[i]])
return N - res;
visit[digit[i]] = true;
}
return N - res - 1;
}
};