手机网站存储登录信息,网站没有备案做竞价吗,常州创新优典网站建设,国家工信部网站备案查询1. 题目
给定一个非负整数 n#xff0c;计算各位数字都不同的数字 x 的个数#xff0c;其中 0 ≤ x 10n。
示例:
输入: 2
输出: 91
解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外#xff0c;在 [0,100) 区间内的所有数字。来源#xff1a;力扣#xff08;Lee…1. 题目
给定一个非负整数 n计算各位数字都不同的数字 x 的个数其中 0 ≤ x 10n。
示例:
输入: 2
输出: 91
解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外在 [0,100) 区间内的所有数字。来源力扣LeetCode 链接https://leetcode-cn.com/problems/count-numbers-with-unique-digits 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 动态规划
n各位都不同的元素个数0101100-9291
dp[i]dp[i]dp[i] 表示 n i 的时候有多少各位都不相同的数 那么 dp[i]dp[i]dp[i] 肯定需要加上 n i-1 时的个数 dp[i−1]dp[i-1]dp[i−1] 那么从 i-1 位数变成 i 位数且各位不相同的数有多少 首先 i-1 位的数有多少个 dp[i-1] - dp[i-2] 个 这 i-1 位数组成 i 位数且各个位都不一样可以添加的数的选择有多少种10-(i-1) 所以状态转移公式为 dp[i]dp[i−1](dp[i−1]−dp[i−2])∗(10−(i−1))dp[i] dp[i-1] (dp[i-1]-dp[i-2])*(10-(i-1))dp[i]dp[i−1](dp[i−1]−dp[i−2])∗(10−(i−1))
class Solution {
public:int countNumbersWithUniqueDigits(int n) {if(n 0)return 1;if(n 1)return 10;int dp[n1] {0};dp[0] 1, dp[1] 10;for(int i 2; i n; i){dp[i] dp[i-1] (dp[i-1]-dp[i-2])*(10-(i-1));}return dp[n];}
};
