012._Integer_to_Roman.md

12. Integer to Roman

题目: https://leetcode.com/problems/integer-to-roman/

难度: Medium

思路：

首先我学习了一下罗马字母是如何表示的。然后感慨，这个阿拉伯数字是多么好的发明

上图

基于的是这些个Symbol：

1	5	10	50	100	500	1000
I	V	X  	 L	 C	 D	 M

罗马数字表示法见Leetcode 013

这里有一个很棒的算法

AC代码

class Solution(object):
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        lookup = {
            'M': 1000, 
            'CM': 900, 
            'D': 500, 
            'CD': 400, 
            'C': 100, 
            'XC': 90, 
            'L': 50, 
            'XL': 40, 
            'X': 10, 
            'IX': 9, 
            'V': 5, 
            'IV': 4, 
            'I': 1
        }
        romanStr = ''

        for symbol, val in sorted(lookup.items(), key = lambda t: t[1], reverse = True):
        	while num >= val:
        		romanStr += symbol
        		num -= val
        return romanStr

因为dict本身是无序的，这里做了一个排序的操作，否则可能会出现IIII这种状况。