[leetcode]IntegerToRoman

oj.leetcode.com/problems/integer-to-roman/

 

nteger to Roman
Total Accepted: 7321 Total Submissions: 22682

Given an integer, convert it to a roman numeral.

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

 在转换之前先要了解一下罗马数字的相关限制：

写道

在解本题之前要先搞清楚罗马数字的相关限制：
重复数次：一个罗马数字重复几次，就表示这个数的几倍。
右加左减：
  在较大的罗马数字的右边记上较小的罗马数字，表示大数字加小数字。
  在较大的罗马数字的左边记上较小的罗马数字，表示大数字减小数字。
  左减的数字有限制，仅限于I(1)、X(10)、C(100)。比如45不可以写成VL，只能是XLV
  但是，左减时不可跨越一个位数。比如，99不可以用IC（100 - 1）表示，而是用XCIX（[100 - 10] + [10 - 1]）表示。（等同于阿拉伯数字每位数字分别表示。） 
  左减数字必须为一位，比如8写成VIII，而非IIX。 
  右加数字不可连续超过三位，比如14写成XIV，而非XIIII。
加线乘千：
  在罗马数字的上方加上一条横线或者加上下标的Ⅿ，表示将这个数乘以1000，即是原数的1000倍。
  同理，如果上方有两条横线，即是原数的1000000（1000^{2}）倍。
数码限制：
  同一数码最多只能出现三次，如40不可表示为XXXX，而要表示为XL。
  例外：由于IV是古罗马神话主神朱庇特（即IVPITER，古罗马字母里没有J和U）的首字，因此有时用IIII代替Ⅳ。

 虽然自己的代码也AC了，但是感觉毫无技术含量，只是单纯的判断打印，长达60+行，哎。。。看了某位大神的代码。。。。还是贴人家的吧

典型的贪心算法：

	public String intToRoman(int num) {
		String[] roman = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
		int[] number = {1000,900,500,400, 100, 90,  50, 40, 10, 9, 5, 4, 1};
		StringBuilder str = new StringBuilder();
		for(int i = 0;num != 0; i++){
			while(num >= number[i]){
				num -= number[i];
				str.append(roman[i]);
			}
		}
		return str.toString();
	}