Leetcode skimming -- count the number of numbers with different numbers 357 medium

The train of thought and source code of counting the number of different numbers
     The topic of counting the number of different figures is shown in the figure below , This problem belongs to mathematics and backtracking type , It mainly examines the use of backtracking methods and the understanding of mathematical ideas of the topic . The title of this article, the author thought 2 Methods , They are permutation and combination method and recursive method , The permutation and combination method uses Java Compiling , The recursive method uses Python Compiling , Of course, this may not be the optimal solution , I also hope you guys can give a faster algorithm .

     I think this problem can be solved by using the idea of permutation and combination , First, judge whether the number is 0 perhaps 1, If it is 0 Just go back to 1; If it is 1 Just go back to 10, Then start initializing the result variables and subscript variables . Start traversing the loop , Record the temporary arrangement result with the current subscript result , Then add it to the result variable , Until the end of the traversal returns the final result . Then according to this idea, our Java The code is as follows ：

# Fire breathing dragon and water arrow turtle 
class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return 10;
        }
        int resFinal = 10;
        int ind = 9;
        for (int jr = 0; jr < n - 1; jr++) {
            ind = ind * (9 - jr);
            resFinal = resFinal + ind;
        }
        return resFinal;
    }
}

     obviously , We can see that the effect of the permutation row combination method is ok , At the same time, we can also use the recursive method to solve . First, initialize a list , And the assignment 9 individual 0 Is the initialization result . Let the first list element be 1, The second list element is 10, Then start traversing the loop from the second element , After deduction and summary, use mathematical recurrence formula to calculate , Get the traversal result and return the element of the last list . So according to this idea, we can solve , Here is Python Code ：

# Fire breathing dragon and water arrow turtle 
class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        vc = []
        for ij in range(9):
            vc.append(0)
        vc[0] = 1
        vc[1] = 10
        for jr in range(2,9):
            vc[jr] = vc[jr-1] + (vc[jr-1]-vc[jr-2])*(10-(jr-1))
        return vc[n]

     As a result Java The efficiency of the permutation and combination method of version is good , and Python The speed of the recursive method of version is also ok , But there should be more ways to further speed up , I hope friends can give me more advice , Thank you very much .