12. 整数转罗马数字

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

• I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
• X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
• C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。

示例 4:
输入: 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.

示例 5:
输入: 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

解法一

没看答案之前的做法，暴力求解法。
主要思路：从个位开始，遍历出每一位，然后根据各种情况再表示出来，并拼接到返回的字符串上。

    # ['I', 'V', 'X', 'L', 'C', 'D', 'M']
    # [1,    5,   10,  50,  100, 500, 1000]

    def handleNum(cur, ns):
        if cur < 4:
            ns = 'I' * cur + ns
        elif cur == 4:
            ns = 'IV' + ns
        elif cur == 5:
            ns = 'V' + ns
        elif cur < 9:
            ns = 'V' + 'I' * (cur - 5) + ns
        elif cur == 9:
            ns = 'IX' + ns
        elif cur < 40:
            ns = 'X' * (cur // 10) + ns
        elif cur == 40:
            ns = 'XL' + ns
        elif cur == 50:
            ns = 'L' + ns
        elif cur < 90:
            ns = 'L' + 'X' * (cur // 10 - 5) + ns
        elif cur == 90:
            ns = 'XC' + ns
        elif cur < 400:
            ns = 'C' * (cur // 100) + ns
        elif cur == 400:
            ns = 'CD' + ns
        elif cur == 500:
            ns = 'D' + ns
        elif cur < 900:
            ns = 'D' + 'C' * (cur // 100 - 5) + ns
        elif cur == 900:
            ns = 'CM' + ns
        elif cur < 4000:
            ns = 'M' * (cur // 1000) + ns

        return ns

    # 先从个位开始，表示每一位，再拼接起来
    ns, div = "", 10
    
    while True:
        # 这一位的数
        cur = num % div
        ns = handleNum(cur, ns)
        # 将这位去掉过后的整数
        num = num // div * div
        div *= 10

        # 最后一位，计算出来就结束了
        if num // div == 0:
            cur = num
            ns = handleNum(cur, ns)
            break

    return ns

解法二

参考力扣官方答案，采用贪心算法，贪心算法是一种在当前时间做出最佳可能决策的算法。这里既是取出最大可能的符合。
主要思想：为了表示一个给定的整数，我们寻找适合它的最大符号。我们减去它，然后寻找适合余数的最大符号，依此类推，直到余数为0。我们取出的每个符号都附加到输出的罗马数字字符串上。

def intToRoman2(num):

    digits = [(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")]
    # 记录罗马数字符号
    roman_digits = []
    # 从最大到最小循环遍历每个符号，检查当前符号的有多少个副本适合剩余的整数
    for value, symbol in digits:
        # 当数字取完了过后就结束遍历
        if num == 0: break
        # Return the tuple (x//y, x%y)
        count, num = divmod(num, value)
        # 将这位表示的罗马数字符号添加到数组里面
        roman_digits.append(symbol * count)
    # 返回拼接起来的字符串
    return "".join(roman_digits)

复杂度分析

• 时间复杂度：O(1)。由于有一组有限的罗马数字，循环可以迭代多少次有一个硬上限。因此，我们说时间复杂度是常数的，即 O(1)。
• 空间复杂度：O(1)，使用的内存量不会随输入整数的大小而改变，因此是常数的。

解法三

参考力扣官方答案，将每一位都表示出来，然后再逐位进行计算和我的解法一有点相像。

主要思想：在代码中实现它最简单的方法是使用 4 个独立的数组；每个位置值对应一个数组。然后，在输入数字中提取每个位置的数字，在相关数组中查找它们的符号，并将它们全部附加在一起。

def intToRoman3(num):
    thousands = ["", "M", "MM", "MMM"]
    hundreds = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"]
    tens = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"]
    ones = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]
    return thousands[num // 1000] + hundreds[num % 1000 // 100] + tens[num % 100 // 10] + ones[num % 10]

复杂度分析

• 时间复杂度：O(1)。无论输入的大小，都会执行相同数量的操作。因此，时间复杂度是常数的。
• 空间复杂度：O(1)，虽然我们使用数组，但不管输入的大小，它们都是相同的大小。因此，它们是常数级空间。

力扣官方答案