[LeetCode] 13. Roman to Integer 羅馬數(shù)字轉化成整數(shù)

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.

Example 1:

Input: "III"
Output: 3

Example 2:

Input: "IV"
Output: 4

Example 3:

Input: "IX"
Output: 9

Example 4:

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

Example 5:

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

羅馬數(shù)轉化成數(shù)字問題，我們需要對于羅馬數(shù)字很熟悉才能完成轉換。以下截自百度百科：

I - 1

V - 5

X - 10

L - 50

C - 100 

D - 500

M - 1000

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;
    }
};

我們也可以每次跟前面的數(shù)字比較，如果小于等于前面的數(shù)字，先加上當前的數(shù)字，比如 "VI"，第二個字母 'I' 小于第一個字母 'V'，所以要加1。如果大于的前面的數(shù)字，加上當前的數(shù)字減去二倍前面的數(shù)字，這樣可以把在上一個循環(huán)多加數(shù)減掉，比如 "IX"，我們在 i=0 時，加上了第一個字母 'I' 的值，此時結果 res 為1。當 i=1 時，字母 'X' 大于前一個字母 'I'，這說明前面的1是要減去的，而由于前一步不但沒減，還多加了個1，所以此時要減去2倍的1，就是減2，所以才能得到9，整個過程是 res = 1 + 10 - 2 = 9，參見代碼如下:

解法二：

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) {
            if (i == 0 || m[s[i]] <= m[s[i - 1]]) res += m[s[i]];
            else res += m[s[i]] - 2 * m[s[i - 1]];
        }
        return res;
    }
};

到此這篇關于C++實現(xiàn)LeetCode(13.羅馬數(shù)字轉化成整數(shù))的文章就介紹到這了,更多相關C++實現(xiàn)羅馬數(shù)字轉化成整數(shù)內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論