How to Check If a Integer is a Strobogrammatic Number?

  • 时间:2020-10-11 15:48:46
  • 分类:网络文摘
  • 阅读:78 次

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Write a function to determine if a number is strobogrammatic. The number is represented as a string.

Example 1:
Input: “69”
Output: true

Example 2:
Input: “88”
Output: true

Example 3:
Input: “962”
Output: false

The digits of 1, 6, 9, 8, 0 when rotated 180 degrees are valid while the rest are invalid. Therefore, if we meet invalid digits, we can simply return false. Otherwise, we can construct the rotated version and then compare to the origin – a strobogrammatic number if its rotated version is the same.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool isStrobogrammatic(string num) {
        string x = "";
        for (int i = 0; i < num.size(); ++ i) {
            switch (num[i] - 48) {
                case 2:
                case 3:
                case 4:
                case 5:
                case 7: return false;
                case 1: x = "1" + x; break;
                case 6: x = "9" + x; break;
                case 9: x = "6" + x; break;
                case 8: x = "8" + x; break;
                case 0: x = "0" + x; break;
            }
        }
        return x == num;
    }
};
class Solution {
public:
    bool isStrobogrammatic(string num) {
        string x = "";
        for (int i = 0; i < num.size(); ++ i) {
            switch (num[i] - 48) {
                case 2:
                case 3:
                case 4:
                case 5:
                case 7: return false;
                case 1: x = "1" + x; break;
                case 6: x = "9" + x; break;
                case 9: x = "6" + x; break;
                case 8: x = "8" + x; break;
                case 0: x = "0" + x; break;
            }
        }
        return x == num;
    }
};

The string concatenation may take O(N) complexity in the worst case, thus the above complexity is actually O(N^2). If we think about it, we don’t need to construct the rotated version, we just need to check if the current digit when rotated equals to another digit at the other side, thus we have the following improved version, which just runs at O(N) and O(1) space complexity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool isStrobogrammatic(string num) {
        int len = num.size();
        for (int i = 0; i < len; ++ i) {
            switch (num[i] - 48) {
                case 2:
                case 3:
                case 4:
                case 5:
                case 7: return false;
                case 6: if ('9' != num[len - 1 - i]) return false; break;
                case 9: if ('6' != num[len - 1 - i]) return false; break;
                case 1:
                case 8: 
                case 0: if (num[i] != num[len - 1 - i]) return false; break;
            }
        }
        return true;
    }
};
class Solution {
public:
    bool isStrobogrammatic(string num) {
        int len = num.size();
        for (int i = 0; i < len; ++ i) {
            switch (num[i] - 48) {
                case 2:
                case 3:
                case 4:
                case 5:
                case 7: return false;
                case 6: if ('9' != num[len - 1 - i]) return false; break;
                case 9: if ('6' != num[len - 1 - i]) return false; break;
                case 1:
                case 8: 
                case 0: if (num[i] != num[len - 1 - i]) return false; break;
            }
        }
        return true;
    }
};

To generate the Strobogrammatic numbers of Size N, we can still use the Recursive Depth First Search Algorithm: Depth First Search Algorithm to Find the Strobogrammatic Number of Given Length

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
问题奶粉不断涌现,奶粉监管怎么了?  保健食品营销骗局令人深恶痛绝  清明时节,可适当多吃寒性食物  饮食养生:越吃越聪明的健康食品  酒鬼酒被曝塑化剂严重超标事件  光明牛奶“酸败门”牛奶变质事件  古井贡酒用食用酒精勾兑生产事件  伊利公司部分批次奶粉出现汞超标  立顿茶系列饮品被指农药超标  雅培配方奶粉被曝不符合安全标准 
评论列表
添加评论