图解LeetCode12：整数转罗马数字(贪心算法思路)

太过爱你忘了你带给我的痛 2023-10-04 17:13 32阅读 0赞

### LeetCode12：整数转罗马数字 ###

罗马数字包含以下七种字符：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。

给你一个整数，将其转为罗马数字。

示例：

输入：num = 3
    输出："III"
    
    输入：num = 4
    输出："IV"

#### 解题思路： ####

输入4的时候，输出应该是IV，而非IIII，因为4可以用IV代替，也就是输出的时候应该是就大输出，而非就小输出。就好像你找妈妈要生活费，你要了1000RMB，妈妈给了你1000 \* 1RMB，虽然也是钱，但是肯定不如给你10 \* 100RMB省事，如果有面值1000的RMB，肯定也是给你1 \* 1000RMB。

这个规律就是和整数转换罗马数字的规律相似，每次转换的时候需要尽可能使用大罗马数字

罗马数字代表的数值  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54mn56CB5paH_size_20_color_FFFFFF_t_70_g_se_x_16]

为了使得每次转换的时候尽量使用大的罗马数字，那就需要把罗马数字数值组合罗列出来

罗马数字组合数值：
    I		1
    IV		4
    V		5
    IX		9
    X		10
    XL		40
    L		50
    XC		90
    C		100
    CD		400
    D		500
    CM		900
    M		1000

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54mn56CB5paH_size_20_color_FFFFFF_t_70_g_se_x_16 1]

所以对于给定的数字，我们就要寻找不超过num的最大罗马数字值，然后将num减去该罗马值，继续寻找不超过num的最大罗马值，然后拼接罗马数字，循环遍历直到num为0.最后得到的字符串就是整数num代表的罗马数字。  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54mn56CB5paH_size_20_color_FFFFFF_t_70_g_se_x_16 2]

**这种解题思路就类似于找零钱的思路，使用经典的贪心算法，确保每一次遍历采用的都是当前情况下最大数值，然后再接着匹配下一阶段的最大数值，直到num为0为止。**

#### 代码实现 ####

在代码层面我们可以建立一个数值和罗马数字的列表，要求一一对应。按照数值的从大到小进行排列。遍历数值匹配列表，直到最终的num==0时，退出循环

// 创建两个数组
    int[] nums = {
        1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    String[] romans = {
        "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
    
    public String intToRoman(int num){
        
        // 声明一个StringBuilder存放结果
        StringBuilder roman = new StringBuilder();
    
        // 遍历数组
        for (int i = 0; i < nums.length; i++) {
        
            // 取出对应i的数值
            int value = nums[i];
            // 与num比较，找出小于num的最大数值
            while(value <= num){
        
                // 更新num
                num = num - value;
                // 更新罗马数字
                roman.append(romans[i]);
            }
            // num为0时候退出循环
            if (num == 0){
        
                break;
            }
        }
        return roman.toString();
    }

测试代码

public static void main(String[] args) {
        
        LeetCode12 lc = new LeetCode12();
        System.out.println(lc.intToRoman(1234));
    }

结果

MCCXXXIV

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54mn56CB5paH_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/390642195c874a34a389d138a3d7129d.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA54mn56CB5paH,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54mn56CB5paH_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/b77c6c26d8ea4bbfb63fbd0038f08922.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA54mn56CB5paH,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54mn56CB5paH_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/6ee5799fbefb43068c2e07bcbc8fff31.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA54mn56CB5paH,size_20,color_FFFFFF,t_70,g_se,x_16