013. 罗马数字转整数 | Leetcode题解
16lz
2021-01-22
题目描述:
罗马数字包含以下七种字符: I ， V ， X ， L ， C ， D 和 M 。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为X + II 。 27 写做 XXVII , 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 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。
给定一个罗马数字，将其转换成整数。输入确保在 1到 3999 的范围内。
示例1:
输入:"III"
输出: 3
示例2:
输入:"IV"
输出: 4
示例3:
输入:"IX"
输出: 9
示例4:
输入:"LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.
示例5:
输入:"MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.
难度：
- 难度：简单
- 支持语言：JavaScript、Python、C++
相关标签
- 数学
- 字符串
相关企业
- 字节
- 阿里巴巴
复杂度分析
- 时间复杂度：由于左右指针移动的次数加起来正好是 n， 因此时间复杂度为 。
- 空间复杂度：。
Js中文网 - 前端进阶资源教程 www.javascriptC.com,typescript 中文文档 Javascript中文网是以前端进阶资源教程分享为主的专业网站，包括：前端、大厂面试题、typescript教程、程序人生、React.js……等，以帮助开发者成长为愿景的社区
思路1：
- 注意
4和9是前一个数字比后一个数字小，其他都是前一个数字比后一个数字大。
思路2：
罗马数字转换为阿拉伯数字的时候，实际上是从左到右将每个字符对应的值累加的过程。例如“XVI”，实际就是
10（X）+5（V）+1（I）。只不过由于存在特殊规则增加了这个过程的复杂，不过同样可以用上面的思路解决。举个例子，“IX”，可以看作是-1+10=9；“XIX”可以看作是10-1+10=19。
题目又告诉我们，通常情况下，罗马数字中小的数字在大的数字的右边。所以，如果s[i]<s[i+1]，那s[i]在累加时需要加一个负号，这就完成了特殊规则的处理。
思路3：
- 利用switch语句将字符转换成对应的数字，然后去判断下一位字符是否比当前的字符大，若大则当前字符取相反数，然后sum++；
思路4：
给定一个罗马数字，将其转为整数，输入的数字在1到3999范围内。 已知：罗马数字包含以下七种字符：I,V,X,L,C,D,M
转换表为：
字符 数值 进位
I 1 个位值为1
V 5 个位值为5
X 10 十位值为1
L 50 十位值为5
C 100 百位值为1
D 500 百位值为5
M 1000 千位值为1
由我12题的分析思路直接摘抄如下
由罗马数字表示规则可知
例如：4:IV 9:IX
40:XL 90:XC
400:CD 900:CM
可知：数值大小 == 大的数字位-小的数字位 ---- 《2》- 例如：6：VI 7:VII 8:VIII
- 可知：数值大小 == 大的数字位+小的数字位 ---- 《1》
- 再如：1:I 2:II 3: III
- 一般情况下 数字组成：大的数字位+小的数字位 ---- <1>
- 但当罗马数字进位值（个、十、百、千）== 9 或 == 4 时，数字组成变为：小的数字+大的数字 ---- <2>
由以上分析可知
- 《1》 即 左边的罗马数字 > 右边的罗马数字时 => 罗马数 == 左边罗马数字对应的阿拉伯数字 + 右边罗马数字对应的阿拉伯数字
- 《2》 即 左边的罗马数字 < 右边的罗马数字时 => 罗马数 == 左边罗马数字对应的阿拉伯数字的反数即负数 + 右边罗马数字对应的阿拉伯数字
- 且 罗马数字的转换表在上意味着 所有数字都可以有其中的罗马数字字符组成 => 建立罗马数字和阿拉伯数字 Hash对照表
- 遍历罗马数字 因为转换表里对应的阿拉伯数字带有千、百、十和个位 所以 不需考虑9，99，999临界位 直接求出总和即可
代码
JavaScripe 实现
/**
* @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
* @param {string} s
* @return {number}
*/
var romanToInt = function(s) {
let hash={
I:1,
V:5,
X:10,
L:50,
C:100,
D:500,
M:1000
}
let sum=0
for(let i=0;i<s.length;i++){
let res
let cur=hash[s[i]]
let next=hash[s[i+1]]
if(next && cur < next){
res=next-cur
i++
}else{
res=cur
}
sum+=res
}
return sum
};
/**
* @param {number} num
* @return {string}
//作者：Alexer-660
//链接：https://leetcode-cn.com/problems/integer-to-roman/solution/12-zheng-shu-zhuan-luo-ma-shu-zi-by-alexer-660/
*/
var romanToInt = function(s) {
var hashNum = {
"I":1,
"V":5,
"X":10,
"L":50,
"C":100,
"D":500,
"M":1000
}
var result = 0;
for(let i = 0;i<s.length;i++){
hashNum[s[i]] < hashNum[s[i+1]] ? result -= hashNum[s[i]] : result += hashNum[s[i]]
}
return result;
};
/**
作者：iamapig120
链接：https://leetcode-cn.com/problems/integer-to-roman/solution/cyu-yan-js-cong-di-wei-kai-shi-an-wei-qu-zhi-cha-b/
*/
/**
* @param {string} s
* @return {number}
*/
var romanToInt = function(s) {
let keys = ['M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I'],
values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1],
res = 0, idx;
while(s.length) {
idx = keys.indexOf(s[0] + s[1]);//先判断是不是符合2个字符的单位
if(idx >= 0){
s = s.substring(2, s.length);
}else{
idx = keys.indexOf(s[0]);
s = s.substring(1, s.length);
}
res += values[idx];//得到对应的值
}
return res;
};
c++ 实现
//作者：iamapig120
//链接：https://leetcode-cn.com/problems/integer-to-roman/solution/cyu-yan-js-cong-di-wei-kai-shi-an-wei-qu-zhi-cha-b/
class Solution {
public:
int change(char a) {
switch(a)
{
case 'I':return 1;break;
case 'V':return 5;break;
case 'X':return 10;break;
case 'L':return 50;break;
case 'C':return 100;break;
case 'D':return 500;break;
case 'M':return 1000;break;
}
return 0;
}
int romanToInt(string s) {
int SUM=0,sum=0;
int i;
for(i=0;i<s.length();i++)
{
int num=change(s[i]);
if(change(s[i+1])>num)num=-num;
SUM+=num;
}
return SUM;
}
};
// 作者：junex233
// 链接：https://leetcode-cn.com/problems/roman-to-integer/solution/si-lu-qing-xi-shi-xian-jian-dan-de-fang-fa-by-june/
class Solution {
public:
int romanToInt(string s) {
int result=0;
map<char,int> luomab={
{'I',1},
{'V',5},
{'X',10},
{'L',50},
{'C',100},
{'D', 500},
{'M', 1000}
};//初始化哈希表
for(int i=0;i<s.length();i++)
{
if(luomab[s[i]] < luomab[s[i+1]])
result -= luomab[s[i]];
else
{
result += luomab[s[i]];
}
}
return result;
}
};
python 实现
# 作者：z1m
# 链接：https://leetcode-cn.com/problems/roman-to-integer/solution/qing-xi-tu-jie-python3-by-ml-zimingmeng/
class Solution:
def romanToInt(self, s: str) -> int:
Roman2Int = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
Int = 0
n = len(s)
for index in range(n - 1):
if Roman2Int[s[index]] < Roman2Int[s[index + 1]]:
Int -= Roman2Int[s[index]]
else:
Int += Roman2Int[s[index]]
return Int + Roman2Int[s[-1]]
# 作者：zkk-c
# 链接：https://leetcode-cn.com/problems/integer-to-roman/solution/tan-xin-ha-xi-biao-tu-jie-by-ml-zimingmeng/
class Solution:
def romanToInt(self, s: str) -> int:
#时间复杂度为O(n),空间复杂度为O(1)
d = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}
result = 0
for i in range(len(s) - 1):
if d[s[i]] >= d[s[i + 1]]:
result += d[s[i]]
else:
result -= d[s[i]]
result += d[s[-1]]
return result
其他
- 原题leetcode链接：https://leetcode-cn.com/problems/roman-to-integer/
- 合作方：JavaScript中文网 – 全球极客挚爱的技术成长平台
- 说明：leetcode 题解 | 每日一题
更多相关文章
- 012. 整数转罗马数字 | Leetcode题解
- 使用数字作为javascript对象元素的名称
- jQuery+EasyUI实现treegrid/datagride所绑定列只能够输入数字，且
- js限制文本框只能输入数字方法
- phpcms日期--汉字与数字的转换
- php实现完整版验证码（数字+大小写字母+干扰素）
- PHP中是否存在“clamp”数字函数?
- mysql_fetch_array返回一个数组，数字为“1”
- php 从指定数字中获取随机组合的方法
随机推荐