面试经典150题——整数转罗马数字

本文主要是介绍面试经典150题——整数转罗马数字，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

面试经典150题 day18

- - 题目来源
  - 我的题解
  - - 方法一模拟
    - 方法二不使用额外空间的方法

题目来源

力扣每日一题；题序：12

我的题解

方法一模拟

俗称狗屎代码哈哈哈哈

时间复杂度：O(K)。K=13
空间复杂度：O(1)

public String intToRoman(int num) {Map<Integer,String> map=new HashMap<>();map.put(1,"I");map.put(4,"IV");map.put(5,"V");map.put(9,"IX");map.put(10,"X");map.put(40,"XL");map.put(50,"L");map.put(90,"XC");map.put(100,"C");map.put(400,"CD");map.put(500,"D");map.put(900,"CM");map.put(1000,"M");StringBuilder sb=new StringBuilder();int count=0;if(num>=1000){count=num/1000;num=num-count*1000;for(int i=0;i<count;i++)sb.append(map.get(1000));}if(num>=900){count=num/900;num=num-900;if(count!=0)sb.append(map.get(900));}if(num>=500){count=num/500;num=num-500;if(count!=0)sb.append(map.get(500));}if(num>=400){count=num/400;num=num-400;if(count!=0)sb.append(map.get(400));}if(num>=100){count=num/100;num=num-count*100;for(int i=0;i<count;i++)sb.append(map.get(100));}if(num>=90){count=num/90;num=num-90;if(count!=0)sb.append(map.get(90));}if(num>=50){count=num/50;num=num-50;if(count!=0)sb.append(map.get(50));}if(num>=40){count=num/40;num=num-40;if(count!=0)sb.append(map.get(40));}if(num>=10){count=num/10;num=num-count*10;for(int i=0;i<count;i++)sb.append(map.get(10));}if(num>=9){count=num/9;num=num-9;if(count!=0)sb.append(map.get(9));}if(num>=5){count=num/5;num=num-5;if(count!=0)sb.append(map.get(5));}if(num>=4){count=num/4;num=num-4;if(count!=0)sb.append(map.get(4));}if(num>=1){count=num/1;num=num-count;for(int i=0;i<count;i++)sb.append(map.get(1));}return sb.toString();
}

方法二不使用额外空间的方法

其实和方法一相同，只是进行了一些封装。getStr函数按理说不应该这样写，可以使用TreeMap使得代码简洁，但是发现使用TreeMap之后，运行时间差的有点多。

时间复杂度：O(n)
空间复杂度：O(1)

public  String intToRoman(int num) {StringBuilder sb=new StringBuilder();while(num>0){String s=getStr(num);sb.append(s);num-=getVal(s);}return sb.toString();
}
public  String getStr(int num){if(num>=1000)return "M";else if(num>=900)return "CM";else if(num>=500)return "D";else if(num>=400)return "CD";else if(num>=100)return "C";else if(num>=90)return "XC";else if(num>=50)return "L";else if(num>=40)return "XL";else if(num>=10)return "X";else if(num==9)return "IX";else if(num>=5)return "V";else if(num==4)return "IV";else if(num>=1)return "I";elsereturn "error";
}
public  int getVal(String str) {switch(str) {case "I": return 1;case "V": return 5;case "X": return 10;case "L": return 50;case "C": return 100;case "D": return 500;case "M": return 1000;case "IV": return 4;case "IX": return 9;case "XL": return 40;case "XC": return 90;case "CD": return 400;case "CM": return 900;}return 0;
}

//将上述的方式改为哈希表简化代码
TreeMap<Integer,String> numToRoman;
Map<String, Integer> romanToNum;
public String intToRoman(int num) {init();StringBuilder sb=new StringBuilder();while(num>0){String str=getStr(num);sb.append(str);num-=romanToNum.get(str);}return sb.toString();
}
public void init(){numToRoman=new TreeMap<>((a,b)->b-a);numToRoman.put(1,"I");numToRoman.put(4,"IV");numToRoman.put(5,"V");numToRoman.put(9,"IX");numToRoman.put(10,"X");numToRoman.put(40,"XL");numToRoman.put(50,"L");numToRoman.put(90,"XC");numToRoman.put(100,"C");numToRoman.put(400,"CD");numToRoman.put(500,"D");numToRoman.put(900,"CM");numToRoman.put(1000,"M");romanToNum = new HashMap<>();for (Map.Entry<Integer,String> entry : numToRoman.entrySet()) {romanToNum.put(entry.getValue(), entry.getKey());}
}
public String getStr(int num){String res="";for (Map.Entry<Integer,String> entry : numToRoman.entrySet()) {if(num>=entry.getKey()){res=entry.getValue();break;}}return res;
}