闯关leetcode——13. Roman to Integer
大纲
- 题目
- 地址
- 内容
- 解题
- 代码地址
题目
地址
https://leetcode.com/problems/roman-to-integer/description/
内容
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, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 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.
Example 1:
Input: s = “III”
Output: 3
Explanation: III = 3.
Example 2:
Input: s = “LVIII”
Output: 58
Explanation: L = 50, V= 5, III = 3.
Example 3:
Input: s = “MCMXCIV”
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
Constraints:
- 1 <= s.length <= 15
- s contains only the characters (‘I’, ‘V’, ‘X’, ‘L’, ‘C’, ‘D’, ‘M’).
- It is guaranteed that s is a valid roman numeral in the range [1, 3999].
解题
这题是要求将罗马数字转换成整型数字。这就要熟悉罗马数字特点：
- 罗马数字通过较小的数字在较大的数字的左侧还是右侧，来决定较小的数字是进行加法操作还是减法操作。如果较小数字出现在较大数字左侧，则表示减去较小数字。比如IV，V表示5，I表示1，I小于V且出现在V的左侧，则IV表示5-1=4；如果较小的数字出现在较大数字的右侧，则表示加上较大的数字。比如VI,I出现在V的右侧，于是VI表示5+1=4。
- 在表示一个比较大的数字时，大的数字在左侧。比如1994（MCMXCIV），表示千位的M会最先出现，表示4的IV最后出现。
基于上述规律，我们可以得出结论：如果一个数比上个数字小，则减去该数；如果大于等于上个数字，则加上该数。最后一位一定是加上。
#include <string>
#include <unordered_map>
using namespace std;class Solution {
public:int romanToInt(string s) {const unordered_map<char, int> roman_map = {{'I', 1},{'V', 5},{'X', 10},{'L', 50},{'C', 100},{'D', 500},{'M', 1000}};int result = 0;int previous_value = 0;for (char c : s) {int current_value = roman_map.at(c);if (previous_value < current_value) {result -= previous_value;} else {result += previous_value;}previous_value = current_value;}result += previous_value;return result;}
};
代码地址
https://github.com/f304646673/leetcode/tree/main/13-Roman-to-Integer
