前言

❤️笔芯❤️~

栈,队列,链表,集合,字典和散列表,树,图

13. 罗马数字转整数

一、题目描述

罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。

image.png

image.png

二、思路分析

  1. 罗马数字由I,V,X,L,C,D,M 构成;
  2. 当小值在大值的左边,则减小值,如 IV=5-1=4
  3. 当小值在大值的右边,则加小值,如 VI=5+1=6
  4. 由上可知,右值永远为正,因此最后一位必然为正

把一个小值放在大值的左边,就是做减法,否则为加法。

image.png

  • 首先将所有的组合可能性列出并添加到哈希表中
  • 然后对字符串进行遍历,由于组合只有两种,一种是 1 个字符,一种是 2 个字符,其中 2 个字符优先于 1 个字符
  • 先判断两个字符的组合在哈希表中是否存在,存在则将值取出加到结果 ans 中,并向后移2个字符。不存在则将判断当前 1 个字符是否存在,存在则将值取出加到结果 ans 中,并向后移 1 个字符
  • 遍历结束返回结果 ans

image.png

image.png

image.png

image.png

三、答案代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
var romanToInt = function(s) {
let map = {
I: 1,
IV: 4,
V: 5,
IX: 9,
X: 10,
XL: 40,
L: 50,
XC: 90,
C: 100,
CD: 400,
D: 500,
CM: 900,
M: 1000
}
let ans = 0;
for(let i=0; i<s.length;){
if( i+1 < s.length && map[s.substring(i,i+2)] ){
// 2个一组
ans += map[s.substring(i,i+2)];
i += 2;
}else{
// 单一个
ans += map[s.substring(i,i+1)];
i++;
}
}
return ans;
};

四、总结

  1. 罗马数字转整数题解

回看笔者往期高赞文章,也许能收获更多喔!

❤️关注+点赞+收藏+评论+转发❤️,原创不易,鼓励笔者创作更好的文章