12.整数转罗马数字

LeetCode LeetCode 哈希表 数学 字符串
发布时间 :
字数:1.9k 阅读 : 评论:
  1. 12.整数转罗马数字
    1. 12.1 题目
    2. 12.2 题解
      1. 贪心算法映射数组按规则模拟拼接
      2. 硬编码
    3. 12.3 代码
    4. 12.4 运行结果

12.整数转罗马数字

12.1 题目

罗马数字包含以下七种字符：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 = 4
    • 输出: "IV"

  • 示例 3:

    • 输入: num = 9
    • 输出: "IX"

  • 示例 4:

    • 输入: num = 58
    • 输出: "LVIII"
    • 解释: L = 50, V = 5, III = 3.

  • 示例 5:

    • 输入: num = 1994
    • 输出: "MCMXCIV"
    • 解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示：

  • 1 <= num <= 3999

12.2 题解

贪心算法映射数组按规则模拟拼接

// 方法一：贪心算法映射数组按规则模拟拼接
// 将整数转换为罗马数字，使用贪心算法逐个匹配对应的罗马数字字符
static string IntToRoman1(int num)
{
    // 定义罗马数字字符和对应数值的映射
    string[] romanChars = { "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 用于构建最终的罗马数字字符串
    StringBuilder stringBuilder = new StringBuilder();

    // 当 num 大于0时，继续循环
    while (num > 0)
    {
        // 遍历所有的值，从最大值开始
        for (int i = 0; i < values.Length; i++)
        {
            // 如果当前 num 大于或等于当前值
            if (num >= values[i])
            {
                // 添加对应的罗马数字字符到 StringBuilder 中
                stringBuilder.Append(romanChars[i]);
                // 从 num 中减去当前值
                num -= values[i];
                // 跳出当前 for 循环，重新开始 while 循环
                break;
            }
        }
    }

    // 返回最终的罗马数字字符串
    return stringBuilder.ToString();
}

硬编码

// 方法二：硬编码
// 把对应位的字符存到字典，丢上去
static string IntToRoman2(int num)
{
    // 定义罗马数字字符
    string[] thousands = { "", "M", "MM", "MMM" };
    string[] hundreds = { "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" };
    string[] tens = { "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" };
    string[] ones = { "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" };

    // 构建罗马数字字符串
    string result = thousands[num / 1000] + hundreds[(num % 1000) / 100] + tens[(num % 100) / 10] + ones[num % 10];

    return result;
}

12.3 代码

using System;
using System.Collections.Generic;
using System.Text;

class Program
{
    static void Main()
    {
        #region 题目

        // 罗马数字包含以下七种字符： 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 = 4
        // 输出: "IV"

        // 示例 3:
        // 输入: num = 9
        // 输出: "IX"

        // 示例 4:
        // 输入: num = 58
        // 输出: "LVIII"
        // 解释: L = 50, V = 5, III = 3.

        // 示例 5:
        // 输入: num = 1994
        // 输出: "MCMXCIV"
        // 解释: M = 1000, CM = 900, XC = 90, IV = 4.

        // 提示：
        // 1 <= num <= 3999

        #endregion

        #region 测试

        // 示例 1
        int num1 = 3;
        string result1 = IntToRoman1(num1);
        Console.WriteLine($"示例1 方法1 输出：{result1}");
        string result1_2 = IntToRoman2(num1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        int num2 = 4;
        string result2 = IntToRoman1(num2);
        Console.WriteLine($"示例2 方法1 输出：{result2}");
        string result2_2 = IntToRoman2(num2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        // 示例 3
        int num3 = 9;
        string result3 = IntToRoman1(num3);
        Console.WriteLine($"示例3 方法1 输出：{result3}");
        string result3_2 = IntToRoman2(num3);
        Console.WriteLine($"示例3 方法2 输出：{result3_2}");

        // 示例 4
        int num4 = 58;
        string result4 = IntToRoman1(num4);
        Console.WriteLine($"示例4 方法1 输出：{result4}");
        string result4_2 = IntToRoman2(num4);
        Console.WriteLine($"示例4 方法2 输出：{result4_2}");

        // 示例 5
        int num5 = 1994;
        string result5 = IntToRoman1(num5);
        Console.WriteLine($"示例5 方法1 输出：{result5}");
        string result5_2 = IntToRoman2(num5);
        Console.WriteLine($"示例5 方法2 输出：{result5_2}");

        #endregion
    }

    #region 答案

    // 方法一：贪心算法映射数组按规则模拟拼接
    // 将整数转换为罗马数字，使用贪心算法逐个匹配对应的罗马数字字符
    static string IntToRoman1(int num)
    {
        // 定义罗马数字字符和对应数值的映射
        string[] romanChars = { "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 用于构建最终的罗马数字字符串
        StringBuilder stringBuilder = new StringBuilder();

        // 当 num 大于0时，继续循环
        while (num > 0)
        {
            // 遍历所有的值，从最大值开始
            for (int i = 0; i < values.Length; i++)
            {
                // 如果当前 num 大于或等于当前值
                if (num >= values[i])
                {
                    // 添加对应的罗马数字字符到 StringBuilder 中
                    stringBuilder.Append(romanChars[i]);
                    // 从 num 中减去当前值
                    num -= values[i];
                    // 跳出当前 for 循环，重新开始 while 循环
                    break;
                }
            }
        }

        // 返回最终的罗马数字字符串
        return stringBuilder.ToString();
    }


    // 方法二：硬编码
    // 把对应位的字符存到字典，丢上去
    static string IntToRoman2(int num)
    {
        // 定义罗马数字字符
        string[] thousands = { "", "M", "MM", "MMM" };
        string[] hundreds = { "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" };
        string[] tens = { "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" };
        string[] ones = { "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" };

        // 构建罗马数字字符串
        string result = thousands[num / 1000] + hundreds[(num % 1000) / 100] + tens[(num % 100) / 10] + ones[num % 10];

        return result;
    }

    #endregion
}

12.4 运行结果

示例1 方法1 输出：III
示例1 方法2 输出：III
示例2 方法1 输出：IV
示例2 方法2 输出：IV
示例3 方法1 输出：IX
示例3 方法2 输出：IX
示例4 方法1 输出：LVIII
示例4 方法2 输出：LVIII
示例5 方法1 输出：MCMXCIV
示例5 方法2 输出：MCMXCIV
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