leetcode解题: Strobogrammatic Number (246)

发表于 | 分类于

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.

For example, the numbers “69”, “88”, and “818” are all strobogrammatic.

解法1：HashMap, Two pointers, O(N)

题目的意思是一个数倒过来之后和原数一样，那么满足这种性质的单个的数只有0，1，6，8，9. 其中6和9只能搭配使用.
本题用一个hashmap来存储对应的关系可以使解法变得比较干净. 6->9, 9->6, 0，1，8 对应自己。用两个指针，从两边往中间扫描，只有经过映射后的数值相等的情况下颠倒才能保持原数。
C++

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) {
        unordered_map<char, char> map;
        map['0'] = '0';
        map['1'] = '1';
        map['6'] = '9';
        map['8'] = '8';
        map['9'] = '6';
        int left = 0, right = num.length() - 1;
        while (left <= right) {
            if (map[num[left]] != num[right]) {
                return false;
            }
            ++left;
            --right;
        }
        return true;
    }
};

Java

1