[LeetCode] 13. Roman to Integer 羅馬數(shù)字轉(zhuǎn)化成整數(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ù)轉(zhuǎn)化成數(shù)字問題，我們需要對(duì)于羅馬數(shù)字很熟悉才能完成轉(zhuǎn)換。以下截自百度百科：

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ù)字，先加上當(dāng)前的數(shù)字，比如 "VI"，第二個(gè)字母 'I' 小于第一個(gè)字母 'V'，所以要加1。如果大于的前面的數(shù)字，加上當(dāng)前的數(shù)字減去二倍前面的數(shù)字，這樣可以把在上一個(gè)循環(huán)多加數(shù)減掉，比如 "IX"，我們?cè)?i=0 時(shí)，加上了第一個(gè)字母 'I' 的值，此時(shí)結(jié)果 res 為1。當(dāng) i=1 時(shí)，字母 'X' 大于前一個(gè)字母 'I'，這說明前面的1是要減去的，而由于前一步不但沒減，還多加了個(gè)1，所以此時(shí)要減去2倍的1，就是減2，所以才能得到9，整個(gè)過程是 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;
    }
};

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

最新評(píng)論