12-整数转罗马数字(Integer to Roman)

原文链接: https://leetcode-cn.com/problems/integer-to-roman

英文原文

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.

Given an integer, convert it to a roman numeral.

Example 1:

Input: num = 3
Output: "III"

Example 2:

Input: num = 4
Output: "IV"

Example 3:

Input: num = 9
Output: "IX"

Example 4:

Input: num = 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.

Example 5:

Input: num = 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Constraints:

1 <= num <= 3999

中文题目

罗马数字包含以下七种字符： 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:

输入: num = 3
输出: "III"

示例 2:

输入: num = 4
输出: "IV"

示例 3:

输入: num = 9
输出: "IX"

示例 4:

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

示例 5:

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

提示：

1 <= num <= 3999

通过代码

高赞题解

这道题使用贪心算法的直觉来源是：尽可能优先使用较大数值对应的字符，最后转换得到的罗马数字的字符个数更少，字符更少更方便交流使用，这应该是设计罗马数字的人们的初衷。但是这 其中有一个规则，题目中没有强调，为了避免冲淡主题，我们放在后面说。

方法：贪心算法

生活中的经验

在以前还使用现金购物的时候，找零钱的时候一般商家会尽量选择面值大的纸币（硬币）给顾客，这样才会使得给顾客的纸币（硬币）张数最少，让顾客点钱的时候更方便。

题意分析

本题中，首先给出「罗马数字」与「阿拉伯数字」的对应关系：

罗马数字	阿拉伯数字
`I`	$1$
`V`	$5$
`X`	$10$
`L`	$50$
`C`	$100$
`D`	$500$
`M`	$1000$

先研究几个例子：

阿拉伯数字	转换规则	罗马数字
$1$	直接看表	`I`
$2$	$2 = 1 + 1$，相同数字简单叠加	`II`
$3$	$3 = 1 + 1 + 1$，相同数字简单叠加	`III`
$4$	题目中说的特例：不能写成 $4 = 1 + 1 + 1 + 1$，$4$ 应该看做 $4 = 5 - 1$	`IV`
$5$	直接看表	`V`
$6$	$6 = 5 + 1$，大数字在前，小数字在后	`VI`
$7$	$7 = 5 + 1 + 1$，大数字在前，小数字在后，相同数字简单叠加	`VII`
$8$	$8 = 5 + 1 + 1 + 1$，大数字在前，小数字在后，相同数字简单叠加	`VIII`
$9$	题目中说的特例：不能写成 $9 = 5 + 1 + 1 + 1 + 1$，$9$ 应该看做 $9 = 10 - 1$	`IX`
$10$	直接看表	`X`

发现规律

可以发现规律：数字 $1$、$5$、$10$、$50$、$100$、$500$、$1000$ 是分水岭，转换的时候默认使用加法，如果一个字符超过 $3$ 次重复使用，就改成减法，这样就可以用两个字符表示一个罗马数字（数量更少），所以 $4$ 应该看成 $5 - 1$，即 IV。

其实题目中也强调了「做减法的特例」：出现 $4$、$9$、$40$、$90$、$400$、$900$ （$4000$、$9000$ 不讨论了，题目最后说测试用例不包含）。

我们把 所有的 组成罗马数字的最基本的字符组成单元罗列如下，并且按照对应阿拉伯数字降序排序。

罗马数字	阿拉伯数字
`M`	$1000$
`CM`	$900$
`D`	$500$
`CD`	$400$
`C`	$100$
`XC`	$90$
`L`	$50$
`XL`	$40$
`X`	$10$
`IX`	$9$
`V`	$5$
`IV`	$4$
`I`	$1$

设计贪心算法如下：每一步都使用当前对应阿拉伯数字较大的罗马数字作为加法因子，最后得到罗马数字表示就是长度最少的。

贪心算法的证明：

我们先说 题目中隐含的条件，这是我在调试的时候发现的：$900$（CM）、$400$（CD），$90$、$40$、$9$、$4$ 这些数字只允许出现一次，即：$1800$ 不能对应 CMCM，应该对应 MDCCC，也就是说，如果能拆分 $4$、$9$、$40$、$90$、$400$、$900$ 作为加法因子，它们只能出现一次。

剩下的可以出现多次的字符有 $1$、$5$、$10$、$50$、$100$、$500$、$1000$，它们呈明显的倍数关系。例如 $1000 = 500 \times 2$，能用 $1000$ 就不应该用 $2$ 个 $500$。贪心选择可以保证使用的字符在这样的规则下字符最少。

总结

题目中阿拉伯数组转换成罗马数字的规则如下：

$4$、$9$、$40$、$90$、$400$、$900$ 对应的罗马数字字符只出现一次；
其余字符可以连续出现的次数不超过 $3$ 次。

按照贪心的方式，尽可能先选出大的数字进行转换。

参考代码：

[]
public class Solution {

    public String intToRoman(int num) {
        // 把阿拉伯数字与罗马数字可能出现的所有情况和对应关系，放在两个数组中，并且按照阿拉伯数字的大小降序排列
        int[] nums = {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 stringBuilder = new StringBuilder();
        int index = 0;
        while (index < 13) {
            // 特别注意：这里是等号
            while (num >= nums[index]) {
                stringBuilder.append(romans[index]);
                num -= nums[index];
            }
            index++;
        }
        return stringBuilder.toString();
    }
}

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

复杂度分析：

时间复杂度：$O(\log N)$，这里讨论的是一般情况，忽略题目中测试数据范围的限制。输入整数的位数，决定了循环的次数，所以复杂度为 $O(\log_{10}N)$；
空间复杂度：$O(\log N)$，阿拉伯数字与罗马数字的对应关系也取决于输入数字的位数。

补充说明：

一开始我把这个问题想复杂了，觉得需要很复杂的数学证明。直到我把 $1800$ 作为测试数据，后台返回 "MDCCC"，发现带 $4$ 和 $9$ 的都是「至多只能使用一次」的字符组合；
事实上，有一个非常经典的贪心算法的问题，叫「找零钱问题」，就是在找零钱的时候，优先使用大的面值的纸币（或硬币）找给顾客，这样顾客得到的纸币的张数最少。这种贪心选择性质可以成立，是与可以使用的纸币（硬币）的面值有关。例如：
- 可选纸币（硬币）面值列表为 [1, 5, 10]，要找给顾客 $15$ 元时，给 $10$ 和 $5$ 是张数最少的。
- 可选纸币（硬币）面值列表为 [1, 5, 11]，要找给顾客 $15$ 元时，就不能用贪心算法，$15 = 11 + 1 + 1 + 1 + 1$ 用了 $5$ 张，最优解为 $15 = 5 + 5 + 5$ 用了 $3$ 张。

结论：可以贪心与可选硬币（纸币）的面值有关。

（本题解于 2020 年 11 月 19 日更新）

统计信息

通过次数	提交次数	AC比率
243558	366873	66.4%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
罗马数字转整数	简单
整数转换英文表示	困难

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途