JAVA练习369- 整数转罗马数字
题目概览
七个不同的符号代表罗马数字，其值如下：
| 符号 | 值 |
|---|---|
| I | 1 |
| V | 5 |
| X | 10 |
| L | 50 |
| C | 100 |
| D | 500 |
| M | 1000 |
罗马数字是通过添加从最高到最低的小数位值的转换而形成的。将小数位值转换为罗马数字有以下规则：
- 如果该值不是以 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）
解题分析
方法一：模拟（贪心算法）
这是最直观和常用的方法。核心思想是：每次都尽可能使用当前最大的罗马数字符号来表示剩余的数字。
算法步骤：
- 预先定义两个数组：
values[]：按从大到小的顺序存储所有可能的“数字值”，包括常规符号（如 1000, 500, 100...）和特殊的减法形式（如 900, 400, 90...）。symbols[]：存储与values[]一一对应的罗马数字字符串。
- 初始化一个结果字符串（如
StringBuilder）。 - 从最大的数字值（
values[0]）开始遍历数组：- 如果当前数字
num大于等于values[i]，则将对应的symbols[i]追加到结果中，并从num中减去values[i]。 - 重复此步骤，直到
num小于values[i]，然后移动到下一个更小的值。
- 如果当前数字
- 当
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）：
- num=3749 >= 1000，追加 “M”，num=2749。
- num=2749 >= 1000，追加 “M”，num=1749。
- num=1749 >= 1000，追加 “M”，num=749。此时已得到 “MMM”。
- num=749 < 900 但 >= 500，追加 “D”，num=249。得到 “MMMD”。
- num=249 < 400 但 >= 100，追加 “C”，num=149。得到 “MMMDC”。
- num=149 >= 100，追加 “C”，num=49。得到 “MMMDCC”。
- num=49 < 90 但 >= 40，追加 “XL”，num=9。得到 “MMMDCCXL”。
- num=9 >= 9，追加 “IX”，num=0。得到最终结果 “MMMDCCXLIX”。
方法二：硬编码
这种方法利用了罗马数字表示法的确定性：对于给定的整数（1 ≤ num ≤ 3999），其千位、百位、十位、个位上的数字是确定的，且每个数位上的数字（0-9）对应的罗马数字组合也是固定的。因此，我们可以预先为每个数位上的所有可能数字（0-9）编码好对应的罗马数字字符串，然后通过简单的数学运算取出每一位的数字，拼接对应的字符串即可。
核心思路：
- 数位分离：将输入整数
num分解为千位、百位、十位、个位四个数字。 - 查表映射：为每个数位预先定义一个长度为 10 的字符串数组，下标 0-9 分别对应数字 0-9 在该数位上的罗马数字表示（其中 0 对应空字符串）。
- 拼接结果：将四个数位对应的罗马数字字符串按顺序（千位、百位、十位、个位）拼接起来，即为最终结果。
算法步骤：
- 定义四个字符串数组：
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"）。
- 通过整数除法和取余运算获取每一位的数字：
- 千位：
num / 1000 - 百位：
(num % 1000) / 100或num % 1000 / 100 - 十位：
(num % 100) / 10或num % 100 / 10 - 个位：
num % 10
- 千位：
- 根据每一位的数字作为下标，从对应的数组中取出罗马数字字符串，依次拼接到结果中。
- 返回拼接后的字符串。
为什么可行？
因为罗马数字的表示是按位独立的。千位只由 '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）：
- 千位：
3749 / 1000 = 3→thousands[3] = "MMM" - 百位：
3749 % 1000 = 749，749 / 100 = 7→hundreds[7] = "DCC"（注意：700 是 DCC，不是 CC...） - 十位：
3749 % 100 = 49，49 / 10 = 4→tens[4] = "XL" - 个位：
3749 % 10 = 9→ones[9] = "IX" - 拼接：
"MMM" + "DCC" + "XL" + "IX" = "MMMDCCXLIX"
方法对比：
- 贪心模拟法更通用，体现了罗马数字的构造规则，易于理解和扩展。
- 硬编码法更高效、更直接，利用了问题范围的有限性（num ≤ 3999），代码极其简洁，在实际编码竞赛或面试中可能是更优的选择。