12、整数转罗马数字
问题描述
问题分析
分析题目，可以这样考虑：按照罗马字符所表示的范围进行分层，依次匹配罗马字符，然后更新原数字，迭代进行，最终得到结果。
第一种解法：比较范围+迭代
罗马字符所表示的范围为：
- 1000-3999 M
- 900-1000 CM
- 500-900 D
- 400-500 CD
- 100-400 C
- 90-100 XC
- 50-90 L
- 40-50 XL
- 10-40 X
- 9 IX
- 5-9 V
- 4 IV
- 1-4 I
主要的时间花费在迭代时的比较上。
Java代码
class Solution {public String intToRoman(int num) {String result = "";while (num > 0){if (num >= 1000){num -= 1000;result = result+"M";}else if (num >= 900 && num < 1000){num -= 900;result = result+"CM";}else if (num >= 500 && num < 900){num -= 500;result = result+"D";}else if (num >= 400 && num < 500){num -= 400;result = result+"CD";}else if (num >= 100 && num < 400){num -= 100;result = result+"C";}else if (num >= 90 && num < 100){num -= 90;result = result+"XC";}else if (num >= 50 && num < 90){num -= 50;result = result+"L";}else if (num >= 40 && num < 50){num -= 40;result = result+"XL";}else if (num >= 10 && num < 40){num -= 10;result = result+"X";}else if (num >= 9 && num < 10){num -= 9;result = result+"IX";}else if (num >= 5 && num < 9){num -= 5;result = result+"V";}else if (num >= 4 && num < 5){num -= 4;result = result+"IV";}else if (num >= 1 && num < 4){num -= 1;result = result+"I";}}return result;}
}
结果分析
以上代码的执行结果：
| 执行时间 | 内存消耗 |
|---|---|
| 25ms | 41.2MB |
第二种解法：记录法（优化）
第一种方法的时间主要花费在比较上，数字在减小，但是每次还是从范围1000开始比较，进行了很多重复而无意义的比较操作。我们可以用记录法记录上次比较结束的地方，下次比较就直接从记录的地方开始即可。
Java代码
class Solution {public String intToRoman(int num) {StringBuilder sb = new StringBuilder();int[] value = {1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000};String[] symbol = {"I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"};int n = value.length;for(int i = n - 1; i >= 0; i--) {if(num >= value[i]) {int count = num / value[i];num %= value[i];while(count-- > 0) {sb.append(symbol[i]);}}}return sb.toString();}
}
结果分析
以上代码的执行结果：
| 执行时间 | 内存消耗 |
|---|---|
| 21ms | 38.1MB |
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！