题目：
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.
链接： http://leetcode.com/problems/strobogrammatic-number/
题解：
验证一个数是否是strobogrammatic number。我们可以用验证Palindrome的方法，从头部和尾部向中间遍历。这里因为这种数的条件比较少，所以我用了一个HashMap来保存所有合理的可能性。空间复杂度应该也可以算是O(1)的
Time Complexity - O(n)， Space Complexity - O(1)。
public class Solution {
public boolean isStrobogrammatic(String num) {
if(num == null || num.length() == 0)
return false;
int lo = 0, hi = num.length() - 1;
Map<Character, Character> map = new HashMap<>();
map.put('0', '0');
map.put('1', '1');
map.put('6', '9');
map.put('8', '8');
map.put('9', '6');
while(lo <= hi) {
char cLo = num.charAt(lo);
if(!map.containsKey(cLo))
return false;
else if(map.get(cLo) != num.charAt(hi))
return false;
else {
lo++;
hi--;
}
}
return true;
}
}
二刷：
先建立一个查找表，然后遍历字符串的时候进行查找。表很小所以可以看做O(1)。 Stefan Pochmann还有很fancy的解法，放在reference里，很漂亮。
Java：
Time Complexity - O(n)， Space Complexity - O(1)。
public class Solution {
public boolean isStrobogrammatic(String num) {
if (num == null || num.length() == 0) {
return false;
}
Map<Character, Character> map = new HashMap();
map.put('6', '9');
map.put('9', '6');
map.put('1', '1');
map.put('8', '8');
map.put('0', '0');
int lo = 0, hi = num.length() - 1;
while (lo <= hi) {
if (map.containsKey(num.charAt(hi)) && num.charAt(lo) == map.get(num.charAt(hi))) {
lo++;
hi--;
} else {
return false;
}
}
return true;
}
}
三刷：
Java:
public class Solution {
public boolean isStrobogrammatic(String num) {
if (num == null) return false;
Map<Character, Character> map = new HashMap<>();
map.put('6', '9');
map.put('9', '6');
map.put('8', '8');
map.put('1', '1');
map.put('0', '0');
int lo = 0, hi = num.length() - 1;
while (lo <= hi) {
char loChar = num.charAt(lo);
char hiChar = num.charAt(hi);
if (!map.containsKey(loChar) || map.get(loChar) != hiChar) return false;
lo++;
hi--;
}
return true;
}
}
Reference:
https://leetcode.com/discuss/50594/4-lines-in-java