面试经典算法150题系列-整数转罗马数字

发布于:2024-08-15 ⋅ 阅读:(74) ⋅ 点赞:(0)

序言:之前有写过罗马数字转整数掌握了吗?写完这题想想二者思路有什么不一样呢?

整数转罗马数字

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

符号
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 的次方(IXCM)最多可以连续附加 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. 定义罗马数字和数值映射:首先,定义两个数组,一个用于存储罗马数字符号(如"I", "V", "X"等),另一个用于存储它们对应的数值(如1, 5, 10等)。

  2. 初始化结果:创建一个空的字符串或字符串构建器(如Java中的StringBuilder),用于存储最终的罗马数字表示。

  3. 从最大数值开始迭代:使用一个循环,从罗马数字的最大数值(在这个例子中是1000,对应"M")开始,向下迭代到最小的数值。

  4. 检查数值:在每次迭代中,检查输入的整数num是否大于或等于当前的罗马数字数值。

  5. 减值并添加符号:如果num大于或等于当前的罗马数字数值,从num中减去这个数值,并在结果字符串中添加对应的罗马数字符号。

  6. 更新num:重复步骤4和5,直到num小于当前的罗马数字数值。

  7. 移动到下一个罗马数字:当num小于当前的数值时,移动到下一个较小的罗马数字数值,并重复步骤4至6。

  8. 结束条件:当num减少到0时,结束循环。

  9. 返回结果:返回构建的罗马数字字符串。

实现代码:

 public  String intToRoman(int num) {
        // 定义罗马数字与数值的映射关系
        String[] romanSymbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};

        StringBuilder roman = new StringBuilder();
        // 从最大的罗马数字开始
        for (int i = 0; num > 0; i++) {
            // 减去相应的罗马数字数值,并添加符号到结果字符串
            while (num >= values[i]) {
                num -= values[i];
                roman.append(romanSymbols[i]);
            }
        }
        return roman.toString();
    }

思路实例模拟

让我们用实例模拟上述过程,将数字 1994 转换为罗马数字。以下是逐步模拟:

  1. 定义罗马数字和数值映射

    • 罗马数字符号:["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
    • 对应数值:[1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
  2. 初始化结果

    • 结果字符串:roman = ""(空字符串)
  3. 从最大数值开始迭代

    • 从数值1000开始。
  4. 检查数值

    • 1994 >= 1000,满足条件。
  5. 减值并添加符号

    • 从1994中减去1000,得到994。
    • 结果字符串变为:roman = "M"
  6. 更新num

    • num现在是994。
  7. 移动到下一个罗马数字

    • 移动到下一个较小的数值,即900。
  8. 重复步骤4至7

    • 994 >= 900,满足条件。
    • 减去900,得到94。
    • 结果字符串变为:roman = "MCM"
  9. 继续迭代

    • 94 >= 50(下一个数值),不满足条件,移动到下一个。
    • 94 >= 40,满足条件。
    • 减去40,得到54。
    • 结果字符串变为:roman = "MCMXL"
  10. 处理剩余数值

    • 54 >= 10,满足条件。
    • 减去10,得到44。
    • 结果字符串变为:roman = "MCMXLX"
    • 44 >= 5,满足条件。
    • 减去5,得到39。
    • 结果字符串变为:roman = "MCMXLIX"
  11. 结束条件

    • 39 < 40,不满足条件,移动到下一个数值10。
    • 39 >= 10,满足条件。
    • 减去10,得到29。
    • 结果字符串变为:roman = "MCMXLIX"(这里看起来没有变化,但实际上我们已经完成了所有的减法)。
  12. 最后处理

    • 29 >= 10,不满足条件,移动到下一个数值。
    • 29 >= 5,满足条件。
    • 减去5,得到24。
    • 结果字符串变为:roman = "MCMXLIXV"
  13. 最终剩余数值处理

    • 24 >= 1,满足条件。
    • 连续减去24个1,得到0。
    • 结果字符串变为:roman = "MCMXLIXVI"
  14. 返回结果

    • 所有数值已经处理完毕,返回结果字符串:"MCMXLIXVI"

这个模拟过程展示了如何逐步将整数转换为罗马数字,遵循了上述算法的核心思路。实际编程实现时,可以使用数组或列表来存储罗马数字和它们的数值,并使用循环和条件语句来构建最终的罗马数字字符串。