leetcode--357. Count the number of different figures

• Give you an integer n , Count and return numbers with different numbers x The number of , among 0 <= x < 10n . ¹

• Example ：

#  Example  1
 Input ：n = 2
 Output ：91
 explain ： The answer should be to remove  11、22、33、44、55、66、77、88、99  Outside , stay  0 ≤ x < 100  All numbers in the range .
#  Example  2
 Input ：n = 0
 Output ：1

• Tips ：0 <= n <= 8

• Ideas ：

Recursion , First set the exit of recursion , if n Reduced to 0 了 , return 1
The loop logic is ：
f(0) = 1
f(1) = 9 + f(0)
f(2) = 9 * 9 + f(1)
f(3) = 9 * 9 * 8 + f(2)
…
Set a value to 9, Then set a loop in the input value from 1 Traversing n, Analysis shows that to define a 9 And another one. 9 unchanged , Then the sum must be equal to 10, Then the realization of the function is as follows: solution 1
Returns the of the previous value ans Plus the recursion of the function

• Solution 1 – recursive ：

class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        if n == 0:
            return 1
        ans = 9
        for i in range(1, n):
            ans *= (10 - i)
        return ans + self.countNumbersWithUniqueDigits(n - 1)

• Ideas ：

Two functions are set , First of all to see cntpo, This function returns the sum of unqualified numbers between every few digits
countNumbersWithUniqueDigits The function is to add up the sum of each unqualified number , Then return a total minus the unqualified number , That is, the number of qualified

• Solution 2 – Violence solution ：

class Solution:
    def countNumbersWithUniqueDigits(self, n):
        s = 0
        for i in range(1, n + 1):
            j = self.cntpo(i)
            s += j
        s_sum = pow(10, n)
        return s_sum - s

    def cntpo(self, n):
        cnt = 0
        for i in range(pow(10, n-1), pow(10, n)):
            for j in str(i):
                if str(i).count(j) > 1:
                    cnt += 1
                    break
        return cnt