leetcode 357 计算各个位数不同的数字个数
程序员文章站
2022-05-20 12:57:04
...
题目
leetcode 357 计算各个位数不同的数字个数
给定一个非负整数 n,计算各位数字都不同的数字 x 的个数,其中 0 ≤ x < 10n 。
示例:
输入: 2
输出: 91
解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外,在 [0,100) 区间内的所有数字。
分析
- 注意到 n 是非负整数,当
n == 0,x = 1
- 最高位的解空间是
[1-9]
,其余位的解空间是[0-9]
暴力穷举(回溯)
- 每一位都是路径中的节点
- 解空间:第一个节点是[1-9],其他节点是[0-9]
- 终止条件:路径长度 大于 n
- 解的判断条件:每次进入函数时,counter加一,表示以当前节点为个位的不相同数
- 回溯的状态:建立一个used数组,表示到当前节点时,已经使用过的数字,如果已经使用,直接结束;否则在解空间中选择一个未使用的进入下个节点搜索
code
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。
- 定义dp[i]为,个数为i的不重复的数的个数。
- dp[0] = 1;
- dp[1] = 9;
- dp[2] = 9 * 9; 十位可以选[1-9]中的任意一个,9种选择,个位选[0-9]中除去十位选择的任意一个,共 10 -1 = 9 种
- dp[3] = 9 * 9 * 8;
- …
- dp[10] = 9 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
- 要求的结果就是i:dp[0] + dp[1] + … + dp[n];
- 根据以上规律,建立一个辅助table[] = {1,9,9,8,7,6,5,4,3,2,1}
- 注意到dp[i] = dp[i -1] * table[i],因此用变量dp_i 来表示dp数组,节省空间。
code
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;
}
};
上一篇: 盛最多水的容器
推荐阅读
-
题目: 要求从键盘接受一个4位的会员卡号,利用/或% ,分别拆分出这个4位数的各个位的数字,计算其相加之和!
-
【LeetCode-402】402.移除k位数字(给定一个以字符串表示的非负整数 num,移除这个数中的 k 位数字,使得剩下的数字最小。)
-
跟着专注于计算机视觉的AndyJ的妈妈我学算法之每日一题不是leetcode题每次移动一个数字排序
-
leetcode 357 计算各个位数不同的数字个数
-
1002 写出这个数 (20)(20 分) 读入一个自然数n,计算其各位数字之和,用汉语拼音写出和的每一位数字。 输入格式:每个测试输入包含1个测试用例,即给出自然数n的值。这里保证n小于10^10
-
跟着专注于计算机视觉的AndyJ的妈妈我学算法之每日一题不是leetcode题每次移动一个数字排序