Leetcode 整数转罗马数字

这段代码的算法思想是基于罗马数字的减法规则，将整数转换为罗马数字的字符串表示。下面是详细的解释：

算法步骤：

1. 定义数值和符号对应关系：代码中定义了两个数组：values 和 symbols。values 数组包含了罗马数字的数值，按从大到小的顺序排列；symbols 数组包含了与这些数值对应的罗马数字符号。比如，1000 对应 “M”，900 对应 “CM”，依此类推。

   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"};
   

2. 初始化结果：使用 StringBuilder 对象 roman 来存储结果字符串，最终得到罗马数字的表示形式。

   StringBuilder roman = new StringBuilder();
   

3. 循环匹配数值：使用一个 for 循环遍历 values 数组中的每个数值。对于每个数值 values[i]，我们通过 while 循环检查当前的数字 num 是否大于等于 values[i]。

   • 如果 num >= values[i]，说明 num 中包含了 values[i] 所代表的罗马数字部分。
   • 在 while 循环中，我们将 values[i] 从 num 中减去，并将对应的罗马数字符号 symbols[i] 添加到 roman 中。
   • 这样做的目的是确保将大的数值优先匹配完毕，从而符合罗马数字的书写规则。

   for (int i = 0; i < values.length && num > 0; i++) {
       while (num >= values[i]) {
           num -= values[i];
           roman.append(symbols[i]);
       }
   }
   

4. 结束条件：当 num 被减到零时，说明所有的数值都已经转换为罗马数字表示。此时，我们退出循环。

5. 返回结果：将 StringBuilder 对象 roman 转换为字符串并返回，得到最终的罗马数字表示。

   return roman.toString();
   

算法思想总结：

该算法采用贪心策略，即每次从最大的数值开始匹配并减去，直到 num
为零。因为罗马数字规则要求从高位到低位的排列，所以按照从大到小的顺序进行匹配和减法操作可以保证最终结果符合罗马数字的标准格式。

同时，这种方法避免了复杂的判断逻辑，是一种高效的解决方案。

通过这种方式，我们可以将整数逐步转换为符合规则的罗马数字字符串。

Java 实现

class Solution {
    public String intToRoman(int num) {
        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"};

        StringBuilder roman = new StringBuilder();
        
        for(int i = 0; i < values.length && num > 0; i++) {
            while(num >= values[i]) {
                num -= values[i];
                roman.append(symbols[i]);
            }
        }

        return roman.toString();
    }
}