整数转罗马数字

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param n int整型
# @return string字符串
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/7649cde9711f42da81209819b790a640?tpId=196&tqId=40451&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    参考：
        大神：牛客849220173号
    算法：
        1. 建立哈希表，键：数字，值：数字对应的罗马数字，总共有13种关键数字，使用nums存储这13种数字，按照从大到小顺讯
        2. 遍历nums：
            若n == num，刚好解析完成；
            否则，若n > num，进行整除和取余操作，累加结果
    复杂度：
        时间复杂度：O(1)
        空间复杂度：O(1)
    """

    def ArabicToRoman(self, n):
        # write code here
        hashMap = {1000: "M", 900: "CM", 500: "D", 400: "CD", 100: "C", 90: "XC", 50: "L", 40: "XL", 10: "X", 9: "IX",
                   5: "V", 4: "IV", 1: "I", }
        nums = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]

        res = ""
        for num in nums:
            if n == num:
                res += hashMap[n]
                break
            elif n > num:
                count = n / num
                res += hashMap[num] * count
                n %= num

        return res


if __name__ == "__main__":
    sol = Solution()

    # n = 5

    # n = 6

    # n = 3049

    n = 3999

    res = sol.ArabicToRoman(n)

    print res