357、计算各个位上的数字不同的数字的个数
给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 $0 ≤ x < 10^n $。
示例:
输入: 2
输出: 91
解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 区间内的所有数字。
题解
1、数学+动态规划
数学规律——组合数
每个数字在前一个的基础上，加上一位（除去0），
- 1位数有：0～9:10
- 2位数有：10*9-9 = 81
- 3位数有：81*8
- 4位数有：8187
- 5位数有：8187*6
- 6位数有：818765
- 7位数有：818765*4
- 8位数有：81876543
- 9位数有：81876543*2
- 10位数有：8187654321
- 累加即可
代码
// java
class Solution {
public int countNumbersWithUniqueDigits(int n) {
if(n == 0) {
return 1;
}
if (n >= 10) {
n = 10;
}
int[] dp = new int[11];
dp[1] = 10;
dp[2] = 81;
// 从三位数开始，遵循排列数规律
for (int i = 3;i <= n;i++) {
dp[i] = dp[i - 1]*(11-i);
}
int sum = 0;
for (int i = 1;i <= n;i++) {
sum += dp[i];
}
return sum;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
