[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']))

留下评论