【题目】
Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
【分析】
这是一种首先会想到的思路:一个一个字母解析,先解析是不是双字母罗马数字,如果不是就按单字母罗马数字解析。
【代码】
/*********************************
* 日期:2015-01-22
* 作者:SJF0115
* 题目: 13.Roman to Integer
* 网址:https://oj.leetcode.com/problems/roman-to-integer/
* 结果:AC
* 来源:LeetCode
* 博客:
**********************************/
#include <iostream>
using namespace std;
class Solution {
public:
int romanToInt(string s) {
int result = 0;
int len = s.length();
if(len <= 0){
return result;
}//if
for(int i = 0;i < len;++i){
if(s[i] == 'M'){
result += 1000;
}//if
else if(s[i] == 'D'){
result += 500;
}
else if(s[i] == 'C'){
if(s[i+1] == 'M'){
result += 900;
++i;
}//if
else if(s[i+1] == 'D'){
result += 400;
++i;
}
else{
result += 100;
}
}
else if(s[i] == 'L'){
result += 50;
}
else if(s[i] == 'X'){
if(s[i+1] == 'C'){
result += 90;
++i;
}//if
else if(s[i+1] == 'L'){
result += 40;
++i;
}
else{
result += 10;
}
}
else if(s[i] == 'V'){
result += 5;
}
else if(s[i] == 'I'){
if(s[i+1] == 'X'){
result += 9;
++i;
}
else if(s[i+1] == 'V'){
result += 4;
++i;
}
else{
result += 1;
}
}
}//for
return result;
}
};
int main(){
Solution solution;
string roman = "XCVIII";
int result = solution.romanToInt(roman);
// 输出
cout<<result<<endl;
return 0;
}
【分析二】
在一个较大的罗马数字的右边记上一个较小的罗马数字,表示大数字加小数字。在一个较大的数字的左边记上1个较小的罗马数字,表示大数字减小数字。
可以通过判断相邻两个数的大小来计算
【代码二】
class Solution {
public:
int romanToInt(string s) {
int result = 0;
int len = s.length();
if(len <= 0){
return result;
}//if
int value[] = {1000,500,100,50,10,5,1};
// 转换
int i;
for(i = 0;i < len-1;++i){
int index = FindIndex(s[i]);
int index2 = FindIndex(s[i+1]);
// 相邻左边下标大于等于右边下标
if(index <= index2){
result += value[index];
}
// 相邻左边下标小于右边下标
else{
result += value[index2] - value[index];
++i;
}
}//for
if(i != len){
// 最后一个元素
int index = FindIndex(s[len-1]);
result += value[index];
}//if
return result;
}
private:
int FindIndex(char r){
char roman[] = {'M','D','C','L','X','V','I'};
for(int i = 0;i < 7;++i){
if(r == roman[i]){
return i;
}//if
}//for
return -1;
}
};
【分析三】
从前向后扫描,如果当前比前一个大,说明这一段的值为当前值减去上一个值(如IV = 5 -1 = 4),否则将当前值加入结果中。
有一点需要说明一下:
假如遍历到CD,遍历‘C’时,‘C’的值小于'D'的值,加入结果中,遍历‘D’时,比前一个值大,结果应该是加上当前值减去上一个值,可是再遍历‘C’时,多加了一个'C'的值
因此在遍历‘D’时应再减去一个‘C’的值。即当前值减去两个上一个值,result += map(s[i]) - 2*map(s[i-1]);
【代码三】
class Solution {
public:
int romanToInt(string s) {
int result = 0;
int len = s.length();
// 转换
for(int i = 0;i < len;++i){
if(i > 0 && map(s[i]) > map(s[i-1])){
result += map(s[i]) - 2*map(s[i-1]);
}
else{
result += map(s[i]);
}
}//for
return result;
}
private:
int map(char r){
switch(r){
case 'M':return 1000;
case 'D':return 500;
case 'C':return 100;
case 'L':return 50;
case 'X':return 10;
case 'V':return 5;
case 'I':return 1;
default:return 0;
}
}
};
分享到:
相关推荐
LeetCode Roman to Integer解决方案
leetcode上Roman to Integer的完整C++代码,已被accepted
13. 罗马数字转整数 Roman to Integer用哈希存储映射字符--->对映的值对字符串的字符挨个判断,考虑下一个字符如果下一个字符大于当前字符,su
13. Roman to Integer 15. 3Sum 16. 3Sum Closest 17. Letter Combinations of a Phone Number 18. 4Sum 19. Remove Nth Node From End of List 20. Valid Parentheses 21. Merge Two Sorted Lists 22. Generate ...
13. Roman to Integer 14. Longest Common Prefix 15. 3Sum 20. Valid Parentheses 21. Merge Two Sorted Lists 22. Generate Parentheses 25. Reverse Nodes in k-Group 26. Remove Duplicates from Sorted Array ...
Leetcode回文串拼接 leetcode_node 题解 该项目主要用于基于Leetcode的刷题记录,与日常...13.Roman To Integer 289 347 380 442 457 Circular Array Loop 535 Encode and Decode TinyURL 560 565 566 Maximum Binary T
第 338 章力码 LeetCode刷题总结 ...13.Roman to Integer 14.Longest Common Prefix (Trie树待完成) 15.3Sum 16.3Sum Closest 17.Letter Combinations of a Phone Number 18.4Sum 19.Remove Nth Node From End
leetcode Python 001 leetcode的算法问题 这是我的解决方案,用 cpp 、 java 和 python 编写 #LeetCode 解决的问题: 001. Two Sum 002. Add Two Numbers 003. Longest Substring Without Repeating Characters4. ...
leetcode 跳跃 LeetCode Solved by Python easy/middle/hard:15/36/5 1. Two Sum 两数之和 2. Add Two Numbers 两数相加 ...Integer ...to Integer ...Integer to Roman ...13. Roman to Integer 罗马数字转
Up to date (2016-12-18), there are `447` Algorithms / `13` Database / `4` Shell / `4` Draft questions on [LeetCode Online Judge](https://leetcode.com/). The number of questions is increasing recently...
加油站 ...1.Roman to Integer 2.Binary Tree Level Order Travasal II 3.Binary Tree Level Order Travasal 4.Contains Duplicate II 5.Contains Duplicate 07/02/2015 1.Valid Parentheses 2.Maximum
13. Roman to Integer 查表,通过从前往前筛选字符串,把代表的值一个个加起来 26. Remove Duplicates from Sorted Array 难度easy的题目。根据题目要求,是不能新建数组。只能在原来的基础上做修改。基本上这个算法...
leetcode-integer_to_roman
13. Roman to Integer:这道题没有思路,翻阅讨论区发现原来IV其实就是V-I其余类似,都是前一个减去后一个。 14. Longest Common Prefix:这道题和大家思路一样,都是取第一个字符串里的字节与后面的进行比较,只是...
java lru leetcode Fighting for a job! 记录找工作期间搬运的题,全部使用Java实现,本人C++鶸 1 ...LeetCode ...LeetCode ...LeetCode ...LeetCode ...LeetCode ...LeetCode ...LeetCode ...LeetCode ...Integer LeetCode 6 Zi
leetcode 答案力码 做LeetCode 1.【二和】(Array & Hash Table) (Easy) 20190911 完成 2.【加两个数】(链表&数学)(中) ...3.【无重复字符的最长子串...13.【Roman To Integer】(中) 20181106完成的IIV是非法的? 14.
lru缓存leetcode 力码 涵盖了 Geeks for Geeks 和 Leet Code 的各种问题。...Integer (249_Easy) LeetCode 14 : 最长公共前缀 (250_Easy) LeetCode 15 : 3Sum (271_Medium) LeetCode 17 : 电话号码的
Integer 运行时间:52 毫秒内存使用:14.1 MB 14. Longest Common Prefix 运行时间:40 毫秒内存使用:13.9 MB 20. Valid Parentheses 运行时间:40 毫秒内存使用:13.8 MB 22. Generate Parentheses 运行时间:164 ...
问题/数组和字符串/13.roman_to_integer.md) [26. Remove Duplicates from Sorted Array](Leetcode Problems/Array and String/26_remove_duplicates_from_sorted_array.md) [(雅虎)139。 Word Break](Leetcode ...
12.integer-to-roman,自动创建文件夹和文件并使用vim打开文件(如下文件内容是自动生成的,根据剪贴板中的代码) 在 Solution 类中填写代码,保存退出 在终端输入leetcode commit ,即可将Solution类的代码复制到系统...