leetcode13__0">leetcode13. 罗马数字转整数
示例 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 <= 15
s 仅含字符 (‘I’, ‘V’, ‘X’, ‘L’, ‘C’, ‘D’, ‘M’)
题目数据保证 s 是一个有效的罗马数字,且表示整数在范围 [1, 3999] 内
题目所给测试用例皆符合罗马数字书写规则,不会出现跨位等情况。
IL 和 IM 这样的例子并不符合题目要求,49 应该写作 XLIX,999 应该写作 CMXCIX 。
题目描述
给定一个罗马数字字符串,将其转换为整数。
算法分析
这个问题可以通过遍历罗马数字字符串并解析每个字符来解决。罗马数字由特定的字符表示,每个字符都有其对应的整数值。在解析时,我们需要考虑一些特殊情况,比如某些字符组合(如IV, IX, XL, XC, CD, CM)表示的整数值与单个字符的组合不同。
算法步骤
- 初始化一个变量
res
用于存储结果,并将其设置为 0。 - 遍历罗马数字字符串
s
。 - 对于每个字符,根据其值和其后的字符,更新
res
。 - 考虑特殊情况,如IV, IX等,并正确处理。
- 返回最终结果
res
。
算法流程
具体代码
class Solution {
public:int romanToInt(string s) {int n=s.size();int res=0;for(int i=0;i<n;i++){if(s[i]=='I'){if(s[i+1]=='V'){res+=4;i++;}else if(s[i+1]=='X'){res+=9;i++;}else{res+=1;}}else if(s[i]=='X'){if(s[i+1]=='L'){res+=40;i++;}else if(s[i+1]=='C'){res+=90;i++;}else{res+=10;}}else if(s[i]=='C'){if(s[i+1]=='D'){res+=400;i++;}else if(s[i+1]=='M'){res+=900;i++;}else{res+=100;}}else {if(s[i]=='V'){res+=5;}else if(s[i]=='L'){res+=50;}else if(s[i]=='D'){res+=500;}else if(s[i]=='M'){res+=1000;}}}return res;}
};
算法分析
复杂度分析
- 时间复杂度:O(n),其中 n 是字符串
s
的长度。 - 空间复杂度:O(1),我们只需要常数级别的额外空间。
易错点
- 在处理特殊情况时,确保正确地识别和处理它们。
- 在更新结果时,确保正确地计算整数值。
注意事项
- 确保在遍历字符串时不要超出字符串的边界。
- 在处理字符串元素时,确保不会转换错误。
相似题目
题目 | 链接 |
---|---|
罗马数字转整数 | https://leetcode.com/problems/roman-to-integer/ |
整数转罗马数字 | https://leetcode.com/problems/integer-to-roman/ |
反转字符串 | https://leetcode.com/problems/reverse-string/ |
字符串转换整数 | https://leetcode.com/problems/string-to-integer-atoi/ |