Leetcode 12. Integer to Roman

https://leetcode.com/problems/integer-to-roman/

First we have to know the rules of Roman numbers: https://en.wikipedia.org/wiki/Roman_numerals

After knowing the rules, the process is quite simple: move numbers from large to small, and create a map from Roman to usual numbers.

Solution:

# T:O(n) S:O(1)
class Solution:
    # @param {integer} num
    # @return {string}
    def intToRoman(self, num):
        val = [1000, 900, 500, 400,
                100, 90, 50, 40,
                10, 9, 5, 4, 1]
        syb = ['M', 'CM', 'D', 'CD',
                'C', 'XC', 'L', 'XL',
                'X', 'IX', 'V', 'IV', 'I']
        res, i = '', 0
        while num > 0:
            for _ in xrange(num//val[i]):
                res += syb[i]
                num -= val[i]
            i += 1
        return res

Run time: 128 ms