[LeetCode] Integer to Roman

题意

将一个十进制数字转换成罗马数字。

限制：1<=x<=3999

题解

首先 维基 一下什么是罗马数字：

罗马数字共有 7 个，即 Ⅰ（1）、Ⅴ（5）、Ⅹ（10）、Ⅼ（50）、Ⅽ（100）、Ⅾ（500）和 Ⅿ（1000）。

需要注意的是罗马数字中没有 “0”，与进位制无关。

一般认为罗马数字只用来记数，而不作演算。

总结一下不超过 3999 的罗马计数的特点：

1. 两个大原则：右加、重复次数即相乘倍数（例：VI=V+I=6，VVV=V*3=25）。
2. 每个字母连续重复不超过 3 次。
3. 如果 “需要出现四次”，那么使用 “左减”：只能减去 I、X、C，且尽量减去最大的（例如：4 应该为 IV，9 应该为 IX，40 应该为 XL）。

我们发现，只有 “左减” 比较不好玩。但是我们不难发现，只有带 4 和带 9 的需要使用 “左减”：在个位范围是 4 和 9，在十位范围内是 40 和 90，在百位范围内是 400 和 900。其余的只需要 “右加” 就好了。

那么我们就可以投机取巧一下了：我们可以提前把这几个 4 和 9 写出来。这样就变成了纯纯的加减问题了。

代码

class Solution(object):
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        n_10 = [1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000]
        n_ro = ['I', 'IV', 'V', 'IX', 'X', 'XL', 'L', 'XC', 'C', 'CD', 'D', 'CM', 'M']
        ans = ''
        i = len(n_10) - 1
        while num > 0 and i >= 0:
            if num >= n_10[i]:
                ans += (n_ro[i] * (num // n_10[i]))
                num -= (n_10[i] * (num // n_10[i]))
            i -= 1
        return ans

你要问了，为什么不把 num // n_10[i] 提出来放进去一个变量里面呢？我也可奇怪，提取出来之后用时反而比这样写耗时要长。

结果

3999 / 3999 test cases passed. （So，您的测试数据就是从 1 到 3999？！Excuse Me？覆盖度超级高啊！）
Status: Accepted
Runtime: 132 ms

桩程序

if __name__ == '__main__':
    cases = [
        {'num': 1, 'ans': 'I'},
        {'num': 8, 'ans': 'VIII'},
        {'num': 14, 'ans': 'XIV'},
        {'num': 15, 'ans': 'XV'},
        {'num': 16, 'ans': 'XVI'},
        {'num': 199, 'ans': 'CXCIX'},
        {'num': 3978, 'ans': 'MMMCMLXXVIII'},
    ]
    for item in cases:
        ans = (Solution()).intToRoman(num=item['num'])
        print(str(ans == item['ans']) + "\t=>" + str(ans) + ":" + str(item['ans']))