Integer to Roman

题目描述

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

解题方法

1、罗马数字共有7个，即I（1）、V（5）、X（10）、L（50）、C（100）、D（500）和M（1000）。

2、左减右加逻辑，以及右加不能超过三位，左减只能有1位。

• addtion notation的表达方法基本就是分隔的将单独的value加起来
• substract notation的表达方法是两个字符代表一个数，能够代表的数也是有限的

所以我们可以将能够单独表达的数字列出来

1000 900 500 400 100 90 50 40 10 9 5 4 1

罗马数字基本是从左到右，从大到小排列的，所以按照这个value array来做greedy判断，就可以得到结果

Solution

class Solution(object):
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        if not num:
            return ""
        values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
        symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
        index = 0
        result = ""
        while num:
            cur = num / values[index]
            for j in range(cur):
                result += symbols[index]
            num %= values[index]
            index += 1
        return result

Reference