1088. Confusing Number II

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.

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:

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:

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

这道题是之前那道 Confusing Number 的拓展,之前那道只是问一个给定的数字是否是迷惑数,而这道题是问给定数字N之内有多少个迷惑数字。这样的话难度就增加了不少,肯定不要想着直接遍历小于N的所有数字,对每个数字都调用之前的判断方法,毫无疑问的会超时。实际上大多数字都不是迷惑数字,所以一个一个的检验非常的不高效。这里需要使用一些技巧,由于组成迷惑数的只有五个数字,那么迷惑数的每个位上只能是这五个数字,于是就可以用递归来遍历所有的情况,假如N是个三位数,那么每一位有五种情况,总共也就 125 个数字要验证,远小于遍历所有的数字。但是由于迷惑数要求翻转后跟原数字不相同,所以还需要一个子函数判断一下是否是真正的迷惑数,这个需要计算出翻转后的数字,然后跟原数字比较一下,不相同才返回 true。当判断了是真正的迷惑数时,结果 res 自增1即可,参见代码如下:

解法一:

class Solution {
public:
    int confusingNumberII(int N) {
        int res = 0;
        unordered_map<int, int> m{{0, 0}, {1, 1}, {6, 9}, {8, 8}, {9, 6}};
        helper(N, 0, m, res);
        return res;
    }
    void helper(int N, long cur, unordered_map<int, int>& m, int& res) {
        if (isConfusingNum(cur, m)) ++res;
        for (auto a : m) {
            if (cur * 10 + a.first <= N && cur * 10 + a.first != 0) {
                helper(N, cur * 10 + a.first, m, res);
            }
        }
    }
    bool isConfusingNum(long num, unordered_map<int, int>& m) {
        long oldNum = num, res = 0;
        while (num > 0) {
            if (m.count(num % 10)) return false;
            res = res * 10 + m[num % 10];
            num /= 10;
        }
        return res != oldNum;
    }
};

我们还可以使用迭代的写法,思路跟上面的递归写法基本一样,就是写法上有些不同,这里用到一个数组 vec,初始时将0放入,然后进行循环,循环的条件是 found 为 false,这个 found 变量是用来控制当前生成的数字是否在 [1, N] 范围中的。在循环中需要用一个临时数组t,此时生成的方法是,遍历 vec 数组中的每个数字,在其基础上新增一位数字,这个数字要遍历五个候选数字,组成新的数字后首先看是否越界,是的话将found 赋值为 true,然后直接 break 掉内层的 for 循环。因为这种 BFS 的遍历方式是一种层序遍历,之后组成的数字一定会越来越大,所以只要当前超过 N 了,后面的数字一定都会超过N。假如没超过N,若当前数字不为0,则将其加入t数组中,然后再对该数字调用判断迷惑数的子函数,若返回 true,则结果 res 自增1。内层 for 循环结束后,看下 found 值,若为 true,则 break 掉外层 for 循环。外层 for 循环结束后,要将临时数组t赋值给数组 vec,参见代码如下:

解法二:

class Solution {
public:
    int confusingNumberII(int N) {
        int res = 0;
        map<int, int> m{{0, 0}, {1, 1}, {6, 9}, {8, 8}, {9, 6}};
        vector<int> vec{0};
        bool found = false;
        while (!found) {
            vector<int> t;
            for (int num : vec) {
                for (auto a : m) {
                    int cur = num * 10 + a.first;
                    if (cur > N) {
                        found = true; break;
                    }
                    if (cur != 0) t.push_back(cur);
                    if (isConfusingNum(cur, m)) ++res;
                }
                if (found) break;
            }
            vec = t;
        }
        return res;
    }
    bool isConfusingNum(int num, map<int, int>& m) {
        int oldNum = num, res = 0;
        while (num > 0) {
            if (!m.count(num % 10)) return false;
            res = res * 10 + m[num % 10];
            num /= 10;
        }
        return res != oldNum;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1088

类似题目:

Confusing Number

参考资料:

https://leetcode.com/problems/confusing-number-ii/

https://leetcode.com/problems/confusing-number-ii/discuss/313407/Backtracking-and-Iterative-Solution-in-Java

https://leetcode.com/problems/confusing-number-ii/discuss/446589/Easy-to-understand-Java-backtracking-solution-covers-edge-case

https://leetcode.com/problems/confusing-number-ii/discuss/392786/Confusing-number-Total-number-Strobogrammatic-number-(Java-1ms)

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation