LeetCode 13 罗马数字转整数
1. 题目13. 罗马数字转整数 - 力扣LeetCode题目描述罗马数字包含以下七种字符IVXLCDM。字符数值I1V5X10L50C100D500M1000特殊规则正常情况大数在右直接相加如III3、VI6减法特例I在V/X前 4/9X在L/C前 40/90C在D/M前 400/900。给定合法罗马字符串转换为对应整数。示例输入III→ 3输入IV→ 4输入IX→ 9输入LVIII→ 58输入MCMXCIV→ 1994约束1≤s.length≤15s 仅由I,V,X,L,C,D,M组成输入保证合法罗马数字2. 最佳解题思路描述哈希映射 后项比较极简通用核心规律罗马数字整体从左到右数值递减若当前字符值 右侧字符值属于减法组合总和减去当前值其余情况总和加上当前值。步骤建立字符到数字的映射表遍历字符串到倒数第二位map[s[i]] map[s[i1]]sum - map[s[i]]否则sum map[s[i]]最后单独加上末尾字符的值优势代码短无冗长 switch 分支统一一套判断逻辑不用分七种字符单独处理特殊情况时间O(n)空间O(1)固定 7 个映射。3. 我的可优化代码逻辑存在多处 bug思路繁琐class Solution { public: int romanToInt(string s) { int sum 0; for(int i0;is.length();i){ switch(s[i]){ case I: if(s[i1]V||s[i1]X) break; sum; break; case V: if(i0 s[i-1]I){ sum4; break; } sum5; break; case X: if(i0 s[i-1]I){ sum9; break; } if(s[i1]L||s[i1]C) break; sum10; break; case L: if(i0 s[i-1]X){ sum40; break; } sum50; break; case C: if(i0 s[i-1]X){ sum90; break; } if(s[i1]D||s[i1]M) break; sum100; break; case D: if(i0 s[i-1]C){ sum400; break; } sum500; break; case M: if(i0 s[i-1]C){ sum900; break; } sum1000; break; default: break; } } return sum; } };代码致命 bug越界访问s[i1]i 走到最后一位时i1超出字符串下标访问非法内存运行崩溃重复叠加数值例如IVi0 (I) 满足s[i1]V直接 break不加 1i1 (V) 判断前一位是 Isum 4结果正确但IX、XL、XC、CD、CM均会出现重复特殊值叠加逻辑极容易算错分支逻辑割裂极易漏写 / 写错特殊条件七种字符分开处理每个字符单独判断左右相邻代码冗余庞大维护困难错误判断X分支判断s[i-1]I求 9逻辑写反IX是 I 在前 X 在后该判断永远不会触发IX计算直接出错。整体缺陷靠 switch 暴力分情况代码冗长、边界越界、逻辑易出错没有统一的数学判断规则靠人工枚举所有减法组合扩展性差。4. 最优标准代码哈希映射统一判断#include unordered_map #include string using namespace std; class Solution { public: int romanToInt(string s) { unordered_mapchar, int mp { {I,1},{V,5},{X,10},{L,50}, {C,100},{D,500},{M,1000} }; int sum 0; int n s.size(); for(int i 0; i n - 1; i){ if(mp[s[i]] mp[s[i1]]){ sum - mp[s[i]]; }else{ sum mp[s[i]]; } } // 最后一位一定只加不减 sum mp[s.back()]; return sum; } };5. 总结你的 switch 暴力分支写法存在数组越界、逻辑判断错误无法正常通过用例不推荐通用核心规则前小后大则减当前值否则加当前值一套逻辑覆盖所有情况遍历只到倒数第二位避免访问i1越界末尾字符单独累加用哈希表存储字符数值映射消除大量重复 if/switch 分支代码简洁易读。6. 相关知识拓展拓展 1反向遍历简化写法从后往前遍历记录最大值当前值小于最大值则相减否则更新最大值并相加int romanToInt(string s) { unordered_mapchar,int mp{{I,1},{V,5},{X,10},{L,50},{C,100},{D,500},{M,1000}}; int sum0,maxVal0; for(int is.size()-1;i0;i--){ int curmp[s[i]]; if(curmaxVal) sum-cur; else { sumcur; maxValcur; } } return sum; }拓展 2进阶题目 LC12 整数转罗马数字逆向转换采用贪心从大到小匹配数值符号对拓展 3复杂度对比switch 暴力分支代码冗余存在越界 bug理论时间 O (n)哈希正向遍历最优解时间 O (n)空间 O (1)固定 7 组映射反向遍历时间 O (n)空间 O (1)。拓展 4易错点记忆正向遍历不要访问s[n]循环上限n-1减法组合本质小数出现在大数左侧统一做减法无需单独枚举 IV、IX 等所有特例。
)
