【leetcode刷题】T168-计算各个位数不同的数字个数

• 2019 年 10 月 6 日
• 笔记

木又连续日更第4天（4/100）

木又的第168篇leetcode解题报告

动态规划类型第13篇解题报告

leetcode第357题：计算各个位数不同的数字个数

https://leetcode-cn.com/problems/count-numbers-with-unique-digits/

【题目】

给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10^n 。

示例:  输入: 2  输出: 91  解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 区间内的所有数字。  

【思路】

这道题主要用到排列组合知识。

首先考虑特殊情况，n>10，肯定会存在重复数字，所以返回0。

使用dp[i]存储i位数符合条件的个数（不包含最高位为0的数），最后返回sum(dp)。

n==0时，dp[i]=1

n==1时，dp[i]=9*dp[0]

n==2时，dp[i]=9*dp[1]，相当于首位数有9种可能（1->9），第二位数也存在9种可能（0->9除了首位数）

n==3时，dp[i]=8*dp[i]，首位数有9种可能（1->9），第二位数存在9种可能（0->9除了首位数），第三位数存在8种可能（0->9除了首位数和第二位数）

同理得到n>1时，dp[i] = (10-i+1)*dp[i-1]，相当于前面几位都排序好，接下来一位只存在(10-i+1)种可能。

【代码】

python版本

class Solution(object):      def countNumbersWithUniqueDigits(self, n):          """          :type n: int          :rtype: int          """          if n > 10:              return 0          dp = [1] * (n+1)          for i in range(1, n+1):              if i < 3:                  dp[i] = dp[i-1] * 9              else:                  dp[i] = dp[i-1] * (10-i+1)          return sum(dp)  

C++版本

class Solution {  public:      int countNumbersWithUniqueDigits(int n) {          if(n > 10)              return 0;          vector<int> dp(n+1, 1);          for(int i=1; i<n+1; i++){              if(i < 3)                  dp[i] = 9 * dp[i-1];              else                  dp[i] = (10-i+1) * dp[i-1];          }          // 求和          int sum = 0;          for(auto tmp: dp)              sum += tmp;          return sum;      }  };