42

13. Roman to Integer

这道题害我看了三个多小时维基百科，从图利乌斯改革一直看到凯撒遇刺，从十字军东征看到君士坦丁堡沦陷。不由得让我想起那个电影，这个男人来自地球。

就注意一下罗马数字的特点，小的数在大的的数前面就是减去小的数，在后面就是往上加，减去的方式就是减自己两回，这样比较干净。

public class Solution {
    public int romanToInt(String s) {
        if (s == null || 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;
        }
    }
}

12. Integer to Roman

罗马数字有几个限制：

• 只有I C X可以出现在左边用作被减的数字，比如45不可以写成VL，只能是XLV

• 左减时不可跨越一个位值。比如，99不可以用IC（100-1）表示，而是用XCIX（[100-10]+[10-1]）表示。

  比如799不是IDCCC，而是DCCXCIX

• 左减数字必须为一位，比如8写成VIII，而非IIX。

• 右加数字不可连续超过三位，比如14写成XIV，而非XIIII。

所以先把可能的情况全部写出来有利于减少corner case。

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

{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}; { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

很巧妙的做法，注意break

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();
    }
}

273. Integer to English Words

其实挺麻烦的，需要考虑的东西很多。

• 小于 20 的数要字典；

• 十几 Tens 的，需要字典；

• 多少个 thousands 的，需要字典，

• 从右往左 index 递增，用取余的方式处理；

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

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

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);
    }
}

8. String to Integer (atoi)

下一章DFA详细讲。

public class Solution {
    public int myAtoi(String str) {
        str = str.trim();

        int sign = 1;
        int num = 0;
        char state = 's';

        for (int i = 0; i < str.length(); ++i) {
            state = DFA(state, str.charAt(i));
            if (state == 'N') sign = -1;
            if (state == 'F') return num * sign;

            if (state == 'S') {
                int val = str.charAt(i) - '0';
                int next = num * 10 + val;
                if (next / 10 != num) return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
                num = next;
            }
        }
        if (state == 'P' || state == 'N' || state == 's') return 0;
        return num * sign;
    }
    private char DFA(char state, char curt) {
        switch (state) {
            case 's':
                if (Character.isDigit(curt)) return 'S';
                if (curt == '+') return 'P';
                if (curt == '-') return 'N';
                return 'F';
            case 'P':
                if (Character.isDigit(curt)) return 'S';
                else return 'F';
            case 'N':
                if (Character.isDigit(curt)) return 'S';
                else return 'F';
            case 'S':
                if (Character.isDigit(curt)) return 'S';
                else return 'F';
            default:
                return 'F';
        }
    }
}

38. 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)) {
                    index++;
                    count++;
                }
                index++;
                sb.append(count);
                sb.append(num);
            }
        }
        return sb.toString();
    }
}