LeetCode 12:Integer to Roman

Given an integer, convert it to a roman numeral.

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

 

题目很简短,将整型数字转换成罗马数字,问题变成了了解罗马数字的规律了,网上搜了下

记数方法

基本字符
I
V
X
L
C
D
M
相应的阿拉伯数字表示为
1
5
10
50
100
500
1000
  1. 相同的数字连写、所表示的数等于这些数字相加得到的数、如:Ⅲ=3;
  2. 小的数字在大的数字的右边、所表示的数等于这些数字相加得到的数、 如:Ⅷ=8、Ⅻ=12;
  3. 小的数字(限于 I、X 和 C)在大的数字的左边、所表示的数等于大数减小数得到的数、如:Ⅳ=4、Ⅸ=9;
  4. 正常使用时、连写的数字重复不得超过三次;
  5. 在一个数的上面画一条横线、表示这个数扩大 1000 倍。

顺便看了下罗马数字的历史,比如3999,换成罗马数字就是:MMM CM XC IX,顺序从高位到低位,每一位需要考虑的边界值包括1,4,5,9

直接分支写出所有的情况

package com.maoxiaomeng;

/**
* @author lihui
* @date 2018/3/26 12:31
*/

class Solution {
/**
* 罗马字符 I V X L C D M
* 整数数字 1 5 10 50 100 500 1000
* 3999 = MMM CM XC IX
* @param num
* @return romanNum
*/
String romanNum = "";
public String intToRoman(int num) {

if (num >= 1000) {
romanNum += "M";
num -= 1000;
} else if (num >= 900) {
romanNum += "CM";
num -= 900;
} else if (num >= 500) {
romanNum += "D";
num -= 500;
} else if (num >= 400) {
romanNum += "CD";
num -= 400;
} else if (num >= 100) {
romanNum += "C";
num -= 100;
} else if (num >= 90) {
romanNum += "XC";
num -= 90;
} else if (num >= 50) {
romanNum += "L";
num -= 50;
} else if (num >= 40) {
romanNum += "XL";
num -= 40;
} else if (num >= 10) {
romanNum += "X";
num -= 10;
} else if (num >= 9) {
romanNum += "IX";
num -= 9;
} else if (num >= 5) {
romanNum += "V";
num -= 5;
} else if (num >= 4) {
romanNum += "IV";
num -= 4;
} else if (num >= 1) {
romanNum += "I";
num -= 1;
} else {
return romanNum;
}
intToRoman(num);

return romanNum;
}
}

假如个位不是0,1,4,5,9,那么一定会走到else里num=0,最终返回,而不继续递归使得num为负了;如果个位是这5个数字,就不会走到else

既然每个分支了,比较的整数和append的roman字符串是一一对应的,可以直接定义两个数组,这些分支放到一个循环里,就美观很多

package com.maoxiaomeng;

/**
* @author lihui
* @date 2018/3/26 12:31
*/

class Solution {
/**
* 罗马字符 I V X L C D M
* 整数数字 1 5 10 50 100 500 1000
* 3999 = MMM CM XC IX
* @param num
* @return romanNum
*/
public String intToRoman(int num) {
StringBuilder sb = new StringBuilder();
int[] nums = {1000, 900, 500, 400, 100,
90, 50, 40, 10, 9, 5, 4, 1};
String[] romanNums = {"M", "CM", "D", "CD",
"C", "XC", "L", "XL",
"X", "IX", "V", "IV", "I"};
for (int i = 0; i < nums.length; i++) {
while (num >= nums[i]) {
sb.append(romanNums[i]);
num -= nums[i];
}
}
return sb.toString();
}
}

代码质量真的很重要

发表评论