欢迎来到李耶的频道【LeetCode面试题】。罗马数字转整数 LeetCode 原题链接题目罗马数字包含以下七种字符IVXLCD和M。字符 数值I 1V 5X 10L 50C 100D 500M 1000例如罗马数字 2 写做II即为两个并列的 1。12 写做XII即为XII。27 写做XXVII即为XXVII。通常情况下罗马数字中小的数字在大的数字的右边。但也存在特例例如 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。给定一个罗马数字将其转换成整数。输入s III 输出3 输入s IV 输出4 输入s IX 输出9 输入s LVIII 输出58 解释L 50, V 5, III 3 输入s MCMXCIV 输出1994 解释M 1000, CM 900, XC 90, IV 4解法一直接遍历哈希表 减法规则思路建立一个哈希表存储字符到数值的映射。遍历字符串中的每个字符如果当前字符代表的数值小于下一个字符代表的数值说明遇到了减法规则如 IV此时从结果中减去当前字符的数值否则加上当前字符的数值。functionromanToInt(s){constmap{I:1,V:5,X:10,L:50,C:100,D:500,M:1000};letresult0;for(leti0;is.length;i){constcurrentmap[s[i]];constnexti1s.length?map[s[i1]]:0;if(currentnext){result-current;}else{resultcurrent;}}returnresult;}时间复杂度 / 空间复杂度O(n) / O(1)优势只需一次遍历代码简洁是面试中最推荐的写法解法二字符串替换法思路先将特殊的六种减法规则替换为对应的数值表示如 IV 替换为 “IIII”但数值上替换为特定标识然后统一处理。functionromanToInt(s){constmap{I:1,V:5,X:10,L:50,C:100,D:500,M:1000};// 将减法规则的两位字符替换为可处理的格式ss.replace(IV,IIII);ss.replace(IX,VIIII);ss.replace(XL,XXXX);ss.replace(XC,LXXXX);ss.replace(CD,CCCC);ss.replace(CM,DCCCC);letresult0;for(constcharofs){resultmap[char];}returnresult;}时间复杂度 / 空间复杂度O(n) / O(n)字符串替换创建新字符串优势将复杂的特殊规则转化为统一处理思路独特劣势字符串替换效率较低面试中不推荐解法对比解法时间 / 空间复杂度优势推荐指数直接遍历哈希表 减法规则O(n) / O(1)一次遍历空间最优⭐⭐⭐⭐⭐字符串替换法O(n) / O(n)思路独特易于理解特殊规则处理⭐⭐⭐扩展题整数转罗马数字给定一个整数将其转换为罗马数字。Excel 表列序号给定一个 Excel 表格中的列名称返回其对应的列序号如 A - 1, Z - 26, AA - 27。Excel 表列名称给定一个正整数返回它在 Excel 表格中对应的列名称。“多见者博多闻者智。” —— 桓宽《盐铁论》关注李耶每天一道面试题一起卷起来