[Leetcode 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.

解题思路

我们用哈希表保存每个可以翻转的字符翻转后对应的字符，然后对每一位数字进行翻转，检查翻转后的数字和原来的数字是否相等即可。

示例代码 (cpp)

class Solution {
private:
    unordered_map<int,int> dict = {{0,0},{1,1},{6,9},{8,8},{9,6}};
public:
    bool confusingNumber(int N) {
        int rotate = 0;
        int init = N;
        while (init != 0) {
            int digit  = init % 10;
            if (!dict.count(digit)) {
            	return false;
            }
            rotate = rotate * 10 + dict[digit];
            init = init / 10;
        }
        return postNum != N;
    }
};

示例代码 (java)

class Solution {
    public boolean confusingNumber(int N) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(6, 9);
        map.put(9, 6);
        map.put(0, 0);
        map.put(1, 1);
        map.put(8, 8); 
        int newNum = 0;
        int x = N;
        while (x != 0) {
            int remainder = x % 10;
            if (!map.containsKey(remainder)) 
                return false;
            if(newNum > Integer.MAX_VALUE/10)
                return false;
            newNum = newNum * 10 + map.get(remainder);
            x /= 10;
        }    
        return N == newNum? false: true;
    }
}

示例代码 (python)

class Solution:
    def confusingNumber(self, N: int) -> bool:
        S = str(N)
        rotation = {"0" : "0", "1" : "1", "6" : "9", "8" : "8", "9" : "6"}
        result = []        
        for c in S[::-1]:           # iterate in reverse
            if c not in rotation:
                return False
            result.append(rotation[c])                
        return "".join(result) != S

复杂度分析

时间复杂度: O(N)
空间复杂度: O(1)

归纳总结

我们在Youtube上更新了视频讲解，欢迎关注！