246. Strobogrammatic Number

第一道题并不是搜索类题目，先用这个介绍一下背景。就是倒过来要相同，比如1和1，6和9，8和8。

具体做法就是，先定义镜像的关系，然后用双指针来做。

要注意的是，如果面试问到，这种题一定要先问清楚定义再做，比如说2和5，如果在8位码下，他们俩也可以说是镜像对称的。

public class Solution {
    public boolean isStrobogrammatic(String num) {
        int[] mapping = new int[128];
        mapping['0'] = '0';
        mapping['1'] = '1';
        mapping['6'] = '9';
        mapping['8'] = '8';
        mapping['9'] = '6';
        for (int i = 0; i < num.length(); ++i) {
            int j = num.length() - i - 1;
            if (mapping[num.charAt(i)] != num.charAt(j)) return false;
        }
        return true;
    }
}

247. Strobogrammatic Number II

注意：index == 0 并且 i == 0 的时候要跳过，免得在起始位置填上 0

另外注意终止条件之后的return

public class Solution {
    public List<String> findStrobogrammatic(int n) {
        List<String> result = new ArrayList<>();
        if (n == 0) return result;
        char[] num1 = {'0', '1', '8', '6', '9'};
        char[] num2 = {'0', '1', '8', '9', '6'};
        char[] number = new char[n];

        dfs(result, number, num1, num2, 0);
        return result;
    }
    private void dfs(List<String> result, char[] number, char[] num1,
                    char[] num2, int index) {
        int left = index;
        int right = number.length - index - 1;

        if (left > right) {
            result.add(new String(number)); 
            return;
        }

        if (left == right) {
            for (int i = 0; i < 3; ++i) {
                number[left] = num1[i];
                dfs(result, number, num1, num2, index + 1);
            }
        } else {
            for (int i = 0; i < num1.length; ++i) {
                if (index == 0 && i == 0) continue;
                number[left] = num1[i];
                number[right] = num2[i];
                dfs(result, number, num1, num2, index + 1);
            }
        }
    }
}

248. Strobogrammatic Number III

Google 面经里的 follow-up 是，给定一个上限 n ，输出所有上限范围内的数。

办法土了点，遍历所有 lowLen ~ highLen 区间的长度，生成所有可能的结果，考虑到区间可能是大数，我们就改一下，自己写一个 String compare 函数好了。

后来发现有点多余，可以直接用内置的 str1.compareTo(str2)，但是corner case害我在IntelliJ里面跑了好几次才发现bug。

注意compareTo的局限性，长度判断不要忘了。

public class Solution {
    int count = 0;
    public int strobogrammaticInRange(String low, String high) {
        int lowLen = low.length();
        int highLen = high.length();

        char[] num1 = {'0','1','8','6','9'};
        char[] num2 = {'0','1','8','9','6'};

        for (int i = lowLen; i <= highLen; ++i) {
            char[] number = new char[i];
            dfs(number, num1, num2, 0, low, high);
        }
        return count;
    }
    private void dfs(char[] number, char[] num1, char[] num2,
                    int index, String low, String high) {
        int left = index;
        int right = number.length - index - 1;

        if (left > right) {
            String num = new String(number);
            if ((low.length() < num.length() || low.compareTo(num) <= 0)
                    && (high.length() > num.length() || high.compareTo(num) >= 0)) count++;
            return;
        } else if (left == right) {
            for(int i = 0; i < 3; i++){
                number[left] = num1[i];
                dfs(number, num1, num2, index + 1, low, high);
            }
        } else {
            for (int i = 0; i < 5; i++) {
                if (index == 0 && i == 0) continue;
                number[left] = num1[i];
                number[right] = num2[i];
                dfs(number, num1, num2, index + 1, low, high);
            }
        }
    }
}