题目描述(中等难度)

12. Integer to Roman - 图1

把数字转换成罗马数字,正常情况就是把每个字母相加,并且大字母在前,小字母在后,上边也介绍了像 4 和 9 那些特殊情况。

解法一

这个是自己的解法,主要思想就是每次取出一位,然后得到相应的罗马数字,然后合起来就行。

  1. public String getRoman(int num,int count){ //count 表示当前的位数,个位,十位...
  2. char[]ten={'I','X','C','M'}; //1,10,100,1000
  3. char[]five={'V','L','D'};//5,50,500
  4. String r="";
  5. if(num<=3){
  6. while(num!=0){
  7. r+=ten[count];
  8. num--;
  9. }
  10. }
  11. if(num==4){
  12. r=(ten[count]+"")+(five[count]+"");
  13. }
  14. if(num==5){
  15. r=five[count]+"";
  16. }
  17. if(num>5&&num<9){
  18. r=five[count]+"";
  19. num-=5;
  20. while(num!=0){
  21. r+=ten[count];
  22. num--;
  23. }
  24. }
  25. if(num==9){
  26. r = (ten[count] + "") + (ten[count + 1] + "");
  27. }
  28. return r;
  29. }
  30. public String intToRoman(int num) {
  31. String r="";
  32. int count=0;
  33. while(num!=0){
  34. int pop=num%10;
  35. r=getRoman(pop,count)+r;
  36. count++;
  37. num/=10;
  38. }
  39. return r;
  40. }

时间复杂度:num 的位数

12. Integer to Roman - 图2

所以时间复杂度是 O(log(n))。

空间复杂度:常数个变量,O(1)。

下边在分享一些 LeetCode 讨论里的一些解法。

解法二

https://leetcode.com/problems/integer-to-roman/discuss/6310/My-java-solution-easy-to-understand

  1. public String intToRoman(int num) {
  2. int[] values = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
  3. String[] strs = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
  4. StringBuilder sb = new StringBuilder();
  5. for(int i=0;i<values.length;i++) {
  6. while(num >= values[i]) {
  7. num -= values[i];
  8. sb.append(strs[i]);
  9. }
  10. }
  11. return sb.toString();
  12. }

相当简洁了,主要就是把所有的组合列出来,因为罗马数字表示的大小就是把所有字母相加,所以每次 append 那个,再把对应的值减去就行了。

时间复杂度:不是很清楚,也许是 O(1)?因为似乎和问题规模没什么关系了。

空间复杂度:O(1).

解法三

https://leetcode.com/problems/integer-to-roman/discuss/6376/Simple-JAVA-solution

  1. public String intToRoman(int num) {
  2. String M[] = {"", "M", "MM", "MMM"};//0,1000,2000,3000
  3. String C[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};//0,100,200,300...
  4. String X[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};//0,10,20,30...
  5. String I[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};//0,1,2,3...
  6. return M[num/1000] + C[(num%1000)/100]+ X[(num%100)/10] + I[num%10];
  7. }

这就更加暴力了,把每位的情况都列出来然后直接返回,但思路清晰明了呀。

时间复杂度:O(1)或者说是 num 的位数,不是很确定。

空间复杂度:O(1)。

这道题感觉难度应该是 easy ,没有那么难,就是理清楚题意,然后就可以往出列举就行了。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话,可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法,强烈推荐一个我之前学过的课程,可以点击 这里 查看详情