Skip to content

012 Integer to Roman

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这种状况。



回到顶部