leetcode 1012

问题

Given a positive integer N, return the number of positive integers less than or equal to N that have at least 1 repeated digit.

Example 1:

1
2
3
Input: 20
Output: 1
Explanation: The only positive number (<= 20) with at least 1 repeated digit is 11.

Example 2:

1
2
3
Input: 100
Output: 10
Explanation: The positive numbers (<= 100) with atleast 1 repeated digit are 11, 22, 33, 44, 55, 66, 77, 88, 99, and 100.

Example 3:

1
2
Input: 1000
Output: 262

Note:

  1. 1 <= N <= 10^9

分析

先求出符合条件的不重复的数字的个数，再由N减去不重复数字的个数就得到了含有重复数字的个数。

先得到N的位数的情况，然后在求出数位与N相等的情况。

注意要考虑N是否包含重复数字的情况。

代码

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
class Solution {
public:
    int numDupDigitsAtMostN(int N) {
        string n(to_string(N));
        int ans = 0;
        for (int len = 1; len <= n.size()-1; ++len) {
            int t = 9;
            int i = len-1;
            int lastNum = 9;
            while (i--) {
                t *= lastNum;
                lastNum--;
            }
            ans += t;
        }
        // cout << ans << endl;
        vector<bool> used(10, false);
        bool DupDigits = false;
        for (int i = 0; i < n.size(); ++i) {
            int t = 0;
            for (int j = 0; j < n[i]-'0'; ++j) {
                if (used[j] == false)
                    t++;
            }
            if (i == 0)
                t--;  // 首位不能是0
            for (int j = n.size()-i-1, lastNum = 10-i-1; j > 0; --j, --lastNum) {
                t *= lastNum;
            }
            ans += t;
            
            if (used[n[i] - '0'])   // why ??
                return N - ans;
            used[n[i]-'0'] = true;
        }
        return N - ans - 1;  // N 不包含重复数字，要减去N自身
    }
};