面试经典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";
    else
        return "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;
}