LeetCode #13 Roman to Integer 解題思路及翻譯

LeetCode題目翻譯

英文原文如下

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

LeetCode #13 Symbol Value Picture

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 a roman numeral, convert it to an integer.

中文翻譯

羅馬的計數系統是由七個不同的符號來代表(參考上面的圖)

以例子二來說,2在羅馬數字中被寫作II,也就是兩個1加在一起。12被寫成 XII,就是 X + II。27被寫作XXVII,也就是 XX + V + II

羅馬數字通常來說數字大到小是被從左寫到右,然而數字4卻不是IIII,作為替代

4被寫作 IV,因為V前面的I被視為減去來構成4。同樣的原則也發生在數字9上,被寫作IX

這裡列出六個會被視為減去的實例這裡會是重點

  • I 可以被列在 V (5) 跟 X (10) 前,來構成 4 跟 9
  • X 可以被列在 L (50) and C (100) 前,來構成 40 跟 90
  • C 可以被列在 D (500) and M (1000) 前,來構成 400 跟 900.

給予一個羅馬數字,將其轉換為整數

LeetCode #13 題目限制

給予羅馬數字 s 的長度介於1跟15之間

s只有包含這些符號 ( ‘I‘ , ‘V‘ , ‘X‘ , ‘L‘ , ‘C‘ , ‘D‘ , ‘M‘ )

保證s是一個合乎規則且介於 [1,3999]之間的羅馬數字 (註1 : [a,b]為數學中的閉區間,意思為包含 ➔ 1<= int <= 3999 )

以下是官方提供的三個範例

LeetCode #13 官方範例

範例的話我們就只看第三個吧

前兩個範例比較簡單,沒有用到特殊規則(減去的方式)

第一個字 M ,查表得到 1000

第二個字 C ,查表得到 100

第三個字 M ,查表得到 1000 ➔ 觸發規則 C在M之前,為 1000 – 100 = 900

第四個字 X ,查表得到 10

第五個字 C ,查表得到 100 ➔ 觸發規則 X在C之前,為 100 – 10 = 90

第六個字 I ,查表得到 1

第七個字 V ,查表得到 5 ➔ 觸發規則 I 在V之前,為 5 – 1 = 4

加總可得到 : 1000+900+90+4 = 1994

這個例子其實非常刻意的用到了很多 4 跟 9 ,就是羅馬數字規則的特例(數字不是從大到小排序)


解題思路

先看一下上面的圖1,符號跟數字有一個對應表吧,所以這邊就用dict來儲存(符號為 Key,數字為Value )

本來也有想過用 If-Else的,但實在要寫太多條件的感覺

我們先看回題目,上面中文翻譯也有標示出重點,就是4跟9的特殊規則

