您现在的位置是：首页 >技术交流 >LeetCode-13.罗马数字转整数（C/C++）网站首页技术交流
LeetCode-13.罗马数字转整数（C/C++）
简介LeetCode-13.罗马数字转整数（C/C++）
题目描述
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I可以放在V(5) 和X(10) 的左边，来表示 4 和 9。X可以放在L(50) 和C(100) 的左边，来表示 40 和 90。C可以放在D(500) 和M(1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。
示例 1:
输入: s = "III" 输出: 3
示例 2:
输入: s = "IV" 输出: 4
示例 3:
输入: s = "IX" 输出: 9
示例 4:
输入: s = "LVIII" 输出: 58 解释: L = 50, V= 5, III = 3.
示例 5:
输入: s = "MCMXCIV" 输出: 1994 解释: M = 1000, CM = 900, XC = 90, IV = 4.
提示：
1 <= s.length <= 15s仅含字符('I', 'V', 'X', 'L', 'C', 'D', 'M')- 题目数据保证
s是一个有效的罗马数字，且表示整数在范围[1, 3999]内 - 题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
- IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。
- 关于罗马数字的详尽书写规则，可以参考 罗马数字 - 百度百科。
题解
总体思路：（官方学习最简思路）
通常情况下，罗马数字中小的数字在大的数字的右边。若输入的字符串满足该情况，那么可以将每个字符视作一个单独的值，累加每个字符对应的数值即可。
例如 XXVII 可视作 X+X+V+I+I=10+10+5+1+1=27。
若存在小的数字在大的数字的左边的情况，根据规则需要减去小的数字。对于这种情况，我们也可以将每个字符视作一个单独的值，若一个数字右侧的数字比它大，则将该数字的符号取反。
例如 XIV 可视作 X−I+V=10−1+5=14。
如下提供五种解法：
-
小白（本人）映射解法，直观理解
创建字符和整数值的映射数组，对输入字符串每个字符找到映射数组数值，正常情况左大右小，其它特殊情况特殊处理（这里其实判断左小右大就减）两种情况，正常情况累加每位字符对应数值，特殊情况特殊处理。
int romanToInt(char* s){
int result = 0; // 初始化结果为0
int i = 0; // 初始化索引为0
// 定义字符和整数值对应的结构体
typedef struct{
char character; // 罗马数字字符
int value; // 对应的整数值
} CharValuePair;
// 创建字符和整数值的映射数组
CharValuePair pairs[7]={
{'I',1}, // I对应1
{'V',5}, // V对应5
{'X',10}, // X对应10
{'L',50}, // L对应50
{'C',100}, // C对应100
{'D',500}, // D对应500
{'M',1000}, // M对应1000
};
// 遍历字符串直到遇到空字符' '
while(s[i]!= ' '){
// 遍历字符和整数值的映射数组
for(int j = 0; j < 7; j++){
// 如果当前字符与映射数组中的某个字符匹配
if(s[i] == pairs[j].character){
// 如果当前字符不是'I', 'X', 'C'，直接加到结果中
if(j != 0 && j != 2 && j != 4){
result += pairs[j].value;
break; // 找到匹配后跳出循环
}
// 如果当前字符是'I'，检查下一个字符以决定如何转换
else if(j == 0){
// 如果下一个字符是'V'，则组合为4
if(s[i+1] == 'V'){
result += 5 - pairs[j].value;
i++; // 跳过下一个字符
}
// 如果下一个字符是'X'，则组合为9
else if(s[i+1] == 'X'){
result += 10 - pairs[j].value;
i++; // 跳过下一个字符
}
// 否则直接加1
else{
result += pairs[j].value;
}
break; // 找到匹配后跳出循环
}
// 如果当前字符是'X'，检查下一个字符以决定如何转换
else if(j == 2){
// 如果下一个字符是'L'，则组合为40
if(s[i+1] == 'L'){
result += 50 - pairs[j].value;
i++; // 跳过下一个字符
}
// 如果下一个字符是'C'，则组合为90
else if(s[i+1] == 'C'){
result += 100 - pairs[j].value;
i++; // 跳过下一个字符
}
// 否则直接加10
else{
result += pairs[j].value;
}
break; // 找到匹配后跳出循环
}
// 如果当前字符是'C'，检查下一个字符以决定如何转换
else if(j == 4){
// 如果下一个字符是'D'，则组合为400
if(s[i+1] == 'D'){
result += 500 - pairs[j].value;
i++; // 跳过下一个字符
}
// 如果下一个字符是'M'，则组合为900
else if(s[i+1] == 'M'){
result += 1000 - pairs[j].value;
i++; // 跳过下一个字符
}
// 否则直接加100
else{
result += pairs[j].value;
}
break; // 找到匹配后跳出循环
}
}
}
i++; // 移动到下一个字符
}
return result; // 返回转换后的整数
}
-
时间复杂度
对于每一个输入的字符，算法都需要遍历长度固定的字符-数值对数组（长度为7）。因此，算法的时间复杂度为O(n)，其中n是输入字符串s的长度。虽然在每个字符上都有一个内层循环，但由于内层循环的长度是固定的，因此可以视为常数时间操作。
-
空间复杂度
算法的空间复杂度为O(1)，因为使用的额外空间（字符-数值对数组和几个整数变量）不随输入字符串长度变化。字符-数值对数组的大小是固定的7个元素，整数变量用于存储结果和索引位置，因此空间复杂度是常数级别的。
-
自己解法优化版
1. 避免不必要的嵌套循环
使用了两层循环：外层遍历字符串，内层循环遍历字符和值的映射。实际上，只需要简单的比较当前字符和下一个字符来确定是否需要减去当前字符的值。内层循环其实并不必要，可以通过直接映射来简化代码。
2. 减少不必要的判断
有很多判断语句来处理不同的字符位置（比如 j == 0, j == 2, j == 4）。实际上，只需要在遍历字符串时判断当前字符与下一个字符的大小关系即可，只有在当前字符值小于下一个字符时才减去当前字符值。
3. 合并判断逻辑
可以在遍历过程中直接检查当前字符和下一个字符的大小关系来决定是否做减法，这样可以减少重复的代码和复杂的逻辑。
int romanToInt(char* s) {
int result = 0; // 初始化结果为0
int i = 0; // 初始化索引为0
// 定义罗马数字字符到数字的映射结构体
typedef struct {
char character;
int value;
} CharValuePair;
// 创建字符和整数值的映射数组
CharValuePair pairs[7] = {
{'I', 1}, // I对应1
{'V', 5}, // V对应5
{'X', 10}, // X对应10
{'L', 50}, // L对应50
{'C', 100}, // C对应100
{'D', 500}, // D对应500
{'M', 1000} // M对应1000
};
// 创建字符到数字的映射表
int map[256] = {0}; // 创建256大小的字符映射表
for (int j = 0; j < 7; j++) {
map[(int)pairs[j].character] = pairs[j].value; // 将字符映射到对应的数值
}
// 遍历字符串并计算结果
while (s[i] != ' ') {
// 如果当前字符的值小于下一个字符的值，做减法（特殊情况如IV, IX等）
if (map[(int)s[i]] < map[(int)s[i + 1]]) {
result -= map[(int)s[i]]; // 减去当前字符的值
} else {
result += map[(int)s[i]]; // 否则加上当前字符的值
}
i++; // 移动到下一个字符
}
return result; // 返回转换后的整数
}
时间复杂度
- 构建映射表: 构建字符到数值的映射表需要遍历长度为7的
pairs数组，这是一个O(1)的操作。 - 遍历字符串: 遍历输入字符串
s需要O(n)的时间，其中n是字符串的长度。对于每个字符，算法需要查表两次（当前字符和下一个字符），但这仍然是常数时间内完成的操作。 - 总时间复杂度: 因此，整个算法的时间复杂度为O(n)，其中n是输入字符串的长度。
空间复杂度
- 映射表: 创建了一个大小为256的整数数组
map，用于存储字符到数值的映射。这个数组的大小是固定的，不随输入字符串长度变化，因此空间复杂度为O(1)。 - 其他变量: 使用了几个整数变量（
result和i）来存储中间结果和索引，这些变量的空间占用也是常数级别的。 - 总空间复杂度: 因此，整个算法的空间复杂度为O(1)。
-
逆序遍历
逆序遍历字符串，简化了减法操作的逻辑，避免了在遍历过程中进行大量的前后字符比较。此方法更为数学逻辑实现。
int romanToInt(char* s) {
int res = 0; // 初始化结果为0
int length = strlen(s); // 获取字符串的长度
// 从字符串的最后一个字符开始向前遍历
for (int i = length - 1; i >= 0; i--) {
char c = s[i]; // 获取当前字符
// 根据当前字符来更新结果
switch (c) {
case 'I':
// 如果结果大于等于5，说明'I'前面有'V'或'X'，表示减1
// 否则表示加1
res += (res >= 5 ? -1 : 1);
break;
case 'V':
res += 5; // 加5
break;
case 'X':
// 如果结果大于等于50，说明'X'前面有'L'或'C'，表示减10
// 否则表示加10
res += 10 * (res >= 50 ? -1 : 1);
break;
case 'L':
res += 50; // 加50
break;
case 'C':
// 如果结果大于等于500，说明'C'前面有'D'或'M'，表示减100
// 否则表示加100
res += 100 * (res >= 500 ? -1 : 1);
break;
case 'D':
res += 500; // 加500
break;
case 'M':
res += 1000; // 加1000
break;
}
}
return res; // 返回转换后的整数
}
时间复杂度
- 计算字符串长度: 使用
strlen函数获取字符串长度，时间复杂度为O(n)，其中n是字符串的长度。 - 遍历字符串: 从字符串的最后一个字符开始向前遍历，时间复杂度为O(n)。
- 字符处理: 在每次遍历中，使用
switch语句处理字符，时间复杂度为O(1)。 - 总时间复杂度: 因为
strlen和遍历字符串的时间复杂度都是O(n)，因此整个算法的时间复杂度为O(n)。
空间复杂度
- 结果变量: 使用了一个整数变量
res来存储结果，空间复杂度为O(1)。 - 长度变量: 使用了一个整数变量
length来存储字符串的长度，空间复杂度为O(1)。 - 总空间复杂度: 因此，整个算法的空间复杂度为O(1)，使用了常数级别的额外空间。
-
字符ASCII 值索引映射数组法（官方解法）
通过从字符串的左到右遍历，并利用罗马数字的特性来决定每个字符是加还是减。具体来说，罗马数字中较小的字符在较大的字符之前表示减法，否则表示加法。
int romanToInt(char* s) {
// 创建一个大小为26的数组来存储罗马数字字符的整数值
int symbolValues[26];
//数组的索引是通过字符减去'A'得到的，这样可以将罗马数字字符映射到数组中的特定位置。
// 初始化数组中对应罗马数字字符的值
symbolValues['I' - 'A'] = 1; // 'I'对应1
symbolValues['V' - 'A'] = 5; // 'V'对应5
symbolValues['X' - 'A'] = 10; // 'X'对应10
symbolValues['L' - 'A'] = 50; // 'L'对应50
symbolValues['C' - 'A'] = 100; // 'C'对应100
symbolValues['D' - 'A'] = 500; // 'D'对应500
symbolValues['M' - 'A'] = 1000; // 'M'对应1000
int ans = 0; // 初始化结果为0
int n = strlen(s); // 获取字符串的长度
// 遍历字符串中的每个字符
for (int i = 0; i < n; ++i) {
// 获取当前字符对应的整数值
int value = symbolValues[s[i] - 'A'];
// 如果当前字符不是最后一个字符，并且当前字符的值小于下一个字符的值
// 说明这是一个需要减法的情况（例如IV, IX, XL, XC等）
if (i < n - 1 && value < symbolValues[s[i + 1] - 'A']) {
ans -= value; // 减去当前字符的值
} else {
ans += value; // 否则加上当前字符的值
}
}
return ans; // 返回转换后的整数
}
时间复杂度
- 计算字符串长度:
strlen(s)的时间复杂度为 O(n)。 - 遍历字符串: 遍历字符串的每个字符，时间复杂度为 O(n)。
- 字符处理: 在每次遍历中，获取字符值和进行加减法操作，时间复杂度为 O(1)。
- 总时间复杂度: 因此，整个算法的时间复杂度为 O(n)。
空间复杂度
- 映射数组: 创建了一个大小为26的整数数组
symbolValues，空间复杂度为 O(1)。 - 结果变量: 使用了一个整数变量
ans来存储结果，空间复杂度为 O(1)。 - 长度变量: 使用了一个整数变量
n来存储字符串的长度，空间复杂度为 O(1)。 - 总空间复杂度: 因此，整个算法的空间复杂度为 O(1)，使用了常数级别的额外空间。
-
C++哈希表实现（最佳解法）
class Solution {
private:
// 创建一个无序映射表来存储罗马数字字符及其对应的整数值
std::unordered_map<char, int> symbolValues = {
{'I', 1}, // 'I'对应1
{'V', 5}, // 'V'对应5
{'X', 10}, // 'X'对应10
{'L', 50}, // 'L'对应50
{'C', 100}, // 'C'对应100
{'D', 500}, // 'D'对应500
{'M', 1000}, // 'M'对应1000
};
public:
int romanToInt(std::string s) {
int ans = 0; // 初始化结果为0
int n = s.length(); // 获取字符串的长度
// 遍历字符串中的每个字符
for (int i = 0; i < n; ++i) {
int value = symbolValues[s[i]]; // 获取当前字符对应的整数值
// 如果当前字符不是最后一个字符，并且当前字符的值小于下一个字符的值
// 说明这是一个需要减法的情况（例如IV, IX, XL, XC等）
if (i < n - 1 && value < symbolValues[s[i + 1]]) {
ans -= value; // 减去当前字符的值
} else {
ans += value; // 否则加上当前字符的值
}
}
return ans; // 返回转换后的整数
}
};
时间复杂度：
- O(n)：遍历字符串
s一次，每次查找字符对应的值，unordered_map查找的时间复杂度为 O(1)。因此，总时间复杂度为 O(n)，其中n是字符串的长度。
空间复杂度：
- O(1)：
unordered_map存储了 7 个常量大小的键值对，空间复杂度为 O(1)。
哈哈哈，分享趣评
风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。
站长推荐
- U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决 - 分享几个国内免费的ChatGPT镜像网址(亲测有效)
分享几个国内免费的ChatGPT镜像网址(亲测有效) - stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程） - QT多线程的5种用法，通过使用线程解决UI主界面的耗时操作代码，防止界面卡死。
QT多线程的5种用法，通过使用线程解决UI主界面的耗时操作代码，防止界面卡死。... - SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权