时间轴

2025-11-09

init

题目：

P13 罗马数字转整数

https://leetcode.cn/problems/roman-to-integer/description/?envType=study-plan-v2&envId=top-interview-150

直接模拟计算即可

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <string>
#include <unordered_map>
#include <queue>

using std::unordered_map;
using std::string;
using std::queue;

class Solution {
    private:
	unordered_map<string, int> roman_alpha_to_int;

    public:
	Solution()
	{
		roman_alpha_to_int = { { "I", 1 },   { "V", 5 },   { "X", 10 },	 { "L", 50 },	{ "IV", 4 },
				       { "IX", 9 },  { "XL", 40 }, { "XC", 90 }, { "CD", 400 }, { "CM", 900 },
				       { "C", 100 }, { "D", 500 }, { "M", 1000 } };
	}
	int romanToInt(string s)
	{
		queue<char> ch_que;
		int res = 0;
		char front, next;

		for (char ch : s) {
			ch_que.push(ch);
		}

		while (!ch_que.empty()) {
			front = ch_que.front();
			ch_que.pop();
			string tmp;
			tmp.push_back(front);
			if (!ch_que.empty()) {
				next = ch_que.front();
				tmp.push_back(next);
				if (!roman_alpha_to_int.count(tmp)) { //
					tmp.pop_back();
				} else {
					ch_que.pop();
				}
			}
			res += roman_alpha_to_int[tmp];
		}
		return res;
	}
};
int main()
{
	Solution S;
	string s = "III";
	S.romanToInt(s);
}

上面这种方法用string hash效率不高，可以直接模拟：

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
class Solution {
private:
    unordered_map<char, int> symbolValues = {
        {'I', 1},
        {'V', 5},
        {'X', 10},
        {'L', 50},
        {'C', 100},
        {'D', 500},
        {'M', 1000},
    };

public:
    int romanToInt(string s) {
        int ans = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            int value = symbolValues[s[i]];
            if (i < n - 1 && value < symbolValues[s[i + 1]]) {
                ans -= value;
            } else {
                ans += value;
            }
        }
        return ans;
    }
};