Strobogrammatic

两个指针，头尾往中间扫，如果不能匹配上则报错

考点： HashMap的运用 头尾指针法的使用

public class Solution {
    public boolean isStrobogrammatic(String num) {
        if(num == null || num.length() == 0) {
            return false;
        }

        HashMap<Character, Character> map = new HashMap<>();
        map.put('0','0');
        map.put('1','1');
        map.put('8','8');
        map.put('6','9');
        map.put('9','6');

        int n = num.length();
        for(int i = 0, j = n - 1; i <= j; i++, j--) {
            char c = num.charAt(i);
            if(!map.containsKey(c) || map.get(c) != num.charAt(j)) {
                return false;
            }
        }
        return true;
    }
}

Strobogrammatic Number II

找出所有长度为n的Strobogrammatic num。

用dfs的方法，从两边向中间构造，最中心的数是0，1，8.

• 前后是对称的
• 第一个数字不能是0
• 用数组就可以不用backtracking，直接覆盖就可以了
• 中间的数字只能是0，1，8

public class Solution {
    public List<String> findStrobogrammatic(int n) {
        List<String> result = new ArrayList<>();
        char[] s1 = {'0', '1', '8', '6', '9'};
        char[] s2 = {'0', '1', '8', '9', '6'};
        char[] num = new char[n];

        dfs(result, num, s1, s2, 0);
        return result;
    }

    private void dfs(List<String> result, char[] num, char[] s1, char[] s2, int index) {
        int left = index;
        int right = num.length - 1 - index;

        if(left > right) {
            result.add(new String(num));
            return;
        }
        // reach the center of the number
        if(left == right) {
            for(int i = 0; i < 3; i++) {
                num[left] = s1[i];
                dfs(result, num, s1, s2, index + 1);
            }
        } else {
            for(int i = 0; i < 5; i++) {
                // 第一个数不能是0
                if(index == 0 && i == 0) {
                    continue;
                }
                num[left] = s1[i];
                num[right] = s2[i];
                dfs(result, num, s1, s2, index + 1);
            }
        }
    }
}

Strobogrammatic Number III

找出一个范围里面所有的s数

可以直接用内置的 str1.compareTo(str2) 来判断这个数是否在区间里面。

遍历所有 lowLen ~ highLen 区间的长度，生成所有可能的结果

这道题是之前那两道Strobogrammatic Number II和Strobogrammatic Number的拓展，又增加了难度，让我们找到给定范围内的对称数的个数，我们当然不能一个一个的判断是不是对称数，我们也不能直接每个长度调用第二道中的方法，保存所有的对称数，然后再统计个数，这样OJ会提示内存超过允许的范围，所以我们的解法是基于第二道的基础上，不保存所有的结果，而是在递归中直接计数，根据之前的分析，需要初始化n=0和n=1的情况，然后在其基础上进行递归，递归的长度len从low到high之间遍历，然后我们看当前单词长度有没有达到len，如果达到了，我们首先要去掉开头是0的多位数，然后去掉长度和low相同但小于low的数，和长度和high相同但大于high的数，然后结果自增1，然后分别给当前单词左右加上那五对对称数，继续递归调用.

public class Solution {
    int count = 0;
    public int strobogrammaticInRange(String low, String high) {
        char[] s1 = {'0', '1', '8', '6', '9'};
        char[] s2 = {'0', '1', '8', '9', '6'};
        int l1 = low.length();
        int l2 = high.length();

        for(int i = l1; i <= l2; i++) {
            char[] num = new char[i];
            dfs(num, s1, s2, low, high, 0);
        }
        return count;
    }

    private void dfs(char[] num, char[] s1, char[] s2, String low, String high, int index) {
        int left = index;
        int right = num.length - 1 - index;

        if(left > right) {
            String num1 = new String(num);
            // 排除法，正面不行就想办法反过来
            if( (num1.length() == low.length() && (num1.compareTo(low) < 0)) ||
                (num1.length() == high.length() && (num1.compareTo(high) > 0)) ) {
                return;
            } else {
                count++;
            }
            return;
        }

        if(left == right) {
            for(int i = 0; i < 3; i++) {
                num[left] = s1[i];
                dfs(num, s1, s2, low, high, index + 1);
            }
        } else {
            for(int i = 0; i < 5; i++) {
                if(index == 0 && i == 0) {
                    continue;
                }
                num[left] = s1[i];
                num[right] = s2[i];
                dfs(num, s1, s2, low, high, index + 1);
            }
        }
    }
}