LeetCode Strobogrammatic Number三

关于我的 Leetcode 题目解答，代码前往 Github：https://github.com/chenxiangcyr/leetcode-answers

LeeCode题目

LeetCode题目：246. Strobogrammatic Number
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.

class Solution {
    public boolean isStrobogrammatic(String num) {
        int i = 0;
        int j = num.length() - 1;
        
        while(i <= j) {
            // num有奇数位
            if(i == j) {
                if((num.charAt(i) - '0') == 0 || (num.charAt(i) - '0') == 1 || (num.charAt(i) - '0') == 8) {
                    return true;
                }
                else {
                    return false;
                }
            }
            else {
                if(isStrobogrammatic(num.charAt(i) - '0', num.charAt(j) - '0') == false) {
                    return false;
                }
            }
            i++;
            j--;
        }
        
        return true;
    }
    
    public boolean isStrobogrammatic(int i, int j) {
        if(i == 0) return j == 0;
        if(i == 1) return j == 1;
        if(i == 6) return j == 9;
        if(i == 8) return j == 8;
        if(i == 9) return j == 6;
        
        return false;
    }
}

LeeCode题目

LeetCode题目：247. Strobogrammatic Number II
A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
Find all strobogrammatic numbers that are of length = n.
For example,
Given n = 2, return ["11","69","88","96"].

class Solution {
    public List<String> findStrobogrammatic(int n) {
        return findStrobogrammatic(1, n);
    }
    
    public List<String> findStrobogrammatic(int start, int end) {
        if(start > end) return new ArrayList<String>(Arrays.asList(""));
        
        if(start == end)  return new ArrayList<String>(Arrays.asList("0", "1", "8"));
        
        char[] candidates = new char[]{'0', '1', '6', '8', '9'};
        
        List<String> result = new ArrayList<String>();
        
        for(char c : candidates) {
            // 第一个数字不能是0
            if((start == 1 && c !='0') || start != 1) {
                // 递归
                List<String > subSet = findStrobogrammatic(start + 1, end - 1);
                
                for(String str : subSet) {
                    StringBuilder sb = new StringBuilder();
                    sb.append(c); // start位置
                    sb.append(str);  // 中间位置
                    sb.append(findStrobogrammaticChar(c)); // end位置

                    result.add(sb.toString());
                }
            }
        }
        
        return result;
    }
    
    public char findStrobogrammaticChar(char c) {
        if(c == '0') return '0';
        if(c == '1') return '1';
        if(c == '6') return '9';
        if(c == '8') return '8';
        if(c == '9') return '6';
        
        return ' ';
    }
}

LeeCode题目

LeetCode题目：248. Strobogrammatic Number III
A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.
For example,
Given low = "50", high = "100", return 3. Because 69, 88, and 96 are three strobogrammatic numbers.
Note:
Because the range might be a large number, the low and high numbers are represented as string.

public class Solution{


    public int strobogrammaticInRange(String low, String high){
        int count = 0;
        List<String> rst = new ArrayList<String>();
        for(int n = low.length(); n <= high.length(); n++){
            rst.addAll(helper(n, n));
        }
        for(String num : rst){
            
            if((num.length() == low.length()&&num.compareTo(low) < 0 ) ||(num.length() == high.length() && num.compareTo(high) > 0)) continue;
                count++;
        }
        return count;
    }

    private List<String> helper(int cur, int max){
        if(cur == 0) return new ArrayList<String>(Arrays.asList(""));
        if(cur == 1) return new ArrayList<String>(Arrays.asList("1", "8", "0"));

        List<String> rst = new ArrayList<String>();
        List<String> center = helper(cur - 2, max);

        for(int i = 0; i < center.size(); i++){
            String tmp = center.get(i);
            if(cur != max) rst.add("0" + tmp + "0");
            rst.add("1" + tmp + "1");
            rst.add("6" + tmp + "9");
            rst.add("8" + tmp + "8");
            rst.add("9" + tmp + "6");
        }
        return rst;
    }
}