Integer to Roman

Question

Given an integer, convert it to a roman numeral.

The number is guaranteed to be within the range from 1 to 3999.

Example

4 -> IV

12 -> XII

21 -> XXI

99 -> XCIX

Thoughts

首先要知道roman数字的对应

1 -> I
5 -> V
10 -> X
50 -> L
100 -> C
500 -> D
1000 -> M

我们已经知道了这个数的范围是1-3999 罗马数字有两种notation

• additive notation

3 -> III

• subtractive notation

4 -> IV

而数字比如49是XLIX, 代表40 + 9， 39是XXXIX

我们已经知道了各种addtive和subtractive的数字是什么，就可以像求一个表达式一样求出个个symbols出现的次数

Num = f1 * 1000 + f2 * 9000 + f3 * 500 + f4 * 400 + ........  f13 * 1

只要按从大到小的顺序求出各个因子，将对于的symbol放到结果里就可以

Solution

class Solution:
    # @param {int} n The integer
    # @return {string} Roman representation
    def intToRoman(self, n):
        # Write your code here
        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"]

        result = ""
        index = 0
        while n:
            k = n / values[index]
            for j in range(k):
                result += symbols[index]
            n = n % values[index]
            index += 1

        return result