246.Strobogrammatic Number

Tags: Easy Hash Table

Links: https://leetcode-cn.com/problems/strobogrammatic-number/

---

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

---

class Solution {
public:
    bool isStrobogrammatic(string num) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int start = 0, end = num.size() - 1;
        while (start <= end) {
            if ((num[start] == '8' && num[end] == '8') || (num[start] == '6' && num[end] == '9') || (num[start] == '9' && num[end] == '6') || (num[start] == '0' && num[end] == '0') || (num[start] == '1' && num[end] == '1')) {
                ++start; --end;
            }
            else return false;
        }

        return true;
    }
};

执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗 :6.1 MB, 在所有 C++ 提交中击败了100.00%的用户

这道题起始应该归类为哈希表，但是因为其follow up属于递归，所以暂时归类为递归。这道题起始思路很直接，字符串旋转180°相当于翻转字符串，翻转后和原字符串相同，那么只需要去判断0，1，8，6，9这些情况，之所以会有hash map，是因为出现的情况不是很多，所以可以利用hash map存储可能的情况。

class Solution {
public:
    bool isStrobogrammatic(string num) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int start = 0, end = num.size() - 1;
        unordered_map<char, char> um{{'6', '9'}, {'9', '6'},
             {'8', '8'}, {'0', '0'}, {'1', '1'}};
        while (start <= end) {
            if (um[num[start]] != num[end]) return false;
            ++start; --end;
        }

        return true;
    }
};