12. Integer to Roman

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

Input: num = 3
Output: "III"
Explanation: 3 is represented as 3 ones.

Input: num = 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.

Input: num = 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

字典遍历解法

class Solution:def intToRoman(self, num: int) -> str:# 定义字典，映射罗马字符和对应的值dic = {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'}# 初始化结果列表res = []# 遍历字典中的每个值-符号对for value, symbol in dic.items():# 如果num为0，跳出循环if num == 0:break# 用当前的value去除num，并获取商和余数# 商表示当前value可以完全覆盖num的次数，余数表示剩余的部分count, num = divmod(num, value)# 将当前的符号重复count次，并添加到结果列表res.append(symbol * count)# 将结果列表中的字符串连接起来，返回return ''.join(res)

复杂度分析如下：

时间复杂度：我们只需要遍历一次罗马数字的符号字典，其中包含13个元素。所以时间复杂度是 O(1)。尽管我们在每次迭代中都会执行乘法和字符串连接操作，这两种操作的复杂度都是 O(k)，其中 k 是需要重复的次数。但是总体上看，k 的最大值并不大（最大为 3，对应于 “III”、“XXX”、“CCC”、“MMM”），所以可以认为时间复杂度是常量的。

空间复杂度：我们使用了一个固定大小的字典和一个结果列表。结果列表的长度最多为15（考虑到数字1994，对应的罗马数字为 “MCMXCIV”，长度为7），所以空间复杂度也是 O(1)。

Python中的 join() 方法

Python中的 join() 方法是一个字符串方法，它用于将序列中的元素以特定的字符连接生成一个新的字符串。

在代码 ‘’.join(res) 中，join() 方法用于连接序列 res 中的元素，其中的 ‘’（空字符串）表示连接的字符。也就是说，这个方法将 res 列表中的所有元素连接起来，元素之间没有任何字符。

假设我们有以下的列表：

res = ['M', 'CM', 'XC', 'IV']

如果我们执行 ‘’.join(res)，我们会得到：

'MCMXCIV'

join() 方法是一个非常有用的工具，特别是当我们需要将一个字符串列表组合成一个单一的字符串时。它比使用 + 操作符进行字符串连接更有效率，尤其是在处理大型字符串列表时。

divmod() 是一个内置的 Python 函数

divmod() 是一个内置的 Python 函数，用于一次性执行除法和取余操作。它接受两个参数：被除数和除数，然后返回一个元组，其中第一个元素是商，第二个元素是余数。

这是一个简单的例子：

quotient, remainder = divmod(10, 3)
print("Quotient: ", quotient)  # 输出：Quotient: 3
print("Remainder: ", remainder)  # 输出：Remainder: 1

在这个例子中，我们使用 divmod() 函数将 10 除以 3，得到的商是 3，余数是 1。divmod() 函数返回了一个元组 (3, 1)，我们通过元组解包，将商和余数分别赋值给 quotient 和 remainder。

使用 divmod() 函数比分别使用除法和模运算符更有效率，因为它只进行一次除法操作。如果你在写的代码中需要同时得到商和余数，那么使用 divmod() 函数是一个很好的选择。