12. 整数转罗马数字

港控/mmm° 2023-01-01 02:57 117阅读 0赞

# [12. 整数转罗马数字][12.] #

## 1、题目要求 ##

> **题目描述**

![image-20201222211949695][]

> **示例**

示例1：

输入: 3
    输出: "III"

**示例 2:**

输入: 4
    输出: "IV"

**示例 3:**

输入: 9
    输出: "IX"

**示例 4:**

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

**示例 5:**

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

## 2、代码思路 ##

**贪心算法**

将给定的整数转换为罗马数字需要找到上述 13 个符号的序列，这些符号的对应值加起来就是整数。根据符号值，此序列必须按从大到小的顺序排列。符号值如下。

每次应该使用尽可能大的罗马数字去表示，因此，使用贪心算法是有意义的。贪心算法是一种在当前时间做出最佳可能决策的算法；在这种情况下，它会取出最大可能的符号。

为了表示一个给定的整数，我们寻找适合它的最大符号。我们减去它，然后寻找适合余数的最大符号，依此类推，直到余数为0。我们取出的每个符号都附加到输出的罗马数字字符串上。

![image-20201230215635611][]

## 3、代码实现 ##

class Solution {
        
        public String intToRoman(int num) {
        
    
            HashMap<Integer, Character> intToRomanChar = new HashMap<>();
            Integer[] intValues = new Integer[]{
        1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
            String[] romanChars = new String[]{
        "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
    
            int index = 0;
            StringBuilder result = new StringBuilder();
            while (num != 0) {
        
                int quotient = num / intValues[index];
                num = num % intValues[index];
                if (quotient > 0) {
        
                    for (int i = 0; i < quotient; i++) {
        
                        result.append(romanChars[index]);
                    }
                } else {
        
                    index++;
                }
            }
    
            return result.toString();
        }
    }

[12.]: https://leetcode-cn.com/problems/integer-to-roman/
[image-20201222211949695]: /images/20221120/1e53f1c658a94ae59506fc08db781b79.png
[image-20201230215635611]: /images/20221120/182ebad9ccf442bdbc6dd10efc6698cc.png