LeetCode 13. 罗马数字转整数题目难度简单题型分类字符串、哈希表、数学题目链接罗马数字转整数给定一个有效的罗马数字字符串s返回其对应的整数。罗马数字的基本符号如下符号IVXLCDM数值1510501005001000通常按数值从大到小排列并相加但以下组合使用减法IV → 4 IX → 9 XL → 40 XC → 90 CD → 400 CM → 900示例输入s III 输出3 输入s IV 输出4 输入s IX 输出9 输入s LVIII 输出58 输入s MCMXCIV 输出1994 解释M CM XC IV 1000 900 90 4。数据范围1 s.length 15s仅包含I、V、X、L、C、D、M。保证输入是有效的罗马数字表示的整数在[1, 3999]内。解题思路用映射表保存每个罗马字符对应的数值从左到右比较相邻字符当前数值小于右侧数值减去当前数值。否则加上当前数值。最后一个字符没有右侧字符直接加上。例如MCMXCIV1000 - 100 1000 - 10 100 - 1 5 1994题目保证输入合法因此不需要额外校验罗马数字的书写规则。平均时间复杂度O(n)其中n为字符串长度。空间复杂度O(1)映射表固定包含七个符号。JavaclassSolution{publicintromanToInt(Strings){MapCharacter,IntegerROMANnewHashMap();ROMAN.put(I,1);ROMAN.put(V,5);ROMAN.put(X,10);ROMAN.put(L,50);ROMAN.put(C,100);ROMAN.put(D,500);ROMAN.put(M,1000);intans0;for(inti0;is.length()-1;i){intxROMAN.get(s.charAt(i));intyROMAN.get(s.charAt(i1));if(xy){ans-x;}else{ansx;}}returnansROMAN.get(s.charAt(s.length()-1));}}CclassSolution{public:intromanToInt(string s){unordered_mapchar,intROMAN{{I,1},{V,5},{X,10},{L,50},{C,100},{D,500},{M,1000}};intans0;intns.size();for(inti0;in-1;i){intxROMAN[s[i]];intyROMAN[s[i1]];if(xy){ans-x;}else{ansx;}}returnansROMAN[s[n-1]];}};Python 3classSolution:defromanToInt(self,s:str)-int:ROMAN{I:1,V:5,X:10,L:50,C:100,D:500,M:1000}ans0foriinrange(len(s)-1):x,yROMAN[s[i]],ROMAN[s[i1]]ifxy:ans-xelse:ansxreturnansROMAN[s[-1]]