题目概览

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

罗马数字是通过添加从最高到最低的小数位值的转换而形成的。将小数位值转换为罗马数字有以下规则：

• 如果该值不是以 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) 注意：49 不是 50 (L) 减 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

来源：12. 整数转罗马数字 - 力扣（LeetCode）

解题分析

方法一：模拟（贪心算法）

这是最直观和常用的方法。核心思想是：每次都尽可能使用当前最大的罗马数字符号来表示剩余的数字。

算法步骤：

1. 预先定义两个数组：
   • values[]：按从大到小的顺序存储所有可能的“数字值”，包括常规符号（如 1000, 500, 100...）和特殊的减法形式（如 900, 400, 90...）。
   • symbols[]：存储与values[]一一对应的罗马数字字符串。
2. 初始化一个结果字符串（如StringBuilder）。
3. 从最大的数字值（values[0]）开始遍历数组：
   • 如果当前数字num大于等于values[i]，则将对应的symbols[i]追加到结果中，并从num中减去values[i]。
   • 重复此步骤，直到num小于values[i]，然后移动到下一个更小的值。
4. 当num被减至 0 时，转换完成，返回结果字符串。

为什么可行？

因为罗马数字的表示规则本质上就是“贪心”的：对于任何给定的数字，总是优先使用能表示它的最大符号。预定义的数组已经包含了所有必要的减法形式（如 IV, IX, XL 等），确保了算法能正确处理 4 和 9 相关的边界情况。

复杂度分析：

• 时间复杂度：O(1)。虽然有一个循环，但循环次数是固定的（数组长度 13），与输入num的大小无关。在最坏情况下（如 num=1），内层 while 循环可能执行多次，但总操作次数仍有一个很小的常数上界。
• 空间复杂度：O(1)。只使用了固定大小的数组和结果字符串。

