算法练习——罗马数字转整数

2021年1月13日LeetCode每日一题为684. 冗余连接题解基本上都是并查集的解法,因此还是选择完成比较简单的13. 罗马数字转整数,这道题与上一道题整数转罗马数字相反,只需要想明白小的在左边就要减去它就可以了。从最后面开始往前遍历,发现这次的数字小于上次的数字,那么就减去这个数,否则加起来就可以了。

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
31
32
33
34
35
class Solution {
public int romanToInt(String s) {
char[] chars = s.toCharArray();
int sum = 0, pre = 1;
for (int i = chars.length - 1; i >= 0; i--) {
int v = getValue(chars[i]);
if (pre > v) {
sum -= v;
} else {
sum += v;
pre = v;
}
}
return sum;
}

public int getValue(char c) {
switch (c) {
case 'M':
return 1000;
case 'D':
return 500;
case 'C':
return 100;
case 'L':
return 50;
case 'X':
return 10;
case 'V':
return 5;
default:
return 1;
}
}
}

今日的每日一题最开始以为可以采用找回环的方式来找到,但是由于不够熟悉图结构,做了几次都不成功,只能求助题解,发现又是一个并查集的题解,无奈只能继续按顺序完成题库中的题目。罗马数字这题主要就是将数字映射好,并将其几种情况搞清楚就能完成,非常简单。