StrobogrammaticNumber [source code]

public class StrobogrammaticNumber {
static

public class Solution {
    public boolean isStrobogrammatic(String num) {
        char[] digits = num.toCharArray();
        int n = num.length();
        if (n == 0) return false;
        int end = n % 2 == 1 ? n / 2 + 1 : n / 2;
        for (int i = 0; i < end; i++) {
            int mirror = digits[n - 1 - i];
            if (
                (digits[i] == '0' && mirror == '0') ||
                (digits[i] == '1' && mirror == '1') ||
                (digits[i] == '6' && mirror == '9') ||
                (digits[i] == '9' && mirror == '6') ||
                (digits[i] == '8' && mirror == '8')
               ) continue;
            else return false;
        }
        return true;
    }
}

    public static void main(String[] args) {
        StrobogrammaticNumber.Solution tester = new StrobogrammaticNumber.Solution();
        assert tester.isStrobogrammatic("69") == true;
        assert tester.isStrobogrammatic("88") == true;
        assert tester.isStrobogrammatic("818") == true;
        assert tester.isStrobogrammatic("23132") == false;
        assert tester.isStrobogrammatic("0110") == true;;
    }
}

题目本身逻辑还是比较简单的, 无非就是 index 的边界怎么选择要稍微斟酌一下; 最后的速度是0(53), 最优解;

这个是 discussion 看到的一个简写版本:

public boolean isStrobogrammatic(String num) {  
    int[] map = new int[10];  
    map[0]=0;map[1]=1;map[2]=-1;map[3]=-1;map[4]=-1;map[5]=-1;map[6]=9;map[7]=-1;map[8]=8;map[9]=6;  
    int lo = 0, hi = num.length()-1;  
    while(lo<=hi) if(num.charAt(hi--)-'0' != map[num.charAt(lo++)-'0']) return false;  
    return true;  
}

比较可取的地方就是:

• 使用2pointers 而不是一个 pointer, 对于 pointer 的 range 的计算相对就没有那么复杂了;
• 使用 hashing 来完成一个类似 hashtable 的功能;

这个是一个类似的,不过用recursion 来写:

public class Solution {  
    public boolean isStrobogrammatic(String num) {  
        if (num == null)   
            return false;  

        return helper(num, 0, num.length() - 1);  
    }  

    boolean helper(String num, int lo, int hi) {  
        if (lo > hi)   
            return true;  

        char c1 = num.charAt(lo), c2 = num.charAt(hi);  

        int mul = (c1 - '0') * (c2 - '0');  

        if (mul == 1 || mul == 64 || mul == 54 || (mul == 0 && c1 == c2))  
            return helper(num, lo + 1, hi - 1);  
        else  
            return false;  
    }  
}

这个写法还有一个好处就是不用做一个 lookup table, 而是用乘积来查询, 这个想法还是不错的;

public boolean isStrobogrammatic(String num) {  
    for (int i=0, j=num.length()-1; i <= j; i++, j--)  
        if (!"00 11 88 696".contains(num.charAt(i) + "" + num.charAt(j)))  
            return false;  
    return true;  
}

这个是用另外一种思路来完成查询, 这个点子有点刁钻, 不过还是有点意思;

Problem Description

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.

Difficulty:Easy
Category:Algorithms
Acceptance:39.53%
Contributor: LeetCode
Companies
google
Related Topics
hash table math
Similar Questions
Strobogrammatic Number II Strobogrammatic Number III