解法包括暴力解法和扩张方法。
直接对所有的数字求解,约为O(nlogn),目测必定超时,就不浪费时间了。
这个想法是错的……不应该从有重复的数字扩张,应该从没有重复的数字扩张。早上起来做这道题脑子有点懵。
该问题是具备最优子结构的。对于长度为n的问题,与其枚举没有重复的数字,不如枚举重复的数字。 重复源头可以来源于之前(n-1)与当前,因此可以从这个地方开始递推比较最新一位的数字与之前的数字之间的关系。
可以定义数字dp[n][m]为长度为n的数组中以m开头的数内重复的数字个数。 其中对0的处理比较麻烦,最高位不会出现0,但是0是有可能出现重复的,因此可能需要对之前的一位做专门的处理。 因此特殊的,定义dp[n-1][0]为第n位数为任意非0数时,n-1位为0时的重复数字个数
显而易见的是,dp[1][…]=0,长度为一位的时候不会有重复的数据。
最新的一位数据的内容主要包括两个方面:
在计算的时候是一起计算的,n位以0开头的数字可以视为n+1位存在任意数字使其非0。但是最终计算总重复数字时不会加入dp[n][0],因为最高位为时非法的。
以n=3为例子:
官方给的解法:含有d位数(2\geq d\leq 10)的各位数字都不同的数字x的个数可以由9\times A_{9}^{d-1}。(第一位选择范围为除0以外,第二位为10个数字除以第一位,以此类推)
class Solution {
public:
int countNumbersWithUniqueDigits(int n) {
if (n == 0) {
return 1;
}
if (n == 1) {
return 10;
}
int ans = 10, cur = 9;
for (int i = 0; i < n - 1; ++i) {
cur *= 9 - i;
ans += cur;
}
return ans;
}
};