LeetCode12. 整数转罗马数字

贪心算法

贪心法则：我们每次尽量使用最大的数来表示。

字典：

class Solution:
    def intToRoman(self, num: int) -> str:
        # 使用字典，从大到小记录所有的整数-罗马数字的键值对
        dic = {
        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'
        }
        ans = ''
        for key in dic:
            if num // key != 0:
                count = num // key  
                ans += dic[key] * count 
                num %= key
        return ans

列表：

class Solution:
    def intToRoman(self, num: int) -> str:
        symble = [
            (1,'I'),
            (4,'IV'),
            (5,'V'),
            (9,'IX'),
            (10,'X'),
            (40,'XL'),
            (50,'L'),
            (90,'XC'),
            (100,'C'),
            (400,'CD'),
            (500,'D'),
            (900,'CM'),
            (1000,'M')
            ]
        #因为这里没有从大到小排列，所以做一个列表反转
        symble = symble[::-1]
        roman = []
        for i,char in symble:
            while num >= i:
                num -= i
                roman.append(char)
            if num == 0:
                break
        return ''.join(roman)