[leetcode algorithms]題目12

12. Integer to Roman

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

自己寫的代碼：

初始化類的時候創建字典和列表，用於存儲數字和羅馬字母的對應關係。4000作為「哨兵」防止數組溢出。（因為題目限定了1-3999）。定義二分查找函數來查找數字所在的範圍，減去這個數字直至演算法收斂。運行時間317 ms

class Solution: def __init__(self): self.dic = {1: I, 10: X, 100: C, 1000: M , 5: V, 50: L, 500: D , 4: IV, 40: XL, 400: CD , 9: IX, 90: XC, 900: CM} self.nums = [1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000, 4000] def binSearch(self, num): left = 0 right = len(self.nums) - 2 while left <= right: mid = (left + right) // 2 if num < self.nums[mid]: right = mid - 1 elif num >= self.nums[mid + 1]: left = mid + 1 else: break return self.nums[mid] def intToRoman(self, num): res = while num != 0: v = self.binSearch(num) num -= v res += self.dic[v] return res

討論區的優秀代碼：

哈哈，五體投地~

class Solution: def intToRoman2(self, num): M = ["", "M", "MM", "MMM"] C = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"] X = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"] I = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"] return M[num / 1000] + C[(num % 1000) / 100] + X[(num % 100) / 10] + I[num % 10]

推薦閱讀：