2019-03-1-算法-进化（整数转罗马数字）

亦凉 2022-03-15 05:42 36阅读 0赞

**题目描述**  
罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

字符          数值
    I             1
    V             5
    X             10
    L             50
    C             100
    D             500
    M             1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

*  I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9
 *  X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90
 *  C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900

给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。

示例 1:

输入: 3
    输出: "III"

示例 2:

输入: 4
    输出: "IV"

示例 3:

输入: 9
    输出: "IX"

示例 4:

输入: 58
    输出: "LVIII"
    解释: L = 50, V = 5, III = 3.

示例 5:

输入: 1994
    输出: "MCMXCIV"
    解释: M = 1000, CM = 900, XC = 90, IV = 4.

我的初步解答：

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

观察上面的代码，发现这一大串if else if特别的啰嗦，并且处理逻辑基本相同，所以，优化方向就出来了，整合这些逻辑分支为同一个。  
考虑到需要一个有序的key-value的数据结构，在TreeMap与LinkedHashMap之间选。

*  LinkedHashMap：底层为链表，元素顺序为写入时候的顺序；
 *  TreeMap：元素顺序可以通过实现Comparator接口自定义，默认为数字升序排列；

由于我们需要的是数字的降序排列，并且元素初始化顺序可以自定义，所以为方便，选取LinkedHashMap为本次的数据结构  
改进之后的代码如下：

public String intToRoman(int num) {
    		
    		StringBuilder sb = new StringBuilder();
    		Map<Integer, String> map = new LinkedHashMap<Integer, String>() {
    			private static final long serialVersionUID = 1L;
    			{
    				put(1000, "M");
    				put(900, "CM");
    				put(500, "D");
    				put(400, "CD");
    				put(100, "C");
    				put(90, "XC");
    				put(50, "L");
    				put(40, "XL");
    				put(10, "X");
    				put(9, "IX");
    				put(5, "V");
    				put(4, "IV");
    				put(1, "I");
    			}
    		};
    		Set<Map.Entry<Integer, String>> set = map.entrySet();
    		
    		int head =0;
    		while(num > 0) {
    			for(Map.Entry<Integer, String> e: set) {
    				if(num/e.getKey() != 0) {
    					head = num/e.getKey();
    					num -=head*e.getKey();
    					while (head >0) {
    						sb.append(e.getValue());
    						head--;
    					}
    					break;
    				}
    			}
    		}
    		
    		return sb.toString();
        }