Integer 的构造，操作，序列化

Integer to English Words

• 小于 20 的数要字典;

• 十几 Tens 的，需要字典；

• 多少个 thousands 的，需要字典，从右往左 index 递增；

• 以三位数为单位处理，任何三位数都可以用 helper function + 字典解决，自带 hundred 单位。

• 0 在所有情况都代表空字符，除了 num 一开始就等于 0 的情况要返回 "Zero".

自己第一遍 AC 的版本太粗糙，就不放了。

这个版本就简洁了很多，从右向左，递归调用处理三位数的情况；

public class Solution {
    private final String[] LESS_THAN_20 = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    private final String[] TENS = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
    private final String[] THOUSANDS = {"", "Thousand", "Million", "Billion"};

    public String numberToWords(int num) {
        if(num == 0) return "Zero";
        String rst = "";
        int highPtr = 0;
        while(num != 0){
            if(num % 1000 != 0){
                rst = helper(num % 1000) + THOUSANDS[highPtr] + " " + rst;
            }
            num /= 1000;
            highPtr ++;
        }
        return rst.trim();
    }

    private String helper(int num){
        if(num == 0)
            return "";
        else if(num < 20)
            return LESS_THAN_20[num] + " ";
        else if(num < 100)
            return TENS[num / 10] + " " + helper(num % 10);
        else 
            return LESS_THAN_20[num / 100] + ' ' + "Hundred" + ' ' + helper(num % 100);
    }
}

Roman to Integer

Trivial problem. 没啥好讲的。。

public class Solution {
    public int romanToInt(String s) {
        if(s.length() == 0) return 0;

        int num = getNum(s.charAt(0));
        int prev = num;
        for(int i = 1; i < s.length(); i++){
            int cur = getNum(s.charAt(i));
            if(cur > prev){
                num -= 2 * prev;
            }
            prev = cur;
            num += cur;
        }

        return num;
    }

    private int getNum(char chr){
        switch(chr){
            case 'I':
                return 1;
            case 'V':
                return 5;
            case 'X':
                return 10;
            case 'L':
                return 50;
            case 'C':
                return 100;
            case 'D':
                return 500;
            case 'M':
                return 1000;                
            default:
                return 0;
        }
    }
}

Count and Say

这题怪怪的，我也不知道到底想考啥。。难道是迭代和递归么。。。。

public class Solution {
    public String countAndSay(int n) {
        if(n == 1) return "1";
        StringBuilder sb = new StringBuilder();
        sb.append("1");

        for(int i = 1; i < n; i++){
            String str = sb.toString();
            sb.setLength(0);
            int index = 0;
            while(index < str.length()){
                int num = str.charAt(index) - '0';
                int count = 1;
                while(index < str.length() - 1 && str.charAt(index) == str.charAt(index + 1)){
                    count ++;
                    index ++;
                }
                index ++;
                sb.append(count);
                sb.append(num);
            }
        }

        return sb.toString();
    }
}

Integer to Roman

之前那道 Roman to Integer 就弄了个 switch case ，这次可能性稍微多了点，直接开两个 1-1 onto mapping 当表查好了。

• 当可能的情况“有限”并“可数”的时候，可以自己用 array 去建 1-1 mapping 便于查询。

public class Solution {
    public String intToRoman(int num) {
        int[] nums =      {1000,  900,  500,  400,  100,   90,  50,   40,   10,    9,   5,    4,   1};
        String[] romans = { "M", "CM",  "D", "CD",  "C", "XC", "L", "XL",  "X", "IX", "V", "IV", "I"};

        StringBuilder sb = new StringBuilder();
        while(num > 0){
            for(int i = 0; i < nums.length; i++){
                if(num >= nums[i]){
                    num -= nums[i];
                    sb.append(romans[i]);
                    break;
                }
            }
        }

        return sb.toString();
    }
}

Integer to English Words

• 小于 20 的数要字典;

• 十几 Tens 的，需要字典；

• 多少个 thousands 的，需要字典，从右往左 index 递增；

• 以三位数为单位处理，任何三位数都可以用 helper function + 字典解决，自带 hundred 单位。

• 0 在所有情况都代表空字符，除了 num 一开始就等于 0 的情况要返回 "Zero".

自己第一遍 AC 的版本太粗糙，就不放了。

这个版本就简洁了很多，从右向左，递归调用处理三位数的情况；

public class Solution {
    private final String[] LESS_THAN_20 = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    private final String[] TENS = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
    private final String[] THOUSANDS = {"", "Thousand", "Million", "Billion"};

    public String numberToWords(int num) {
        if(num == 0) return "Zero";
        String rst = "";
        int highPtr = 0;
        while(num != 0){
            if(num % 1000 != 0){
                rst = helper(num % 1000) + THOUSANDS[highPtr] + " " + rst;
            }
            num /= 1000;
            highPtr ++;
        }
        return rst.trim();
    }

    private String helper(int num){
        if(num == 0)
            return "";
        else if(num < 20)
            return LESS_THAN_20[num] + " ";
        else if(num < 100)
            return TENS[num / 10] + " " + helper(num % 10);
        else 
            return LESS_THAN_20[num / 100] + ' ' + "Hundred" + ' ' + helper(num % 100);
    }
}