Integer 的构造，操作，序列化

Integer to English Words

小于 20 的数要字典;

• 十几 Tens 的，需要字典；

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

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

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

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

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

伤心的一道题, LeetCode写了7遍, 白板上也写了. FB onsite时把Integer二进制说错了. 印度小哥全程黑脸..让我也是醉了.

String[] ten = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    //String[] twenty = {"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    String[] hundred = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
    public String numberToWords(int num){
        if(num==0) return "Zero"; //key point zero
        return helper(num);
    }

    public String helper(int num){
        String ans; //key point: use else if
        if(num<20)
             ans = ten[num];
        else if(num<100)
             ans = hundred[num/10] + " " + helper(num%10); //don't forget space
        else if(num<1000)
             ans = helper(num/100) + " Hundred " + helper(num%100);
        else if(num<1000000)
             ans = helper(num/1000) + " Thousand " + helper(num%1000);
        else if(num<1000000000)
             ans = helper(num/1000000) + " Million " + helper(num%1000000);
        else
             ans = helper(num/1000000000) + " Billion " + helper(num%1000000000);
        return ans.trim(); //key point trim
    }

Roman to Integer

    public int romanToInt(String s) {

        if(s==null || s.length()==0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        map.put('I', 1); map.put('V', 5); map.put('X', 10);
        map.put('L', 50); map.put('C', 100); map.put('D', 500); map.put('M', 1000);
        int ans = 0;
        for(int i=0;i<s.length();i++){
            if(i+1<s.length() && map.get(s.charAt(i))<map.get(s.charAt(i+1))){
                ans-=map.get(s.charAt(i));
            }
            else
                ans+= map.get(s.charAt(i));
        }
        return ans;
    }

Count and Say

public class Solution {
    public String countAndSay(int n) {
        if(n<=0) {
        return "";
        }
        String nowStr = "1";
        for(int i=1;i<n;i++)
            nowStr = getNext(nowStr);
        return nowStr;
    }

    public String getNext(String str){
        int count = 0; StringBuilder sb = new StringBuilder();
        for(int i=0;i<str.length();i++){
            count++;
            if(i+1==str.length() || str.charAt(i)!=str.charAt(i+1)){ //key point: i+1==str.length() reach to end
                sb.append(count).append(str.charAt(i));
                //if(i+1<str.length())
                    count = 0;
            }
        }
        return sb.toString();
    }
}

Integer to Roman

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

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

    public String intToRoman(int num) {
            int[] values = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
    String[] strs = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"}; //key point: construct this array.


    /*
      map.put('I', 1); map.put('V', 5); map.put('X', 10);
        map.put('L', 50); map.put('C', 100); map.put('D', 500); map.put('M', 1000);
    */



    StringBuilder sb = new StringBuilder();
    for(int i=0;i<values.length;i++) {
        while(num >= values[i]) {
            num -= values[i];
            sb.append(strs[i]);
        }
    }
    return sb.toString();
    }