top12
把数字转换成罗马数字，正常情况就是把每个字母相加，并且大字母在前，小字母在后，上边也介绍了像 4 和 9 那些特殊情况。
解法一
这个是自己的解法，主要思想就是每次取出一位，然后得到相应的罗马数字，然后合起来就行。
publicStringgetRoman(intnum,intcount){ //count 表示当前的位数，个位，十位...char[]ten={'I','X','C','M'}; //1,10,100,1000char[]five={'V','L','D'};//5,50,500Stringr=""; if(num<=3){ while(num!=0){ r+=ten[count]; num--; } } if(num==4){ r=(ten[count]+"")+(five[count]+""); } if(num==5){ r=five[count]+""; } if(num>5&&num<9){ r=five[count]+""; num-=5; while(num!=0){ r+=ten[count]; num--; } } if(num==9){ r= (ten[count] +"") + (ten[count+1] +""); } returnr; } publicStringintToRoman(intnum) { Stringr=""; intcount=0; while(num!=0){ intpop=num%10; r=getRoman(pop,count)+r; count++; num/=10; } returnr; }
时间复杂度：num 的位数 log_{10}(num)+1log10(num)+1所以时间复杂度是 O（log（n））。
空间复杂度：常数个变量，O（1）。
下边在分享一些 LeetCode 讨论里的一些解法。
解法二
https://leetcode.com/problems/integer-to-roman/discuss/6310/My-java-solution-easy-to-understand
publicStringintToRoman(intnum) { 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"}; StringBuildersb=newStringBuilder(); for(inti=0;i<values.length;i++) { while(num>=values[i]) { num-=values[i]; sb.append(strs[i]); } } returnsb.toString(); }
相当简洁了，主要就是把所有的组合列出来，因为罗马数字表示的大小就是把所有字母相加，所以每次 append 那个，再把对应的值减去就行了。
时间复杂度：不是很清楚，也许是 O（1）？因为似乎和问题规模没什么关系了。
空间复杂度：O（1）.
总
这道题感觉难度应该是 easy ，没有那么难，就是理清楚题意，然后就可以往出列举就行了。
