☆打卡算法☆LeetCode 12、整数转罗马数字 算法解析
☆打卡算法☆LeetCode 12、整数转罗马数字 算法解析
一、题目
1、算法题目
“将输入的整数转化成罗马数字。”
题目链接： 来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/integer-to-roman/
2、题目描述
罗马数字包含以下七种字符： 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 = 48
输出："XLVIII"
解析: XL = 40 , V = 5 , III = 3示例 3：
输入：num = 4994
输出："MIVCMXCIV"
解析：MIV = 4000 , CM = 900 , XC = 90 , IV = 4二、解题
1、思路分析
罗马数字由7个符号组成，每个符号对应一个具体的数值，根据减法规则给出了额外的6个复合符号，一共13个独特符号，如下图所示：
这道题的关键是整数转成罗马数字的时候选择尽可能大的符号值，比如140，最大可以选择符号值C = 100，然后 40 选择最大符号值 XL = 40。
2、代码实现
暴力解法：
这个思路相对比较简单，因为整数转罗马数字，每个位数上的数字都可以单独处理，使用模运算和触发运算，可以得到每个位上的数字，然后跟罗马数字中的数字对应起来组合即可。
public class Solution
{
public string IntToRoman(int num)
{
string[] M = { "", "M", "MM", "MMM" }; // 1000，2000，3000
string[] C = { "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" }; // 100~900
string[] X = { "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" }; // 10~90
string[] I = { "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" }; // 1~9
return M[num / 1000] + C[(num % 1000) / 100] + X[(num % 100) / 10] + I[num % 10];
}
}
贪心算法
贪心法则：每次尽量使用最大的数来表示，比如2118这个数，每次尽量选择最大的数来表示，那么就是 2000 ，100 ，10 ，8，会得到正确结果： MMCXVIII。
public class Solution
{
public string IntToRoman(int num)
{
int[] values = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
string[] rom = { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };
StringBuilder sb = new StringBuilder();
for (int i = 0; i < values.Length; i++)
{
while (num >= values[i])
{
sb.Append(rom[i]);
num -= values[i];
}
}
return sb.ToString();
}
}3、时间复杂度
时间复杂度 ： O(1)
计算量与输入数字的大小无关。
空间复杂度： O(1)
计算量与输入数字的大小无关。
三、总结
这道题使用了两种解法去解题，当然还有更多的解题方法，要多思考。
贪心算法的贪心法则：每次尽量使用最大的数来表示，跟整数转罗马数字去较大数的原则类似，字符更少更方便交流使用，这应该也是设计罗马数字的人们的初衷。
腾讯云开发者
