1012. 至少有 1 位重复的数字
给定正整数 n，返回在 [1, n] 范围内具有 至少 1 位 重复数字的正整数的个数。
示例 1：
输入：n = 20
输出：1
解释：具有至少 1 位重复数字的正数（<= 20）只有 11 。
示例 2：
输入：n = 100
输出：10
解释：具有至少 1 位重复数字的正数（<= 100）有 11，22，33，44，55，66，77，88，99 和 100 。
示例 3：
输入：n = 1000
输出：262
提示：
1 <= n <= 10^9解答：数位dp
class Solution {
int P(int a, int b) {
int res = 1;
for (int i = a, j = 0; j < b; i --, j ++ )
res *= i;
return res;
}
public int numDupDigitsAtMostN(int n) {
//数位dp或数位统计（统计满足要求的数字有多少个）
//补集思想：总数-不含重复数字的正整数个数
//画一棵树
//f(n) 1~n之间每一位都不重复的数字个数
LinkedList<Integer> nums =new LinkedList();
int res = n;
while(n>0){
nums.offerLast(n%10);
n/=10;
}
boolean[] st=new boolean[10];
for (int i = 1; i < nums.size(); i ++ )
res -= 9 * P(9, i - 1);
res -= (nums.peekLast() - 1) * P(9, nums.size() - 1);
st[nums.peekLast()] = true;
for (int i = nums.size() - 2; i >= 0; i -- ) {
int x = nums.get(i);
for (int j = 0; j < x; j ++ )
if (!st[j])
res -= P(10 - (nums.size() - i), i);
if (st[x]) return res;
st[x] = true;
}
return res - 1;
}
}
