leetcode 357 计算各个位数不一样的数字个数
给定一个非负整数 n,计算各位数字都不一样的数字 x 的个数,其中 0 ≤ x < 10n 。c++
示例:git
输入: 2
输出: 91
解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外,在 [0,100) 区间内的全部数字。web
n == 0,x = 1
[1-9]
,其他位的解空间是[0-9]
class Solution { int counter = 0; vector<bool> used = vector<bool>(10,false); void backtrace(int n,int level){ counter++; if(level == n){ return; } for(int i = level ? 0 : 1; i < 10; ++i){ if(used[i]) continue; used[i] = true; backtrace(n,level + 1); used[i] = false; } } public: int countNumbersWithUniqueDigits(int n) { if(n == 0) return 1; backtrace(n,0); return counter; } };
通常求取符合某种规则的的“串”的数量,可是不要求具体的“串”的集合,均可以用dp。数组
class Solution { public: int countNumbersWithUniqueDigits(int n) { vector<int> table{1,9,9,8,7,6,5,4,3,2,1}; n = n >=10 ? 10 : n; //n 大于10后是没有符合的数 int counter = table[0]; int dp_i = 1; for(int i = 1; i <= n;++i ){ dp_i *= table[i]; counter += dp_i; } return counter; } };