罗马文转换
将数字转换为罗马文
罗马文有数字表示"I V X L C D M", 分别代表数字 1 5 10 50 100 500 1000.
而罗马文一般以右侧累加的形式表示数字集, 例如：
III 表示 3, VII 表示7 MM表示2000等.
但是同时又有一些例外, 这些例外是在以上数列表示左侧累加, 例如：
IV 表示 4
IX 表示 9
XL 表示 40
XC 表示 90
CD 表示 400
CM 表示 900
如何正确有将数字转换为罗马文呢？
算法1：
# 贪心算法, 暴力破解
def num_to_rome(num):
rome_map = [(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")]
result = []
for n, r in rome_map:
if num == 0:
return ""
count, num = divmod(num, n)
result.append(r * count)
return "".join(result)
print("1939") # MCMXXXIX
print("5999") # MMMMMCMXCIX
解题过程：
该过程将罗马文的元字符表示出来, 同时又将6种左侧累加字符表示出来. 将数值从大到小排列.
每次使用除数与余数的形式, 先从当前最大的数开始. 将当前应表示的个数与要对应的字符累叠在一起, 表示当前罗马数值.
余数参与下一次运算, 重复步骤二, 直到数字终结.
最后返回罗马文.
时间复杂度 O(N)
大神算法：
算法的不同, 虽然在结果上一致, 但在效率与思想上却体现了非常大的差别.
def int_to_rome(num: int) -> str:
ref_str = "IVXLCDM"
res = ""
count = 0
while num != 0:
bit = num % 10
# 不用考虑0，因为会*0没有效果
if bit < 4:
res = ref_str[2 * count] * bit + res
elif bit == 4:
res = ref_str[2 * count:2 * count + 2] + res
elif 4 < bit < 9:
res = ref_str[2 * count + 1] + ref_str[2 * count] * (bit - 5) + res
else:
res = ref_str[2 * count] + ref_str[2 * count + 2] + res
num = num // 10
count += 1
return res
该代码考虑4种情况.
数值小于4, 该值为当前罗马文累加. 例如： III XXX等
数值等于4, 该值为中间数左侧累加表示. 例如： IV XL等
数值大于4但小于9, 该值为中间数右侧累加. 例如： VIII LXX等
数值等于9, 该值表示最大值左侧累加. 例如： IX CM等
算法过程重要思路如下：
"IVXLCDM" 但顺序排位. count 表示当前计算所在位数, 例个位, 十位, 百位, 千位.
将要计算数值 % 10, 算出当前个位（不一定是数字的个位）
找到数值所处的4种情况之一. 根据计算出数值对应的字符.
将数字 // 10, 去掉当前个位（不一定是数字的个位）, count + 1, 表示当前的数字位数.
重复2 - 4步骤.
以上大神算法摘自leetcode算法速度最快解.
