欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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;
    }
};
相关标签: leetcode解题