[Math]012 Integer to Roman

分类：Math
考察知识点：Math
最优解时间复杂度：**O(1) **

12. Integer to Roman

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

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

For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.

Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: 3
Output: "III"

Example 2:

Input: 4
Output: "IV"

Example 3:

Input: 9
Output: "IX"

Example 4:

Input: 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.

Example 5:

Input: 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

代码：

枚举法:

class Solution:
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        M=["","M","MM","MMM"]
        C=["","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"]
        X=["","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"]
        I=["","I","II","III","IV","V","VI","VII","VIII","IX"]
        
        return M[num//1000]+C[(num//100)%10]+X[(num//10)%10]+I[num%10]

非枚举法:

class Solution:
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        num_dict=[(1000,'M'),(900,'CM'),(500,'D'),(400,'CD'),(100,'C'),(90,'XC'),
                  (50,'L'),(40,'XL'),(10,'X'),(9,'IX'),(5,'V'),(4,'IV'),(1,'I')]
        roman_num=""
        for n in num_dict:
            if num//n[0]:
                roman_num+=(n[1]*(num//n[0]))
            num-=(num//n[0])*n[0]
        
        return roman_num

讨论：

1.这个题主要考对罗马数字的理解，有哪些特殊情况，比如900，400这些，然后需要一一考虑进去
2.枚举法利用了空间复杂度，降低了时间复杂度，其实挺好的，但是有点麻烦。
3.但是说白了这道题好像确实没啥价值，而且也不容易考到

枚举法