[LeetCode] 1056. Confusing Number

[grandyang]

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 同步地址:

#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 题目讲解汇总(持续更新中...)