357. 计算各个位数不同的数字个数
难度中等
给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10n 。 示例:
输入: 2 输出: 91 解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 区间内的所有数字。
个人思路：
设变量tol为位数等于n的 n-1个数的所有排序 即：n=3时 abc=ab+ac+bc dp[i]=dp[i-1]tol10
代码1.0
class Solution {
public:
int countNumbersWithUniqueDigits(int n
) {
if(n
<=1)
{
return pow(10,n
);
}
vector
<int> dp(n
+1,0);
dp
[2]=9;
for(int i
=3;i
<=n
;++i
)
{
dp
[i
]=dp
[i
-1]*i
*10-dp
[i
-1];
}
return pow(10,n
)-dp
[n
];
}
};
结果出错
思路2.0
写下前几个，就能看出规律了。 n=1: res=10 n=2: res=9*9+10=91 # 两位数第一位只能为1-9，第二位只能为非第一位的数，加上一位数的所有结果 n=3: res=9 * 9 * 8+91=739 # 三位数第一位只能为1-9，第二位只能为非第一位的数，第三位只能为非前两位的数，加上两位数的所有结果
代码2.0
class Solution {
public:
int countNumbersWithUniqueDigits(int n
) {
if(n
==0)
{
return 1;
}
vector
<int> dp(n
+1,1);
dp
[0]=1;
dp
[1]=9;
for(int i
=2;i
<=n
;++i
)
{
dp
[i
]=dp
[i
-1]*(10-i
+1);
}
return accumulate(dp
.begin(),dp
.begin()+n
+1,0);
}
};
