1056. Confusing Number

Given a number N, return true if and only if it is a  confusing number , which satisfies the following condition:

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.

Example 1:

Input: 6
Output: true
Explanation:
We get `9` after rotating `6`, `9` is a valid number and `9!=6`.

Example 2:

Input: 89
Output: true
Explanation:
We get `68` after rotating `89`, `86` is a valid number and `86!=89`.

Example 3:

Input: 11
Output: false
Explanation:
We get `11` after rotating `11`, `11` is a valid number but the value remains the same, thus `11` is not a confusing number.

Example 4:

Input: 25
Output: false
Explanation:
We get an invalid number after rotating `25`.

Note:

  1. 0 <= N <= 10^9
  2. After the rotation we can ignore leading zeros, for example if after rotation we have 0008 then this number is considered as just 8.

这道题定义了一种迷惑数,将数字翻转 180 度,其中 0, 1, 8 旋转后保持不变,6变成9,9变成6,数字 2, 3, 4, 5, 和 7 旋转后变为非法数字。若能将某个数翻转后成为一个合法的新的数,就说这个数是迷惑数。这道题的难度并不大,就是考察的是遍历整数各个位上的数字,使用一个 while 循环,然后用 mod10 取出当前最低位上的数字,将不合法的数字放入一个 HashSet 中,这样直接在 HashSet 中查找一下当前数字是否存在,存在直接返回 false。不存在的话,则要进行翻转,因为只有6和9两个数字翻转后会得到不同的数字,所以单独判断一下,然后将当前数字拼到 num 的最低位即可,最终拼成的 num 就是原数字 N 的翻转,最后别忘了比较一下是否相同,参见代码如下:

解法一:

class Solution {
public:
    bool confusingNumber(int N) {
        int num = 0, oldN = N;
        unordered_set<int> invalid{{2, 3, 4, 5, 7}};
        while (N > 0) {
            int digit = N % 10;
            if (invalid.count(digit)) return false;
            if (digit == 6) digit = 9;
            else if (digit == 9) digit = 6;
            num = num * 10 + digit;
            N /= 10;
        }
        return num != oldN;
    }
};

这也可以用一个 HashMap 来建立所有的数字映射,然后还是用一个变量 oldN 来记录原来的数字,然后遍历N上的每一位数字,若其不在 HashMap 中,说明有数字无法翻转,直接返回 false,否则就把翻转后的数字加入 res,最后只要看 res 和 oldN 是否相等即可,参见代码如下:

解法二:

class Solution {
public:
    bool confusingNumber(int N) {
        unordered_map<int, int> m{{0, 0}, {1, 1}, {6, 9}, {8, 8}, {9, 6}};
        long oldN = N, res = 0;
        while (N > 0) {
            if (!m.count(N % 10)) return false;
            res = res * 10 + m[N % 10];
            N /= 10;
        }
        return res != oldN;
    }
};

下面来看一种双指针的解法,这里先用一个数组 rotate 来按位记录每个数字翻转后得到的数字,用 -1 来表示非法情况,然后将数字 N 转为字符串,用两个指针 left 和 right 分别指向开头和末尾。用 while 循环进行遍历,假如此时 left 和 right 中有任何一个指向的数字翻转后是非法,直接返回 false。然后看 left 指向的数字翻转后跟 right 指向的数字是否相同,若不同,则将 res 标记为 true,然后移动 left 和 right 指针,最终返回 res 即可,参见代码如下:

解法三:

class Solution {
public:
    bool confusingNumber(int N) {
        bool res = false;
        vector<int> rotate{0, 1, -1, -1, -1, -1, 9, -1, 8, 6};
        string str = to_string(N);
        int n = str.size(), left = 0, right = n - 1;
        while (left <= right) {
            if (rotate[str[left] - '0'] == -1 || rotate[str[right] - '0'] == -1) return false;
            if (rotate[str[left] - '0'] != (str[right] - '0')) res = true;
            ++left; --right;
        }
        return res;
    }
};

Github 同步地址:

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

类似题目:

Strobogrammatic Number

Confusing Number II

参考资料:

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

https://leetcode.com/problems/confusing-number/discuss/303832/Java-Solution-using-HashMap-Similar-to-246.-Strobogrammatic-Number

https://leetcode.com/problems/confusing-number/discuss/398574/Java-0ms-12-line-solution-with-two-pointers

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


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

💰


微信打赏


Venmo 打赏

×

Help us with donation