Leetcode 013. 罗马数字转整数

[meibin08]

题目描述:

罗马数字包含以下七种字符: 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， 因此时间复杂度为 $O(N)$。
• 空间复杂度：$O(1)$。

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题的分析思路直接摘抄如下

• 由罗马数字表示规则可知

  • 一般情况下 数字组成：大的数字位+小的数字位 ---- <1>
    • 例如：6：VI 7:VII 8:VIII
    • 可知：数值大小 == 大的数字位+小的数字位 ---- 《1》
    • 再如：1:I 2:II 3: III
  • 但当罗马数字进位值（个、十、百、千）== 9 或 == 4 时，数字组成变为：小的数字+大的数字 ---- <2>

  例如：4:IV    9:IX
      40:XL   90:XC
     400:CD  900:CM
  可知：数值大小 == 大的数字位-小的数字位 ---- 《2》
  

• 由以上分析可知

  • 《1》 即 左边的罗马数字 > 右边的罗马数字时 => 罗马数 == 左边罗马数字对应的阿拉伯数字 + 右边罗马数字对应的阿拉伯数字
  • 《2》 即 左边的罗马数字 < 右边的罗马数字时 => 罗马数 == 左边罗马数字对应的阿拉伯数字的反数即负数 + 右边罗马数字对应的阿拉伯数字
  • 且 罗马数字的转换表在上意味着 所有数字都可以有其中的罗马数字字符组成 => 建立罗马数字和阿拉伯数字 Hash对照表
  • 遍历罗马数字 因为转换表里对应的阿拉伯数字带有千、百、十和个位 所以 不需考虑9，99，999临界位 直接求出总和即可

代码

JavaScript 实现

/**
 * @来源： 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 题解 | 每日一题🔥 所有题目并非全部为本人解答，部分为在复习学习中整理提取其他解题作者的优秀笔记，便于大家学习共同进步，如有侵权，请联系删除。