罗马数字包含以下七种字符： 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)，虽然我们使用数组，但不管输入的大小，它们都是相同的大小。因此，它们是常数级空间。
