Integer to Roman

12. Integer to Roman

分析


1	2	3	4	5	6	7	8	9
I	II	III	IV	V	VI	VII	VIII	IX
10	20	30	40	50	60	70	80	90
X	XX	XXX	XL	L	LX	LXX	LXXX	XL
100	200	300	400	500	600	700	800	900
C	CC	CCC	CD	D	DC	DCC	DCCC	CM
1000	2000	3000
M	MM	MMM

1234 转换成罗马数字是 MCCXXXIV，也就是从千位到个位依次拼接，用代码将过程模拟出来即可

分解数值：
- 定义一个从大到小排列的数值数组 values，以及对应的罗马数字字符串数组 romans
- 数值包括基本符号（如 1000, 500）及特殊减法组合（如 900, 400）
逐步转换：
- 遍历数值数组 values，对于每个值，检查当前数字 num 是否大于等于该值
- 若是，则从 num 中减去该值，同时将对应的罗马数字添加到结果字符串中
- 重复上述步骤，直到 num 为 0
输出结果：
- 返回拼接的罗马数字字符串

时间复杂度

常数时间复杂度 O(1)

空间复杂度

常数空间复杂度 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class Solution
{
public:
    string intToRoman(int num)
    {
        // 定义数值和对应的罗马数字
        std::vector<int> values =
        {
            1000, 900, 500, 400, 100,
            90, 50, 40, 10, 9, 5, 4, 1
        };

        std::vector<std::string> romans =
        {
            "M", "CM", "D", "CD", "C",
            "XC", "L", "XL", "X", "IX", "V", "IV", "I"
        };

        std::string res;
        // 遍历数值数组
        for (int i = 0; i < values.size(); ++i)
        {
            // 减去当前值，拼接对应罗马数字
            while (num >= values[i])
            {
                num -= values[i];
                res += romans[i];
            }
        }
        return res;
    }
};