【LeetCode】13. Roman to Integer (2 solutions)
LeetCode to 13 Integer Solutions
2023-09-11 14:20:27 时间
Roman to Integer
Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
解法一:非递归
从左到右遍历每个字符,并记录上个字符来处理双字符情况即可。
class Solution { public: int romanToInt(string s) { int n = 0; char lastC = 0; for(int i = 0; i < s.size(); i ++) { switch(s[i]) { case 'I': n += 1; lastC = s[i]; break; case 'V': if(lastC == 'I') {//IV n -= 1; n += 4; lastC = 0; } else { n += 5; lastC = s[i]; } break; case 'X': if(lastC == 'I') {//IX n -= 1; n += 9; lastC = 0; } else { n += 10; lastC = s[i]; } break; case 'L': if(lastC == 'X') {//XL n -= 10; n += 40; lastC = 0; } else { n += 50; lastC = s[i]; } break; case 'C': if(lastC == 'X') {//XC n -= 10; n += 90; lastC = 0; } else { n += 100; lastC = s[i]; } break; case 'D': if(lastC == 'C') {//CD n -= 100; n += 400; lastC = 0; } else { n += 500; lastC = s[i]; } break; case 'M': if(lastC == 'C') {//CM n -= 100; n += 900; lastC = 0; } else { n += 1000; lastC = s[i]; } break; default: return 0; } } return n; } };
解法二:递归
处理开头字符情况之后递归处理后续字符串
class Solution { public: int romanToInt(string s) { if(s == "") return 0; //to here, s.size() >= 1 else if(s[0] == 'M') return 1000 + romanToInt(s.substr(1)); else if(s[0] == 'C') { if(s.size() == 1) //s == "C" return 100; if(s[1] == 'M') return 900 + romanToInt(s.substr(2)); else if(s[1] == 'D') return 400 + romanToInt(s.substr(2)); else return 100 + romanToInt(s.substr(1)); } else if(s[0] == 'D') return 500 + romanToInt(s.substr(1)); else if(s[0] == 'X') { if(s.size() == 1) //s == "X" return 10; if(s[1] == 'C') return 90 + romanToInt(s.substr(2)); else if(s[1] == 'L') return 40 + romanToInt(s.substr(2)); else return 10 + romanToInt(s.substr(1)); } else if(s[0] == 'L') return 50 + romanToInt(s.substr(1)); else if(s[0] == 'I') { if(s.size() == 1) //s == "I" return 1; if(s[1] == 'X') return 9 + romanToInt(s.substr(2)); else if(s[1] == 'V') return 4 + romanToInt(s.substr(2)); else return 1 + romanToInt(s.substr(1)); } else if(s[0] == 'V') return 5 + romanToInt(s.substr(1)); } };
相关文章
- [systemd]How To Use Systemctl to Manage Systemd Services and Units
- Java实现 LeetCode 787 K 站中转内最便宜的航班(两种DP)
- Java实现 LeetCode 747 至少是其他数字两倍的最大数(暴力)
- Java实现 LeetCode 621 任务调度器(暴力大法)
- Java实现 LeetCode 563 二叉树的坡度(又是一个遍历树)
- Java实现 LeetCode 381 O(1) 时间插入、删除和获取随机元素 - 允许重复
- Java实现 LeetCode 278 第一个错误的版本
- Java实现 LeetCode 275 H指数 II
- Java实现 LeetCode 223 矩形面积
- Java实现 LeetCode 83 删除排序链表中的重复元素
- 【LeetCode算法-13】Roman to Integer
- [LeetCode] Different Ways to Add Parentheses
- [LeetCode] Integer to English Words
- [LeetCode] Best Time to Buy and Sell Stock II
- [LeetCode] String to Integer (atoi)
- 【LeetCode 75】颜色分类
- 【LeetCode-面试算法经典-Java实现】【008-String to Integer (atoi) (字符串转成整数)】
- Leetcode:Swap Nodes in Pairs 单链表相邻两节点逆置
- [LeetCode]Best Time to Buy and Sell Stock II
- Leetcode - Best Time to Buy and Sell Stock
- Leetcode:best_time_to_buy_and_sell_stock_II题解
- leetcode 198. House Robber
- leetcode 405. Convert a Number to Hexadecimal
- leetcode 453. Minimum Moves to Equal Array Elements
- LeetCode 92. 反转链表 II
- 【LeetCode】128. 最长连续序列