1012. Numbers With Repeated Digits

Description

image-20210818220237725

Solution

  • The most important tricky point, just find integers have no repeated digit!!!
  • Then use DFS to solve the problem
    • A naive way is to find the permutation -> TLE
    • To speed up, we can directly compute permutation that has less digits than n‘s, then use DFS to compute the combination whose digit equals to n

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
public:
    int res = 0;
    int numDupDigitsAtMostN(int n) {
        int tmp = n;
        int digit = 0;
        vector<int> num;
        while(tmp){
            digit ++;
            num.push_back(tmp%10);
            tmp /= 10;
        }
        reverse(num.begin(), num.end());
        for(int i = 1; i <= digit-1; i++){
            if(i == 1)
                res += 9;
            else
                res += 9 * Amn(i-1,9);
        }
        vector<int> visited(10,0);
        dfs(n, visited, 0, num);
        return n - res;
    }

    void dfs(int n, vector<int>& visited, int curPos, vector<int>& num){
        if(num.size() == curPos){
            res++;
            return;
        }
        for(int i = 0; i < 10; i++){
            if(curPos == 0 && i == 0)
                continue;
            if(i < num[curPos]){
                if(visited[i])
                    continue;
                res += Amn(num.size() - curPos - 1, 9 - curPos);
            }else if(i == num[curPos]){
                if(visited[i])
                    return;
                visited[i] = 1;
                dfs(n, visited, curPos+1, num);
                visited[i] = 0;
            }else
                break;
        }
    }

    int Amn(int m, int n){
        int res = 1;
        for(int i = 0; i < m; i++)
            res *= n - i;
        return res;
    }

};

image-20210818221153644