LeetCode 13. Roman to Integer [Easy] [C++] 解題筆記

    這題題目太冗了，可以直接參考 LeetCode 13. Roman to Integer。簡而言之就是給我們一個羅馬數字表示的字串，要我們轉換成對應的整數值。

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

EX:

Input: "III"
Output: 3

Input: "IV"
Output: 4

Input: "IX"
Output: 9

Input: "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

想法:

        這題主要就是要知道羅馬數字的具體規則:

        1.    相同的數字連寫，所表示的數等於這些數字相加得到的數，如：Ⅲ = 3；
        2.    小的數字在大的數字的右邊，所表示的數等於這些數字相加得到的數， 如：Ⅷ = 8；Ⅻ = 12；
        3.    小的數字，（限於Ⅰ、X 和C）在大的數字的左邊，所表示的數等於大數減小數得到的數，如：Ⅳ= 4；Ⅸ= 9；
        4.    正常使用時，連寫的數字重複不得超過三次。 （錶盤上的四點鐘“IIII”例外）
        5.    在一個數的上面畫一條橫線，表示這個數擴大1000倍。

        另外下列規則也需要注意
        1.    基本數字Ⅰ、X 、C 中的任何一個，自身連用構成數目，或者放在大數的右邊連用構成數目，都不能超過三個；放在大數的左邊只能用一個。
        2.    不能把基本數字V 、L 、D 中的任何一個作為小數放在大數的左邊採用相減的方法構成數目；放在大數的右邊採用相加的方式構成數目，只能使用一個。
        3.    V 和X 左邊的小數字只能用Ⅰ。
        4.    L 和C 左邊的小數字只能用X。
        5.    D 和M 左邊的小數字只能用C。

而這題沒有讓我們來驗證輸入字符串是不是羅馬數字，這樣就簡單許多，可以使用 HashMap 來建立羅馬數字與整數之間的mapping，因為輸入的一定是羅馬數字，那麼只需要考慮：
        1.   如果當前數字是最後一個數字，或者之後的數字比它小的話，則加上當前數字。
        2.   其他情況則減去這個數字。

完整程式碼:

class Solution {

public:

    int romanToInt(string s) {

        int res = 0;

        unordered_map<char, int> m{{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}};

        

        for (int i = 0; i < s.size(); i++) {

            int val = m[s[i]];

            if (i == s.size() - 1 || m[s[i+1]] <= m[s[i]]) {

                res += val;

            }

            else {

                res -= val;

            }

        }

        

        return res;

    }

};