Medium

题目描述

七个不同的符号代表罗马数字，对应的值如下：

符号数值
I1
V5
X10
L50
C100
D500
M1000

罗马数字是通过从高位到低位附加十进制位值的转换来形成的。将十进制位值转换为罗马数字有以下规则：

  • 如果数值不是以 4 或 9 开头，选择可以从输入中减去的最大值的符号，将该符号附加到结果中，减去其值，并将余数转换为罗马数字。
  • 如果数值以 4 或 9 开头，使用减法形式，表示从后面的符号中减去一个符号，例如，4 是比 5 (V) 少 1 (I)：IV，9 是比 10 (X) 少 1 (I)：IX。只使用以下减法形式：4 (IV)、9 (IX)、40 (XL)、90 (XC)、400 (CD) 和 900 (CM)。
  • 只有 10 的幂次（I、X、C、M）可以连续附加最多 3 次来表示 10 的倍数。你不能多次附加 5 (V)、50 (L) 或 500 (D)。如果你需要附加一个符号 4 次，使用减法形式。

给定一个整数，将其转换为罗马数字。

示例 1：

输入：num = 3749
输出："MMMDCCXLIX"
解释：
3000 = MMM 即 1000 (M) + 1000 (M) + 1000 (M)
 700 = DCC 即 500 (D) + 100 (C) + 100 (C)
  40 = XL 即 50 (L) 减去 10 (X)
   9 = IX 即 10 (X) 减去 1 (I)

示例 2：

输入：num = 58
输出："LVIII"
解释：
50 = L
 8 = VIII

示例 3：

输入：num = 1994
输出："MCMXCIV"
解释：
1000 = M
 900 = CM
  90 = XC
   4 = IV

约束条件：

  • 1 <= num <= 3999

解题思路

解题思路

这道题的关键是理解罗马数字的构成规律。我们需要从最大的数值开始，逐步构建罗马数字字符串。

核心思路：

  1. 贪心策略：从大到小遍历所有可能的罗马数字组合（包括减法形式），每次选择不超过当前数值的最大组合。

  2. 预处理映射表：创建一个包含所有可能数值和对应罗马数字的映射表，包括特殊的减法形式（4, 9, 40, 90, 400, 900）。

  3. 构建过程：

    • 从最大值开始遍历映射表
    • 如果当前数值大于等于映射表中的值，就添加对应的罗马数字符号
    • 从数值中减去对应的值，继续处理剩余部分
    • 重复直到数值变为 0

算法步骤：

  1. 创建数值和罗马数字的对应数组，按降序排列
  2. 从最大值开始，计算当前数值可以包含多少个该罗马数字
  3. 将对应数量的罗马数字符号添加到结果中
  4. 更新剩余数值，继续处理下一个较小的罗马数字

这种方法的优势是代码简洁，逻辑清晰，时间复杂度为 O(1)，因为最多只需要遍历 13 个固定的数值。

代码实现

class Solution {
public:
    string intToRoman(int num) {
        vector<int> values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        vector<string> romans = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        
        string result = "";
        for (int i = 0; i < values.size(); i++) {
            while (num >= values[i]) {
                result += romans[i];
                num -= values[i];
            }
        }
        return result;
    }
};

class Solution:
    def intToRoman(self, num: int) -> str:
        values = [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"]
        
        result = ""
        for i in range(len(values)):
            while num >= values[i]:
                result += romans[i]
                num -= values[i]
        return result

public class Solution {
    public string IntToRoman(int num) {
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        string[] romans = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < values.Length; i++) {
            while (num >= values[i]) {
                result.Append(romans[i]);
                num -= values[i];
            }
        }
        return result.ToString();
    }
}

var intToRoman = function(num) {
    const values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
    const romans = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"];
    
    let result = "";
    for (let i = 0; i < values.length; i++) {
        while (num >= values[i]) {
            result += romans[i];
            num -= values[i];
        }
    }
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(1)最多遍历 13 个固定的罗马数字组合，每个数字最多重复 3-4 次
空间复杂度O(1)使用固定大小的数组存储映射关系，额外空间为常数级别

相关题目