class Solution { // 按从大到小的顺序定义所有可能的“值-符号”对 int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}; String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}; public String intToRoman(int num) { StringBuilder roman = new StringBuilder(); // 遍历每一个值 for (int i = 0; i < values.length; ++i) { // 当剩余数字大于等于当前值时，就使用对应的符号 while (num >= values[i]) { roman.append(symbols[i]); num -= values[i]; } // 如果数字已经减到0，可以提前结束（非必需优化） if (num == 0) { break; } } return roman.toString(); } }

代码说明：

• 使用StringBuilder来高效构建结果字符串。
• 内层使用while循环，确保同一个符号可以连续使用多次（例如，3000 对应三个 “M”）。
• 数组包含了所有必要的减法形式（如 900 对应 “CM”），因此算法能自动处理 4、9、40、90、400、900 这些情况。
• 提前判断num == 0可以提前退出循环，是一个小的优化。

示例推演（num = 3749）：

1. num=3749 >= 1000，追加 “M”，num=2749。
2. num=2749 >= 1000，追加 “M”，num=1749。
3. num=1749 >= 1000，追加 “M”，num=749。此时已得到 “MMM”。
4. num=749 < 900 但 >= 500，追加 “D”，num=249。得到 “MMMD”。
5. num=249 < 400 但 >= 100，追加 “C”，num=149。得到 “MMMDC”。
6. num=149 >= 100，追加 “C”，num=49。得到 “MMMDCC”。
7. num=49 < 90 但 >= 40，追加 “XL”，num=9。得到 “MMMDCCXL”。
8. num=9 >= 9，追加 “IX”，num=0。得到最终结果 “MMMDCCXLIX”。

方法二：硬编码

这种方法利用了罗马数字表示法的确定性：对于给定的整数（1 ≤ num ≤ 3999），其千位、百位、十位、个位上的数字是确定的，且每个数位上的数字（0-9）对应的罗马数字组合也是固定的。因此，我们可以预先为每个数位上的所有可能数字（0-9）编码好对应的罗马数字字符串，然后通过简单的数学运算取出每一位的数字，拼接对应的字符串即可。

核心思路：

1. 数位分离：将输入整数num分解为千位、百位、十位、个位四个数字。
2. 查表映射：为每个数位预先定义一个长度为 10 的字符串数组，下标 0-9 分别对应数字 0-9 在该数位上的罗马数字表示（其中 0 对应空字符串）。
3. 拼接结果：将四个数位对应的罗马数字字符串按顺序（千位、百位、十位、个位）拼接起来，即为最终结果。

算法步骤：

1. 定义四个字符串数组：
   • thousands[]：千位数字 0-3 对应的罗马数字（0 为空字符串，1 为 "M"，2 为 "MM"，3 为 "MMM"）。
   • hundreds[]：百位数字 0-9 对应的罗马数字（例如 0="", 1="C", 2="CC", 3="CCC", 4="CD", 5="D", 6="DC", 7="DCC", 8="DCCC", 9="CM"）。
   • tens[]：十位数字 0-9 对应的罗马数字（例如 0="", 1="X", 2="XX", 3="XXX", 4="XL", 5="L", 6="LX", 7="LXX", 8="LXXX", 9="XC"）。
   • ones[]：个位数字 0-9 对应的罗马数字（例如 0="", 1="I", 2="II", 3="III", 4="IV", 5="V", 6="VI", 7="VII", 8="VIII", 9="IX"）。
2. 通过整数除法和取余运算获取每一位的数字：
   • 千位：num / 1000
   • 百位：(num % 1000) / 100或num % 1000 / 100
   • 十位：(num % 100) / 10或num % 100 / 10
   • 个位：num % 10
3. 根据每一位的数字作为下标，从对应的数组中取出罗马数字字符串，依次拼接到结果中。
4. 返回拼接后的字符串。

为什么可行？

因为罗马数字的表示是按位独立的。千位只由 'M' 组成，百位由 'C', 'D', 'M' 的组合构成，十位由 'X', 'L', 'C' 的组合构成，个位由 'I', 'V', 'X' 的组合构成。每个数位上的数字 0-9 都有唯一确定的罗马数字表示（包括减法形式如 IV, IX, XL, XC, CD, CM），且不同数位之间的表示不会相互干扰。因此，预先编码所有可能性并查表拼接是完全正确的。

复杂度分析：

• 时间复杂度：O(1)。仅进行固定次数的数学运算（除法、取余）和字符串拼接操作，与输入大小无关。
• 空间复杂度：O(1)。使用了四个固定大小的数组（总长度 4×10=40）和一个结果字符串，均为常数空间。

class Solution { // 千位：0-3 对应空字符串、"M"、"MM"、"MMM" String[] thousands = {"", "M", "MM", "MMM"}; // 百位：0-9 对应的罗马数字 String[] hundreds = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"}; // 十位：0-9 对应的罗马数字 String[] tens = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"}; // 个位：0-9 对应的罗马数字 String[] ones = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"}; public String intToRoman(int num) { // 使用 StringBuffer 或 StringBuilder 进行高效拼接 StringBuffer roman = new StringBuffer(); // 获取千位数字并拼接对应字符串 roman.append(thousands[num / 1000]); // 获取百位数字并拼接对应字符串 roman.append(hundreds[num % 1000 / 100]); // 获取十位数字并拼接对应字符串 roman.append(tens[num % 100 / 10]); // 获取个位数字并拼接对应字符串 roman.append(ones[num % 10]); return roman.toString(); } }

代码说明：

• 数组定义清晰对应每个数位，注释说明了每个下标的含义。
• 使用StringBuffer（或StringBuilder）进行字符串拼接，效率高于直接使用+操作符。
• 通过简单的除法和取余运算获取每一位的数字，代码简洁且易于理解。
• 由于题目限制1 <= num <= 3999，千位数字范围是 0-3，因此thousands数组只需定义 4 个元素。

示例推演（num = 3749）：

1. 千位：3749 / 1000 = 3→thousands[3] = "MMM"
2. 百位：3749 % 1000 = 749，749 / 100 = 7→hundreds[7] = "DCC"（注意：700 是 DCC，不是 CC...）
3. 十位：3749 % 100 = 49，49 / 10 = 4→tens[4] = "XL"
4. 个位：3749 % 10 = 9→ones[9] = "IX"
5. 拼接："MMM" + "DCC" + "XL" + "IX" = "MMMDCCXLIX"

方法对比：

• 贪心模拟法更通用，体现了罗马数字的构造规则，易于理解和扩展。
• 硬编码法更高效、更直接，利用了问题范围的有限性（num ≤ 3999），代码极其简洁，在实际编码竞赛或面试中可能是更优的选择。