題目鏈接
tag:
- easy
question：
??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:
"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ù)字問(wèn)題应役，我們需要對(duì)于羅馬數(shù)字很熟悉才能完成轉(zhuǎn)換附鸽。以下截自百度百科：
羅馬數(shù)字是最早的數(shù)字表示方式聪黎，比阿拉伯?dāng)?shù)字早2000多年，起源于羅馬。
如今我們最常見(jiàn)的羅馬數(shù)字就是鐘表的表盤(pán)符號(hào)：Ⅰ，Ⅱ，Ⅲ井联，Ⅳ（IIII），Ⅴ您旁，Ⅵ烙常，Ⅶ，Ⅷ，Ⅸ蚕脏，Ⅹ侦副，Ⅺ，Ⅻ……
對(duì)應(yīng)阿拉伯?dāng)?shù)字（就是現(xiàn)在國(guó)際通用的數(shù)字）驼鞭，就是1秦驯，2，3挣棕，4译隘，5，6洛心，7固耘，8，9词身，10玻驻，11，12偿枕。（注：阿拉伯?dāng)?shù)字其實(shí)是古代印度人發(fā)明的，后來(lái)由阿拉伯人傳入歐洲户辫，被歐洲人誤稱為阿拉伯?dāng)?shù)字渐夸。）
- 相同的數(shù)字連寫(xiě)，所表示的數(shù)等于這些數(shù)字相加得到的數(shù)渔欢，如：Ⅲ = 3墓塌；
- 小的數(shù)字在大的數(shù)字的右邊，所表示的數(shù)等于這些數(shù)字相加得到的數(shù)奥额， 如：Ⅷ = 8苫幢；Ⅻ = 12；
- 小的數(shù)字垫挨，（限于Ⅰ韩肝、X 和C）在大的數(shù)字的左邊，所表示的數(shù)等于大數(shù)減小數(shù)得到的數(shù)九榔，如：Ⅳ= 4哀峻；Ⅸ= 9；
- 正常使用時(shí)哲泊，連寫(xiě)的數(shù)字重復(fù)不得超過(guò)三次剩蟀。（表盤(pán)上的四點(diǎn)鐘“IIII”例外）
- 在一個(gè)數(shù)的上面畫(huà)一條橫線，表示這個(gè)數(shù)擴(kuò)大1000倍切威。
有幾條須注意掌握：
- 基本數(shù)字Ⅰ育特、X 、C 中的任何一個(gè)先朦，自身連用構(gòu)成數(shù)目缰冤，或者放在大數(shù)的右邊連用構(gòu)成數(shù)目犬缨，都不能超過(guò)三個(gè)；放在大數(shù)的左邊只能用一個(gè)锋谐。
- 不能把基本數(shù)字V 遍尺、L 、D 中的任何一個(gè)作為小數(shù)放在大數(shù)的左邊采用相減的方法構(gòu)成數(shù)目涮拗；放在大數(shù)的右邊采用相加的方式構(gòu)成數(shù)目乾戏，只能使用一個(gè)。
- V 和X 左邊的小數(shù)字只能用Ⅰ三热。
- L 和C 左邊的小數(shù)字只能用X鼓择。
- D 和M 左邊的小數(shù)字只能用C。
??而這道題好就好在沒(méi)有讓我們來(lái)驗(yàn)證輸入字符串是不是羅馬數(shù)字就漾，這樣省掉不少功夫呐能。我們需要用到HashMap數(shù)據(jù)結(jié)構(gòu)，來(lái)將羅馬數(shù)字的字母轉(zhuǎn)化為對(duì)應(yīng)的整數(shù)值抑堡，因?yàn)檩斎氲囊欢ㄊ橇_馬數(shù)字摆出，那么我們只要考慮兩種情況即可：
- 如果當(dāng)前數(shù)字是最后一個(gè)數(shù)字，或者之后的數(shù)字比它小的話首妖，則加上當(dāng)前數(shù)字偎漫。
- 其他情況則減去這個(gè)數(shù)字。
??我們也可以每次跟前面的數(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í)魄幕，我們發(fā)現(xiàn)字母 'X' 大于前一個(gè)字母 'I'，這說(shuō)明前面的1是要減去的颖杏，而由于我們前一步不但沒(méi)減纯陨，還多加了個(gè)1，所以此時(shí)要減去2倍的1，就是減2翼抠，所以才能得到9咙轩，整個(gè)過(guò)程是 res = 1 + 10 - 2 = 9，參見(jiàn)代碼如下:
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;
}
};
