LeetCode——数字转罗马数字

NO.12 数字转罗马数字中等

思路一：暴力法 因为题目中说了输入范围是1~3999，所以我们可以用一个二维数组列出每一位上的所有可能：

roman[4][10]={

{“”, “I”, “II”, “III”, “IV”, “V”, “VI”, “VII”, “VIII”, “IX”}

{“”, “X”, “XX”, “XXX”, “XL”, “L”, “LX”, “LXX”, “LXXX”, “XC”}

{“”, “C”, “CC”, “CCC”, “CD”, “D”, “DC”, “DCC”, “DCCC”, “CM”}

{“”, “M”, “MM”, “MMM”,””,””,””,””,””,””}

}

然后用一个list<String>存储每一位上的阿拉伯数字的罗马数字表示，最后将String拼起来：

public String intToRoman(int num) {
    String[][] roman=new String[][]{
            {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"},
            {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"},
            {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"},
            {"", "M", "MM", "MMM","","","","","",""}
    };
    StringBuilder result=new StringBuilder();
    result.append(roman[3][num/1000%10]);//最高位，千位
    result.append(roman[2][num/100%10]);//百位
    result.append(roman[1][num/10%10]);//十位
    result.append(roman[0][num%10]);//个位
    return result.toString();
}

思路二：贪心算法 先用两个数组分别列出罗马数字和阿拉伯数字的所有特殊点，然后将当前的阿拉伯数字与当前最大的单位作比较，每次转换完一个当前最大单位就减去已转换的当前最大单位；然后再和当前最大的单位作比较如果已不足当前最大单位，就用仅次于当前最大单位的下一个最大单位去比较。。。直到当前的阿拉伯数字等于0。

例如“2978”，一开始最大单位是”M”表示”1000”，就用两个M转换出2000；

当前阿拉伯数字剩余978，已不足当前最大单位”M”,就用仅次于当前最大单位的”CM”表示”900”去比较，用一个CM转换出900；

当前阿拉伯数字剩余78，已不足当前最大单位”CM”,就用仅次于当前最大单位的”D”表示”500”去比较，还是不足，再用次大的单位”CD”表示”400”去比较，还是不足，再用次大的单位”C”表示”100”去比较，还是不足，再用次大的单位”XC”表示”90”去比较，还是不足，再用次大的单位”L”表示”50”去比较，可以用一个L转换出50；

当前阿拉伯数字剩余28，已不足当前最大单位”L”,就用仅次于当前最大单位的”XL”表示”40”去比较，还是不足，再用次大的单位”X”表示”10”去比较，可以用两个X转换出20；

当前阿拉伯数字剩余8，已不足当前最大单位”X”,就用仅次于当前最大单位的”IX”表示”9”去比较，还是不足，再用次大的单位”V”表示”5”去比较，可以用一个V转换出5；

当前阿拉伯数字剩余3，已不足当前最大单位”V”,就用仅次于当前最大单位的”IV”表示”4”去比较，还是不足，再用次大的单位”I”表示”1”去比较，可以用三个I转换出3；

当前阿拉伯数字剩余0，转换结束，输出两个M、一个CM、一个L、两个XX、一个V、三个I，即“MMCMLXXVIII”。

public String intToRoman(int num) {
//        列出所有罗马数字和阿拉伯数字的特殊点
        String[] roman={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        int[] arab={1000,900,500,400,100,90,50,40,10,9,5,4,1};
//        贪心算法
        String result="";
        int index=0;
        while (num>0){
            int count=num/arab[index];
            while (count-->0){
                result+=roman[index];
            }
            num%=arab[index];
            index++;
        }
        return result;
    }

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github

NO.12 数字转罗马数字 中等

NO.12 数字转罗马数字中等