Leetcode 012. 整数转罗马数字

[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:

输入:3
输出: "III"

示例2:

输入:4
输出: "IV"

示例3:

输入:9
输出: "IX"

示例4:

输入:58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.

示例5:

输入:1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

难度：

• 难度：中等
• 支持语言：JavaScript、Python、C++

相关标签

• 数学
• 字符串

相关企业

• 字节
• 微保
• 爱奇艺

复杂度分析

• 时间复杂度：由于左右指针移动的次数加起来正好是 n， 因此时间复杂度为 $O(N)$。
• 空间复杂度：$O(1)$。

思路 1（javascript）:

注意4和9的处理方式，由于9的罗马文需要用到10，

I(1),V(5),X(10)处理范围[1,9]；
X(10),L(50),C(100)处理范围[10,90]；
C(100),D(500),M(1000)处理范围[100,900]；

确定好处理范围后，对数字的每一位进行处理，再叠加字符串就是结果。

思路 2

1. 找出所有不同的数字和罗马数字的对应组合
2. 用两个数组分别列举
3. 通过已知数字遍历values数组，相同等级的数字直接多次循环，字符串追加即可

思路 3

给定一个整数，将其转为罗马数字，输入数字在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

由罗马数字表示规则可知

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

// 例如：
      4:IV   9:IX
     40:XL  90:XC
    400:CD 900:CM

• 可知：数值大小 == 大的数字位-小的数字位

  • 由上述可以推出罗马数字每个进位值1-9的表示法：
  • 个位【1-9】：I、II、III、IV、V、VI、VII、VIII、IX （对应阿拉伯数字 X%10）
  • 十位【1-9】：X、XX、XXX、XL、L、LX、LXX、LXXX、XC （对应阿拉伯数字 (X%100)/10）
  • 百位【1-9】：C、CC、CCC、CD、D、DC、DCC、DCCC、CM （对应阿拉伯数字 (X%1000)/100）
  • 千位【1-9】：M、MM、MMM （对应阿拉伯数字 X/1000）

• 由以上可知一个阿拉伯数字 => 罗马数字

• num => num/1000 + (num%1000)/100 +(num%100)/10 + num%10

代码

JavaScript 实现

/**
 * @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
 * @param {number} num
 * @return {string}
 */
var intToRoman = function(num) {
  let bit={}
  bit[0]=['I','V','X']
  bit[1]=['X','L','C']
  bit[2]=['C','D','M']
  bit[3]=['M']
  function toRoman(n,cur){
    if(n===0)return ''
    if(n<4)return cur[0].repeat(n)
    if(n===4)return cur[0]+cur[1]
    if(n<9)return cur[1]+cur[0].repeat(n-5)
    if(n===9)return cur[0]+cur[2]
  }
  let str=num+''
  let len=str.length
  let res=''
  let N=num
  for(let i=len;i>=1;i--){
    let curMod=Math.pow(10,i-1)
    let n=Math.floor(N/curMod)
    N %=curMod
    res+=toRoman(n,bit[i-1])
  }
  return res
};

/**
作者：Alexer-660
链接：https://leetcode-cn.com/problems/integer-to-roman/solution/12-zheng-shu-zhuan-luo-ma-shu-zi-by-alexer-660/
 * @param {number} num
 * @return {string}
 */
var intToRoman = function(num) {
    var Q = ["", "M", "MM", "MMM"];
    var B = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"];
    var S = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"];
    var G = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"];
    return Q[Math.floor(num/1000)] + B[Math.floor((num%1000)/100)] + S[Math.floor((num%100)/10)] + G[num%10];
};

/**
 作者：iamapig120
链接：https://leetcode-cn.com/problems/integer-to-roman/solution/cyu-yan-js-cong-di-wei-kai-shi-an-wei-qu-zhi-cha-b/
 */
var intToRoman = function(num) {
  const romanCharFive = ['V', 'L', 'D']
  const romanCharOne = ['I', 'X', 'C', 'M']
  let pointer = 0
  let result = ''
  while (num > 0) {
    const digits = num % 10
    switch (digits) {
      case 1:
      case 2:
      case 3:
        result = `${romanCharOne[pointer].padStart(
          digits,
          romanCharOne[pointer]
        )}${result}`
        break
      case 4:
        result = `${romanCharOne[pointer]}${romanCharFive[pointer]}${result}`
        break
      case 5:
        result = `${romanCharFive[pointer]}${result}`
        break
      case 6:
      case 7:
      case 8:
        result = `${romanCharFive[pointer]}${romanCharOne[pointer].padStart(
          digits - 5,
          romanCharOne[pointer]
        )}${result}`
        break
      case 9:
        result = `${romanCharOne[pointer]}${romanCharOne[pointer + 1]}${result}`
        break
    }
    // JS 中的 number 为 64 位浮点数，此处位运算用于取整
    // parseInt(3.14,10) 和 3.14 >> 0 返回值是一致的
    num = (num / 10) >> 0
    pointer++
  }
  return result
}

C++ 实现

//  作者：z1m
// 链接：https://leetcode-cn.com/problems/integer-to-roman/solution/tan-xin-ha-xi-biao-tu-jie-by-ml-zimingmeng/
string intToRoman(int num) {
    string table[4][10] = { // 1~9
                           {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"},
                            // 10~90
                           {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"},
                            // 100~900
                           {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"},
                            // 1000~3000
                           {"", "M", "MM", "MMM"}
                          };
    string result;
    int count = 0;
    while(num > 0){
        int temp = num % 10;
        result = table[count][temp] + result;
        num /= 10;
        count++;
    }
    return result;
}

// 作者：pinku-2
// 链接：https://leetcode-cn.com/problems/integer-to-roman/solution/zheng-shu-zhuan-luo-ma-shu-zi-cshi-xian-liang-chon/
#include <string>
#include <iostream>
#include <vector>
using namespace std;

class Solution
{
public:
    string intToRoman(int num)
    {
        string result;
        vector<string> tmpVec1 = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
        vector<string> tmpVec2 = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
        vector<string> tmpVec3 = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
        vector<string> tmpVec4 = {"", "M", "MM", "MMM"};
        vector<vector<string>> store = {tmpVec1, tmpVec2, tmpVec3, tmpVec4};
        result.append(store[3][num / 1000 % 10]);
        result.append(store[2][num / 100 % 10]);
        result.append(store[1][num / 10 % 10]);
        result.append(store[0][num % 10]);
        return result;
    }
};

Python 实现

# 作者：liweiwei1419
# 链接：https://leetcode-cn.com/problems/integer-to-roman/solution/tan-xin-suan-fa-by-liweiwei1419/
class Solution:
    def intToRoman(self, num: int) -> str:
        # 把阿拉伯数字与罗马数字可能出现的所有情况和对应关系，放在两个数组中
        # 并且按照阿拉伯数字的大小降序排列，这是贪心选择思想
        nums = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
        romans = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]

        index = 0
        res = ''
        while index < 13:
            # 注意：这里是等于号，表示尽量使用大的"面值"
            while num >= nums[index]:
                res += romans[index]
                num -= nums[index]
            index += 1
        return res

# 作者：z1m
# 链接：https://leetcode-cn.com/problems/integer-to-roman/solution/tan-xin-ha-xi-biao-tu-jie-by-ml-zimingmeng/
class Solution:
    def intToRoman(self, num: int) -> str:
        # 使用哈希表，按照从大到小顺序排列
        hashmap = {1000:'M', 900:'CM', 500:'D', 400:'CD', 100:'C', 90:'XC', 50:'L', 40:'XL', 10:'X', 9:'IX', 5:'V', 4:'IV', 1:'I'}
        res = ''
        for key in hashmap:
            if num // key != 0:
                count = num // key  # 比如输入4000，count 为 4
                res += hashmap[key] * count
                num %= key
        return res

# 作者：z1m
# 链接：https://leetcode-cn.com/problems/integer-to-roman/solution/tan-xin-ha-xi-biao-tu-jie-by-ml-zimingmeng/

class Solution:
    def intToRoman(self, num: int) -> str:
        # 使用哈希表，按照从大到小顺序排列
        hashmap = {1000:'M', 900:'CM', 500:'D', 400:'CD', 100:'C', 90:'XC', 50:'L', 40:'XL', 10:'X', 9:'IX', 5:'V', 4:'IV', 1:'I'}
        res = ''
        for key in hashmap:
            if num // key != 0:
                count = num // key  # 比如输入4000，count 为 4
                res += hashmap[key] * count
                num %= key
        return res

其他

• 原题leetcode链接：https://leetcode-cn.com/problems/integer-to-roman/
• 合作方：JavaScript中文网 – 全球极客挚爱的技术成长平台
• 说明：leetcode 题解 | 每日一题🔥 所有题目并非全部为本人解答，部分为在复习学习中整理提取其他解题作者的优秀笔记，便于大家学习共同进步，如有侵权，请联系删除。