【leetcode】整数转罗马数字、罗马数字转整数【Python】-蒲公英云

【leetcode】整数转罗马数字、罗马数字转整数【Python】

叁歲伎倆 2022-05-09 12:03 420阅读 0赞

题目链接
在这里插入图片描述
递归算法，需要注意40~50的情况特殊性

class Solution(object):
    def intToRoman(self, num):
        if num == 0: return ''
        if num == 4: return 'IV'
        if num == 9: return 'IX'
        if num == 40: return 'XL'
        if num == 90: return 'XC'
        if num == 400: return 'CD'
        if num == 900: return 'CM'
        if num >= 1 and num <= 3:
            return 'I' * num
        if num >= 5 and num <= 8:
            return 'V' + self.intToRoman(num - 5)
        if num >= 10 and num <= 39:
            m = (int)(num / 10)
            return 'X' * m + self.intToRoman(num - 10 * m)
        if num > 40 and num <= 49:
            return 'XL' +self.intToRoman(num - 40)
        if num >= 50 and num < 90:
            return 'L' + self.intToRoman(num - 50)
        if num >= 90 and num <= 99:
            return 'XC' + self.intToRoman(num - 90)
        if num >= 100 and num <= 399:
            m = (int)(num / 100)
            return 'C' * m + self.intToRoman(num - m * 100)
        if num > 400 and num <= 499:
            return 'CD' + self.intToRoman(num - 400)
        if num >= 500 and num < 900:
            return 'D' + self.intToRoman(num - 500)
        if num > 900 and num <= 999:
            return 'CM' +self.intToRoman(num - 900)
        if num >= 1000 and num <= 4000:
            m = (int)(num / 1000)
            return 'M' * m + self.intToRoman(num - m * 1000)
print(Solution().intToRoman(2000))

可以使用字典的方式，一步一步减去，采用字典的方式

class Solution(object):
    def intToRoman(self, num):
        """ :type num: int :rtype: str """
        if num > 3999 or num < 1:
            return 0
        # 字典是无序的，所以不使用字典
        # 注意这里一定要是倒序，否则执行会有问题，让数从大往小查找适合的罗马数
        num_tuple = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
        roman_tuple = ['M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I']
        # 记录结果的字符串
        result_str = ""
        # 从整数的列表中开始遍历
        for i in range(len(num_tuple)):
            # 从大往小开始判断，num小于当前数则进行下一次循环
            # num大于当前数则进行减法运算，并取出相应位置的Roman数
            while num >= num_tuple[i]:
                num -= num_tuple[i]
                result_str += roman_tuple[i]
        return result_str

罗马数字转整数同样用字典

class Solution(object):
    def romanToInt(self, s):
        """ :type s: str :rtype: int """
        dic = { 'M':1000, 'D':500, 'C':100, 'L':50, 'X':10, 'V':5, 'I':1}
        num = 0
        for i in range(len(s)):
            if i < len(s) - 1 and dic[s[i]] < dic[s[i + 1]]:
                num -= int(dic[s[i]])
            else:
                num += int(dic[s[i]])
        return num
print(Solution().romanToInt('MCMXCIV'))