Integer to rome

。題目假設

給一個整數轉換成羅馬數字

。重要問題

要如何有效的轉換，因為羅馬數字的 4, 9 開頭要特別處理

。直覺

從最小位開始將數字分離，再看看數字是多少，然後append 到 StringBuilder 上

。解決方法可行性

照著直覺做有個問題，還要判斷現在這位是個位、十位、還是百位，還要判斷 1, 4, 5, 9的關係，

寫下去會非常長一大串，一定有更好的解法

正面想不出來就反面想！

。解決方案

一個數字，如果有最大可以表示，那輪不到比她小的，像是 949 ，一定是 900 先輸出，輪不到500 or 400

這樣想的話，那可以用減的，從1000開始減，可以減的話就輸出對應的羅馬數字

。資料結構

一維陣列

。複雜度

O(n)

。遇到的困難點、想錯的地方

public String intToRoman(int num) {
    if (num <= 0) {
        return "";
    }

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

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