leetcode_357

发表于   |   分类于

Count Numbers with Unique Digits

题目戳这

题意

给定一个n，求x∈[0,10^n)中，每个数字位上的数字都不同的x有多少个，比如n=2时，x有91个,除去了11,22,…..,99

解法

用排列组合知识求解，当n=0时，返回1，当n=1时，返回10。那么当n\==2时，我们发现第一位是1-9，第二位能组合的数字就少了一个。n\==3时，在n\==2的基础上，第三位可取的数字又少了一位。一直这么算下去即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def countNumbersWithUniqueDigits(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n > 10:
            n = 10
        if n == 0:
            return 1
        if n == 1:
            return 10
        
        val = 9
        ssum = 10
        
        for i in range(2, n+1):
            val *= (9-i+2)     # 每多一位时都少一位数字可取，i=2时可取9位
            ssum += val
        
        return ssum