问题描述
https://leetcode.com/problems/integer-to-roman/
解决思路
用int数组value保存数字，用String数组保存对应的罗马数字，若num大于value的值，则将其从num中减去，并且将对应的罗马数字通过stringBuilder加进去。
代码（07/13）
class Solution {
public String intToRoman(int num) {
//use to array to cordinate value and symbol
int[] value = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
String[] symbol = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
StringBuilder sb = new StringBuilder();
for(int i = 0; i < value.length; i++){
while(num >= value[i]) {
num -= value[i];
sb.append(symbol[i]);
}
}
//convert StringBuilder to String
return sb.toString();
}
}
效率探究
时间效率：O(n^2)
空间效率：O(n)
代码(11/30)
class Solution {
public String intToRoman(int num) {
//use hashmap to store Roman-Number
//also use hashmap to store 4 9 40 90 400 and 900
//use while loop to do judge, until it comes to 0
//judge remain number that which range it belongs to
HashMap<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");
//store the roman numeral
StringBuilder sb = new StringBuilder();
while(num > 0){
if(num >= 1000){
num -= 1000;
sb.append(map.get(1000));
}else if(num >= 900 && num < 1000){
num -= 900;
sb.append(map.get(900));
}else if(num >= 500 && num < 900){
num -= 500;
sb.append(map.get(500));
}else if(num >= 400 && num < 500){
num -= 400;
sb.append(map.get(400));
}else if(num >= 100 && num < 400){
num -= 100;
sb.append(map.get(100));
}else if(num >= 90 && num < 100){
num -= 90;
sb.append(map.get(90));
}else if(num >= 50 && num < 90){
num -= 50;
sb.append(map.get(50));
}else if(num >= 40 && num < 50){
num -= 40;
sb.append(map.get(40));
}else if(num >= 10 && num < 40){
num -= 10;
sb.append(map.get(10));
}else if(num >= 9 && num < 10){
num -= 9;
sb.append(map.get(9));
}else if(num >= 5 && num < 9){
num -= 5;
sb.append(map.get(5));
}else if(num >= 4 && num < 5){
num -= 4;
sb.append(map.get(4));
}else if(num >= 1 && num < 4){
num -= 1;
sb.append(map.get(1));
}
}
String res = "" + sb;
return res;
}
}
效率探究
时间效率：O(n)
空间效率：O(n)
