Roman to Integer

最后更新于:2022-04-01 22:56:00

## 一.题目描述 Given a roman numeral, convert it to an integer.  Input is guaranteed to be within the range from 1 to 3999. ## 二.题目分析 还是先总结一下罗马数字,这是网上找到的一些解释:  罗马数字是最古老的数字表示方式,比阿拉伯数组早2000多年,起源于罗马…  罗马数字有如下符号:  基本字符: I V X L C D M  对应阿拉伯数字 :1 5 10 50 100 500 1000  计数规则: 相同的数字连写,所表示的数等于这些数字相加得到的数,例如:`III = 3`小的数字在大的数字右边,所表示的数等于这些数字相加得到的数,例如:`VIII = 8`小的数字,限于(I、X和C)在大的数字左边,所表示的数等于大数减去小数所得的数,例如:`IV = 4`正常使用时,连续的数字重复不得超过三次在一个数的上面画横线,表示这个数扩大`1000`倍。 **题目思路**,从输入字符串的第一个字符开始(从前向后遍历罗马数字),假设有一个临时变量`k`,结果存放在`result`变量中,算法执行过程中分为以下三种情况: 如果当前字符所对应的数字比前一位字符小,那么就可以先将临时变量的值`k`加到结果`result`中,然后开始下一段记录。比如`VI = 5 + 1`,此时当前为为`'I'`,小于前一位`'V'`,又`k = 5`,当前位对应的数值`curr = 1`,则结果更新为:`result = k + curr`,然后更新临时变量`k = curr`。 如果当前字符所对应的数字和上一个字符一样,那么临时变量`k`加上这个字符。比如`XXX = 30`,在此过程中`k = 10 + 10 + 10`。 如果当前字符所对应的数字比前一位字符大,意味着这一段的值应该是当前这个值减去前面累加的临时变量`k`中的值,比如`IIV = 5 – 2`。 ## 三.示例代码 ~~~ class Solution { public: int getRomanValue(char c) { switch (c) { case 'I': return 1; case 'V': return 5; case 'X': return 10; case 'L': return 50; case 'C': return 100; case 'D': return 500; case 'M': return 1000; default: return 0; } } int romanToInt(string s) { if (s.size() < 1) return -1; int result = 0; int temp = getRomanValue(s[0]); int k = temp; for (size_t i = 1; i < s.size(); i++) { int curr = getRomanValue(s[i]); if (temp > curr) { result += k; k = curr; } else if (temp == curr) k = k + curr; else k = curr - k; temp = curr; } result += k; return result; } }; ~~~ ## 四.小结 网上有更简便的思路: ~~~ class Solution { public: int romanToInt(string s) { int map[26]; map['I' - 'A'] = 1; map['V' - 'A'] = 5; map['X' - 'A'] = 10; map['L' - 'A'] = 50; map['C' - 'A'] = 100; map['D' - 'A'] = 500; map['M' - 'A'] = 1000; int res = 0, n = s.size(); s.push_back(s[n - 1]); for (int i = 0; i < n; i++) { if (map[s[i] - 'A'] >= map[s[i + 1] - 'A']) res += map[s[i] - 'A']; else res -= map[s[i] - 'A']; } return res; } }; ~~~ 对应的题目:Integer to Roman。
';