LeetCode13 Roman to Integer

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

样例

1
2
Input: 
XI
1
2
Output: 
6

思路

将罗马数字转换成十进制数。

对罗马数字的转换规则并不是很熟悉,搜索之后也看得一脸懵逼…

来源: 维基百科—罗马数字

  • 重复数次:一个罗马数字重复几次,就表示这个数的几倍。
  • 右加左减:
    • 在较大的罗马数字的右边记上较小的罗马数字,表示大数字加小数字。
    • 在较大的罗马数字的左边记上较小的罗马数字,表示大数字减小数字。
    • 但是,左减时不可跨越一个位值。
    • 左减数字必须为一位。
    • 右加数字不可连续超过三位。
  • 加线乘千:
    • 在罗马数字的上方加上一条横线或者加上下标的Ⅿ,表示将这个数乘以1000,即是原数的1000倍。
    • 同理,如果上方有两条横线,即是原数的1000000倍。
  • 数码限制:
    • 同一数码最多只能连续出现三次,如40不可表示为XXXX,而要表示为XL。
    • 例外:由于IV是古罗马神话主神朱庇特(即IVPITER,古罗马字母里没有J和U)的首字,因此有时用IIII代替IV。

好在本题只要求罗马数字转十进制且数字范围不大,我们其实只要关注重复数次右加左减这两个规则。简单来说,就是直接把所有数字都加起来,再扣掉“左减”的贡献即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
unordered_map<char, int> hs;

void initMap() {
hs['I'] = 1; hs['V'] = 5;
hs['X'] = 10; hs['L'] = 50;
hs['C'] = 100; hs['D'] = 500;
hs['M'] = 1000;
}

int romanToInt(string s) {
initMap();
int ans = hs[s[0]], n = s.size();
for (int i = 1; i < n; ++i) {
if (hs[s[i-1]] < hs[s[i]]) ans += hs[s[i]] - 2*hs[s[i-1]];
else ans += hs[s[i]];
}
return ans;
}
};
分享到 评论