那現在讓我們來試試看吧 (文章會以C#作為範例說明,其他語言不一定會特別解釋)

C# 解決方案

方案1 – 使用字典來儲存符號對應的值

public class Solution {
    private readonly Dictionary<char, int> dict = new Dictionary<char, int>{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
    
    public int RomanToInt(string s) {
   
        char[] ch = s.ToCharArray();
    
        int result = 0;
        int intVal,nextIntVal;
            
        for(int i = 0; i <ch.Length ; i++){
            intVal = dict[ch[i]];
            
            if(i != ch.Length-1)
            {
                nextIntVal = dict[ch[i+1]];
                
                if(nextIntVal>intVal){          //正常不會出現右邊大於左邊的情況,要是發生就是4或9的狀況
                    intVal = nextIntVal-intVal;  //計算上就將右邊減去左邊即可
                    i = i+1;                     //因右邊也納入計算了,故i直接+1 ,下次跳過他執行
                }
            }
             result = result + intVal;
        }
        return result;
    }
}

可以看到程式碼其實並不算複雜,主要有以下幾點

  • dict 的 Key值設為char ➔ 針對string 的最小單位char來做,避免還需要再轉型的成本
  • dict 設為 readonly ➔ 因為符號跟數字的對應是不會變的,故設為唯獨減少記憶體損耗
  • 最後一點就是針對 4 跟 9 去做這個狀況
    • 正常不會出現右邊大於左邊的情況,又因題目有說到會提供合乎規則的羅馬數字
    • 不然要是傳入IM 我們也會判斷成 1000 – 1 = 999,但其實是不符規則的,若要表示999 應該要為 「CMXCIX」

方案2 – 針對特例進行替換

public class Solution {
    private readonly Dictionary<char, int> dict = new Dictionary<char, int>{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
    
    public int RomanToInt(string s) {
        
        //special situations
        s = s.Replace("IV","IIII");
        s = s.Replace("IX","VIIII");
        s = s.Replace("XL","XXXX");
        s = s.Replace("XC","LXXXX");
        s = s.Replace("CD","CCCC");
        s = s.Replace("CM","DCCCC");
        
        int result = 0;
        
        foreach(var ch in s)
        {
            result += dict[ch];
        }
        
        return result;
    }
}

第二個解決方案就很暴力了,題目中不是有提到共有6種特例嗎?

那我們直接把他們用另一種寫法 取代,就可以用很簡單的加法來計算了

Ex : 4 應該要顯示為 5-1 = IV,我們直接用1+1+1+1 = IIII 來取代,以此類推 (當然這在羅馬數字中不是正規的表示方式!)

JAVA 解決方案

方案1 – Map 可以達成C# 字典的效果

class Solution {
    public int romanToInt(String s) {
        Map<Character, Integer> map = new HashMap<Character, Integer>() {{
        
            put('I',1);
            put('V',5);
            put('X',10);
            put('L',50);
            put('C',100);
            put('D',500);
            put('M',1000);
            
        }};
        
        char[] arr = s.toCharArray();
        
        int result = 0;
        int intVal,nextIntVal;
            
        for(int i = 0; i <arr.length ; i++){
            intVal = map.get(arr[i]);
            
            if(i != arr.length-1)
            {
                nextIntVal = map.get(arr[i+1]);
                
                if(nextIntVal>intVal){
                    intVal = nextIntVal-intVal;
                    i = i+1;
                }
            }
             result = result + intVal;
        }
        return result;
    }
}

方案2

class Solution {
    public int romanToInt(String s) {
        Map<Character, Integer> map = new HashMap<Character, Integer>() {{
        
            put('I',1);
            put('V',5);
            put('X',10);
            put('L',50);
            put('C',100);
            put('D',500);
            put('M',1000);
            
        }};
        
        //special situations  
        s = s.replace("IV","IIII");
        s = s.replace("IX","VIIII");
        s = s.replace("XL","XXXX");
        s = s.replace("XC","LXXXX");
        s = s.replace("CD","CCCC");
        s = s.replace("CM","DCCCC");
        
        
        int result = 0;
        for (char ch: s.toCharArray()) {
            result+= map.get(ch);
        }
        
        return result;
    }
}

Python3 解決方案

方案1

class Solution:
    def romanToInt(self, s: str) -> int:
       dict = {
        'I' : 1,
        'V' : 5,
        'X' : 10,
        'L' : 50,
        'C' : 100,
        'D' : 500,
        'M' : 1000
        } 
       result  = 0
       tmp = 0;
       i = 0

       while i < len(s):
           tmp = dict[s[i]];
           if (i +1) < len(s) and dict[s[i]] < dict[s[i + 1]]:
               tmp = dict[s[i + 1]] - dict[s[i]]
               i += 1
           i += 1
           result += tmp;

       return (result)

方案2

class Solution:
    def romanToInt(self, s: str) -> int:
       dict = {
        'I' : 1,
        'V' : 5,
        'X' : 10,
        'L' : 50,
        'C' : 100,
        'D' : 500,
        'M' : 1000
        } 
       s = s.replace("IV","IIII").replace("IX","VIIII");
       s = s.replace("XL","XXXX").replace("XC","LXXXX");
       s = s.replace("CD","CCCC").replace("CM","DCCCC");
      
       result = 0;
       for i in range(len(s)):
           result += dict[s[i]];          


       return (result)

JavaScript 解決方案

方案1

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    var dict = {
      'I':1,
      'V':5,
      'X':10,
      'L':50,
      'C':100,
      'D':500,
      'M':1000
    };
    
    var result = 0;
    var intVal = 0;
    var nextIntVal = 0;
    for (var i = 0; i < s.length; i++) {
        intVal = dict[s[i]];
        
        if(i!=s.length-1)
        {
            nextIntVal = dict[s[i+1]];
            if(nextIntVal>intVal){
                intVal = nextIntVal-intVal;
                i = i+1;
            }
        }
        result = result + intVal;
    }
    return result;
};

方案2

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    var dict = {
      'I':1,
      'V':5,
      'X':10,
      'L':50,
      'C':100,
      'D':500,
      'M':1000
    };
    
    s = s.replace("IV","IIII").replace("IX","VIIII");
    s = s.replace("XL","XXXX").replace("XC","LXXXX");
    s = s.replace("CD","CCCC").replace("CM","DCCCC");
    
    var result = 0;

    for (var i = 0; i < s.length; i++) {
        result+=dict[s[i]];
    }
    return result;
};

結論

相當經典的一題,考得完全是邏輯的處理,筆者第一次寫LeetCode就是這題

那時確實花了不少時間,最後跑出的成品勉強得到結果,但真的跑得有夠慢…

在寫這篇文章的時候,又回頭重新優化了一次程式語法

來分享個古羅馬 凱薩大帝的名言

"I came, I saw, I conquered."
                                                                                                                 Julius Caesar                            

希望各位在刷LeetCode的時候也能如此霸氣!

最新文章

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *