[LeetCode] 13. Roman to Integer 解題思路 (Easy)

這題需要把數字轉成羅馬數字，本來以為會很難，後來想通了之後發現還好。

LeetCode 題目連結

 

https://leetcode.com/problems/roman-to-integer/

 

題目

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, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven 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. Input is guaranteed to be within the range from 1 to 3999.

Accept 作法

這題利用 HashMap 去紀錄數字對上羅馬數字，時間複雜度O(n)，空間複雜度O(n)。


Runtime: 14 ms
Memory: 45.4 MB

Java 程式碼

class Solution {
    public int romanToInt(String s) {
        HashMap<String,Integer> romanIntMap = new HashMap<String,Integer>();
        romanIntMap.put("I",1);
        romanIntMap.put("V",5);
        romanIntMap.put("X",10);
        romanIntMap.put("L",50);
        romanIntMap.put("C",100);
        romanIntMap.put("D",500);
        romanIntMap.put("M",1000);
        
        int sum = 0;
        String lastKey = "";
        
        for(int i = 0;i<s.length();i++){
            String key = String.valueOf(s.charAt(i));
            if(romanIntMap.containsKey(key)){
                int count = (int) romanIntMap.get(key);
                
                if(lastKey.equals("I") && (key.equals("V") || key.equals("X"))){
                    sum = sum -2;
                }else if(lastKey.equals("X") && (key.equals("L") || key.equals("C"))){
                    sum = sum -20;
                }else if(lastKey.equals("C") && (key.equals("D") || key.equals("M"))){
                    sum = sum -200;
                }
                sum = sum + count;
                
                lastKey = key;
            }
        }
        return sum;
    }
}

 

更多 LeetCode 相關資源

• Udemy 暢銷 - Master the Coding Interview: Data Structures + Algorithms

 

複習程式面試書籍

除了 LeetCode 練習外，我也入手了這本，題庫來自真正的面試，並非摘自教科書。它們反映出頂尖公司真正會出的題目，你可以藉此做好充分準備。
需要的話可以看看，寫得很仔細。

書名：提升程式設計師的面試力：189道面試題目與解答

• 金石堂實體書資訊
• Hyread 電子書資訊

相關 LeetCode文章一律會放在 程式解題 標籤分類，歡迎持續追蹤。

⇒ 點我看更多程式解題