leetcode 1088

问题

We can rotate digits by 180 degrees to form new digits. When 0, 1, 6, 8, 9 are rotated 180 degrees, they become 0, 1, 9, 8, 6 respectively. When 2, 3, 4, 5 and 7 are rotated 180 degrees, they become invalid.

A confusing number is a number that when rotated 180 degrees becomes a different number with each digit valid.(Note that the rotated number can be greater than the original number.)

Given a positive integer N, return the number of confusing numbers between 1 and N inclusive.

Example 1:

1
2
3
4
5
6
7
8
9
10
Input: 20
Output: 6
Explanation: 
The confusing numbers are [6,9,10,16,18,19].
6 converts to 9.
9 converts to 6.
10 converts to 01 which is just 1.
16 converts to 91.
18 converts to 81.
19 converts to 61.

Example 2:

1
2
3
4
Input: 100
Output: 19
Explanation: 
The confusing numbers are [6,9,10,16,18,19,60,61,66,68,80,81,86,89,90,91,98,99,100].

Note:

  1. 1 <= N <= 10^9

分析

思路1: 由 0, 1, 6, 8, 9 进行排列组合出所有有可能是 Confusing Number 的数组，然后再判断其是否是 Confusing Number。

思路2: 由 0, 1, 6, 8, 9 进行排列组合出的所有小于等于N组合数中，不是 Confusing Number 就是Strobogrammatic Number，且 Strobogrammatic Number 的数量要远小于 Confusing Number的数量。因此，可以使用总数量减去 Strobogrammatic Number 的数量来得到 Confusing Number 的数量。

代码1

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
// BFS
class Solution {
public:
    int a[5] = {0, 1, 6, 8, 9};
    int b[10] = {0, 1, -2, -3, -4, -5, 9, -7, 8, 6};
    bool isConfusingNumber(long long X) {
        long long rx = 0;
        long long x  = X;
        while (X > 0) {
            rx = rx*10 + b[X%10];
            X/=10;
        }
        return rx==x? false: true;
    }
    int confusingNumberII(int N) {
        queue<long long> q;
        int ans = 0;
        if (N < 6) return 1;
        if (N < 9) return 2;
        for (int i = 1; i < 5; ++i) {
            q.push(a[i]);
        }
        bool enough = false;
        while (q.size() != 0) {
            long long x = q.front();
            q.pop();
            if (isConfusingNumber(x))
                ans++;
            if (enough == false) {
                for (int i = 0; i < 5; ++i) {
                    long long y = x*10 + a[i];
                    if (y <= N)
                        q.push(y);
                    else
                        enough = true;
                }
            }
        }
        return ans;
    }
};

代码2

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
class Solution {
public:
    int a[5] = {0, 1, 6, 8, 9};
    int b[10] = {0, 1, -2, -3, -4, -5, 9, -7, 8, 6};
    bool isConfusingNumber(long long X) {
        long long rx = 0;
        long long x  = X;
        while (X > 0) {
            rx = rx*10 + b[X%10];
            X/=10;
        }
        return rx==x? false: true;
    }
    int confusingNumberII(int N) {
        int ans = 0;
        for (int i = 1; i < 5; ++i) {
            dfs(a[i], N, ans);
        }
        return ans;
    }
    void dfs(long long num, int N, int &ans) {
        if (num > N)
            return;
        if (isConfusingNumber(num))
            ans++;
        for (int i = 0; i < 5; ++i) {
            dfs(num*10 + a[i], N, ans);
        }
    }
};

代码3

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
56
57
58
// faster 100% 0ms
class Solution {
public:
    vector<vector<char>> pairs = {{'0','0'}, {'1','1'}, {'6','9'}, {'8','8'}, {'9','6'}};
    int a[10] = {0, 1, -1, -1, -1, -1, 9, -1, 8, 6};
    int confusingNumberII(int N) {
        int ans = 0;
        string n = to_string(N);
        // get total number
        ans = getTotalNumber(n);
        for (int len = 1; len <= n.size(); ++len) {
            string s(len, '0');
            ans -= dfs(n, s, 0, len-1);
        }
        return ans;
    }
    
    int dfs(const string &n, string s, int l, int r) {
        int ret = 0;
        if (l > r) {
            if (s.size() == n.size() && s > n)
                return 0;
            else
                return 1;
        } else {
            for (vector<char> &p: pairs) {
                s[l] = p[0];
                s[r] = p[1];
                if (s.size() != 1 && s[0] == '0')
                    continue;
                if (l==r && p[0]!=p[1])
                    continue;
                ret += dfs(n, s, l+1, r-1);
            }
        }
        return ret;
    }
    int getTotalNumber(string n) {
        int ret = 0;
        if (n.size() == 1) {
            ret = count(n[0]+1);
        } else {
            ret = count(n[0])*pow(5, n.size()-1);
            if (a[n[0]-'0'] >= 0)
                ret += getTotalNumber(n.substr(1));
        }
        return ret;
    }

    int count(char c) {
        int ret = 0;
        for (vector<char> &p: pairs) {
            if (c > p[0])
                ret++;
        }
        return ret;
    }
};