Skip to content

LeetCode: 12-Integer to Roman 解題紀錄

Last Updated on 2021-01-10 by Clay

題目

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

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

For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

-  I can be placed before V (5) and X (10) to make 4 and 9. 
-  X can be placed before L (50) and C (100) to make 40 and 90. 
-  C can be placed before D (500) and M (1000) to make 400 and    900.

Given an integer, convert it to a roman numeral.

Example:

Input: num = 3
Output: "III"

Input: num = 58
Output: "LVIII"

Input: num = 1994
Output: "MCMXCIV"

題目給定一整數值，而我們要做的便是將整數值轉換成羅馬數字 —— 也就是說，我們需要回傳字串型態的答案。

解題思路

我這輩子第一次了解什麼是『羅馬數字』，得從 Final Fantasy X 開始說起。（台灣早年翻太空戰士、中國直譯為最終幻想，也就是俗稱的 FF，日本三大國民 RPG 之一！）

那時候我斷斷續續玩了 FFVII、FFVIII，那時候還不知道什麼是羅馬數字，還以為 FF 後面的符號是遊戲開發組瞎掰的 XDDD

雖然不明所以，但是看起來真的很帥啊！然後當我從親戚那邊聽聞了 FF 最新一代準備要發售時，我還興奮地在學校跟朋友吹噓說：

FF VIIIII 要發售啦！（後面那串到底是什麼鬼）

直到我看到了店家貼出來的海報時，我才徹底傻眼了：咦？很炫炮的 VIIIII 到哪去了？為什麼只用一個 X 就寫完了！！！？？？？

我這才發現，我可能壓根兒搞錯了 FF 這款遊戲後面的命名方式。一查之下，才發現，哦～原來這玩意兒是所謂的羅馬數字，跟我們一般來所使用的阿拉伯數字基本是一樣的，是用來表示數字大小的某種『符號』。

ㄜ，話題扯遠啦。簡單來講，羅馬數字有著屬於自己的規律，以下是我自己的理解，從 1 - 10 簡單列出看看：

  • 1: 使用 I 代表（基本符號 I）
  • 2: 使用 II 代表（I + I = II）
  • 3: 使用 III 代表（I + I + I = III）
  • 4: 使用 IV 代表 （V - I = IV，V 則是 5 的符號）
  • 5: 使用 V 代表 （V 是 5 的符號）
  • 6: 使用 VI 代表（V + I = VI）
  • 7: 使用 VII 代表（V + I + I = VII）
  • 8: 使用 VIII 代表（V + I + I + I = VIII）
  • 9: 使用 IX 代表（X - I = IX，X 是 10 的符號）
  • 10: 使用 X 代表（X 是 10 的符號）

可以發現以下這樣的規律：

  • 1 ~ 3 都是 I 符號的累加
  • 4 ~ 8 則是 V 符號的加減
  • 9 ~ 10 則是 X 的符號為主

而這個規律不僅是出現在 1 ~ 10，從 10 ~ 100、100 ~ 1000 基本上也都會遵循這樣的規律，只是符號不同的罷了（比方說 400 就是 CD，可以理解為 500 - 100）。

而按照這個規律，我們便可以把代表特定數字的符號先建立表，從大到小去比較題目輸入的整數值。只要輸入的整數值大於最大的特定數字，則將整數值減去最大的特定數字、然後繼續比較次大的特定數字 ...... 一直重複操作到輸入值歸零。

這個方法用說明的看起來比較繁瑣，以下直接看程式即可：


C++ 程式

class Solution {
public:
    string intToRoman(int num) {
        // Init
        vector<string> symbol({"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"});
        vector<int> nums({1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1});
        string result;
        
        // Loop to combine the answer
        for (int i=0; i<nums.size(); i++) {
            if (num >= nums[i]) {
                for (int n=0; n<(num/nums[i]); n++) {
                    result += symbol[i];
                }
                num = num % nums[i];
            }
        }
        
        return result;
    }
};


Python3 程式碼

class Solution:
    def intToRoman(self, num: int) -> str:
        # Init
        symbol = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
        nums = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
        result = ''
        
        # Loop
        for i in range(len(nums)):
            if (num >= nums[i]):
                result += symbol[i] * (num // nums[i])
                num %= nums[i]
        
        return result;


順帶一提我一開始所想像的方法很單純但是卻也挺快的 XDDD

那就是把所有符號列出來，反正才沒幾項 XDDD

References

Tags:

Leave a Reply