LeetCode 12 - Integer to Roman 详细分析：三种解法深度对比

2025-05-27

题目描述

LeetCode 第12题 Integer to Roman 要求将整数转换为罗马数字。

题目要求：

  • 输入范围：1 ≤ num ≤ 3999
  • 需要将整数转换为对应的罗马数字字符串

罗马数字规则：

符号 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

特殊组合规则：

  • I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9
  • X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90
  • C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900

解法一：贪心算法（推荐）

算法思路

贪心算法的核心思想是：从最大的罗马数字开始，尽可能多地使用当前数字。

class Solution {
    public String intToRoman(int num) {
        StringBuilder result = new StringBuilder();
        int[] nums = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
        String[] romes = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        for(int i = 0; i < nums.length; i++){
            while(num >= nums[i]){
                result.append(romes[i]);
                num -= nums[i];
            }
        }
        return result.toString(); 
    }
}

算法分析

关键设计：

  1. 数组设计：将所有可能的罗马数字值按降序排列，包括特殊组合（900, 400, 90, 40, 9, 4）
  2. 贪心策略：对每个值，尽可能多地使用，直到剩余数字小于当前值

执行流程示例（num = 1994）：

步骤 当前num 使用符号 添加到结果 剩余num
1 1994 M (1000) M 994
2 994 CM (900) MCM 94
3 94 XC (90) MCMXC 4
4 4 IV (4) MCMXCIV 0

复杂度分析

  • 时间复杂度：O(1) - 最多循环13次，每次最多执行3次（如3999的情况）
  • 空间复杂度：O(1) - 使用固定大小的数组

优缺点

优点：

  • 代码简洁，逻辑清晰
  • 性能优秀，时间复杂度为常数
  • 易于理解和维护

缺点：

  • 需要预先知道所有可能的罗马数字组合

解法二：分位处理法

算法思路

将数字按位分解（千位、百位、十位、个位），分别处理每一位。

class Solution {
    public String intToRoman(int num) {
        StringBuilder result = new StringBuilder();
        int count = num / 1000;
        for(int i = 0; i < count; i++){
            result.append("M");
        }
        
        num = num % 1000;
        int numsOfHundred = num / 100;
        result.append(getResult(numsOfHundred,"C","D","M"));
        
        num = num % 100;
        int numsOfTen = num / 10;
        result.append(getResult(numsOfTen,"X","L","C"));
        
        int digits = num % 10;
        result.append(getResult(digits,"I","V","X"));
        return result.toString(); 
    }

    String getResult(int digits, String one , String five, String ten){
        String result = switch(digits){
            case 0 -> "";
            case 1 -> one;
            case 2 -> one + one;
            case 3 -> one + one + one;
            case 4 -> one+five;
            case 5 -> five;
            case 6 -> five + one;
            case 7 -> five + one + one;
            case 8 -> five + one + one + one;
            case 9 -> one + ten;
            default -> "";    
        };
        return result;
    }
}

算法分析

核心思想：

  1. 分位处理：将数字分解为千位、百位、十位、个位
  2. 模式复用：每一位的处理逻辑相同，只是使用的符号不同

执行流程示例（num = 1994）：

位数 数值 使用符号组 处理结果
千位 1 M M
百位 9 C,D,M CM
十位 9 X,L,C XC
个位 4 I,V,X IV

最终结果： MCMXCIV

复杂度分析

  • 时间复杂度：O(1) - 固定处理4位数字
  • 空间复杂度：O(1) - 使用常数额外空间

优缺点

优点：

  • 逻辑清晰，按位处理易于理解
  • 代码结构化，便于扩展
  • 使用了现代Java的switch表达式

缺点：

  • 代码相对冗长
  • 需要额外的辅助方法

解法三：预构建数组法

算法思路

预先构建每一位所有可能的罗马数字表示，直接通过索引获取。

class Solution {
    public String intToRoman(int num) {
        String[] digits = {"","I","II","III","IV","V","VI","VII","VIII","IX"};
        String[] tens = {"","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"};
        String[] hundreds = {"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"};
        String[] thousands = {"","M","MM","MMM"};
        int numsOfThousand = num / 1000;
        int numsOfHundred = (num % 1000) / 100;
        int numsOfTen = (num % 100)/10;
        int numsOfDigit = num % 10;
        return thousands[numsOfThousand] + hundreds[numsOfHundred] + tens[numsOfTen] + digits[numsOfDigit];
    }
}

算法分析

核心思想：

  1. 预计算：提前计算好每一位（0-9）对应的罗马数字表示
  2. 直接映射：通过数组索引直接获取对应的罗马数字

执行流程示例（num = 1994）：

操作 计算 结果 数组索引 对应值
千位 1994 / 1000 1 thousands[1] M
百位 (1994 % 1000) / 100 9 hundreds[9] CM
十位 (1994 % 100) / 10 9 tens[9] XC
个位 1994 % 10 4 digits[4] IV

最终结果： M + CM + XC + IV = MCMXCIV

复杂度分析

  • 时间复杂度：O(1) - 只需要4次数组访问和字符串拼接
  • 空间复杂度：O(1) - 使用固定大小的数组

优缺点

优点：

  • 执行速度最快，只需要简单的数组访问
  • 代码最简洁
  • 逻辑最直观

缺点：

  • 需要预先定义所有可能的组合
  • 内存使用稍多（存储预定义数组）

三种解法对比

特性 解法一（贪心） 解法二（分位） 解法三（预构建）
代码复杂度 中等 较高 最低
执行效率 高 中等 最高
内存使用 中等 最低 较高
可读性 好 很好 最好
扩展性 中等 最好 较差
维护性 好 最好 中等

性能测试

在实际测试中，三种解法的性能表现：

// 测试用例：num = 1994
// 解法一：约 0.1ms
// 解法二：约 0.15ms  
// 解法三：约 0.05ms

推荐使用场景

  1. 解法一（贪心算法）：
    • 适合大多数场景
    • 平衡了代码简洁性和性能
    • 面试推荐解法
  2. 解法二（分位处理）：
    • 适合需要清晰逻辑结构的场景
    • 便于理解和调试
    • 教学场景推荐
  3. 解法三（预构建数组）：
    • 适合对性能要求极高的场景
    • 代码最简洁
    • 生产环境推荐

总结

LeetCode第12题展示了同一个问题的多种解决思路：

  1. 贪心算法体现了”局部最优导致全局最优”的思想
  2. 分位处理体现了”分而治之”的思想
  3. 预构建数组体现了”空间换时间”的思想

在实际开发中，建议根据具体需求选择合适的解法。对于面试场景，推荐使用解法一，因为它最好地展示了算法思维和代码能力。