问题描述
将一个整数转换为罗马数字。罗马数字是由特定的符号组合而成的，每个符号代表不同的数值。以下是基本的罗马数字符号及其对应的值：
- I = 1
- V = 5
- X = 10
- L = 50
- C = 100
- D = 500
- M = 1000
罗马数字的规则如下：
- 罗马数字是从小数位值的高位到低位添加的。
- 如果一个值不是以4或9开头，选择可以从输入中减去的最大值的符号，将该符号附加到结果，减去其值，然后将其余部分转换为罗马数字。
- 如果一个值以4或9开头，使用减法形式，例如4是5减1（IV），9是10减1（IX）。
- 只有10的次方（I, X, C, M）可以连续附加3次，而5（V）、50（L）和500（D）不能多次附加。如果需要附加4次，请使用减法形式。
给定一个整数，编写一个函数将其转换为罗马数字。
示例
示例 1
输入：num = 3749
输出："MMMDCCXLIX"
解释：
- 3000 = MMM（1000 * 3）
- 700 = DCC（500 * 1 + 100 * 2）
- 40 = XL（50 - 10）
- 9 = IX（10 - 1）
示例 2
输入：num = 58
输出："LVIII"
解释：
- 50 = L
- 8 = VIII（5 + 1 + 1 + 1）
示例 3
输入：num = 1994
输出："MCMXCIV"
解释：
- 1000 = M
- 900 = CM（1000 - 100）
- 90 = XC（100 - 10）
- 4 = IV（5 - 1）
提示
1 <= num <= 3999
题解
算法思路
我们可以通过迭代的方式，从最大的罗马数字开始，逐步减去对应的数值，直到剩余的数值小于当前的罗马数字值。这样，我们可以构建出整个罗马数字字符串。
代码实现
java
class Solution {public String intToRoman(int num) {int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};String[] roman = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};StringBuilder sb = new StringBuilder();for (int i = 0; num > 0; i++) {while (num >= values[i]) {num -= values[i];sb.append(roman[i]);}}return sb.toString();}
}算法分析
- 时间复杂度：O(1)，因为罗马数字的符号数量是有限的，所以循环的次数是固定的。
- 空间复杂度：O(1)，除了输入和输出，我们只需要一个固定大小的数组和字符串构建器。
