12. Integer to Roman (Medium)

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

Solution 1: O(n); O(1)

这题和13题是姐妹题，难度差不多，都应该算Easy.（这题的确比13题有意思些）
因为这题求得是字符串，要用append，所以应该从高位计算，即从左到右。

    /**
    * O(n);O(1)
    * 整数到罗马数：从左往右遍历，两个dict array
    * 罗马数到整数：从右往左遍历，HashMap / switch-case
    */    
    public static String intToRoman(int num) {
        if (num < 1 || num > 3999) {
            return "";
        }

        StringBuilder res = new StringBuilder();

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

        int i = 0;
        //iterate until the number becomes zero, NO NEED to go until the last element in roman array
        while (num > 0) {
            while (num >= intDict[i]) {
                num -= intDict[i];
                res.append(romanDict[i]);
            }
            i++;
        }
        return res.toString();
    }

下面写法低效，用上面的while写法好

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

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < intDict.length; i++) { //这种写法低效，用上面的while写法好
            while (num >= intDict[i]) {
                num -= intDict[i];
                sb.append(romaDict[i]);
            }
        }
        return sb.toString();
    }