LeetCode 12. 整数转罗马数字

Categories:

题目描述
思路分析
1. 解法一：贪心 + 映射表（推荐）
2. 解法二：硬编码打表
相似题目

题目描述

✅ 12. 整数转罗马数字

思路分析

解法一：贪心 + 映射表（推荐）

核心思路：

构建一张从大到小排列的「值-符号」映射表，共 13 个条目，涵盖所有特殊组合（如 IV=4、IX=9、XL=40 等）。

从最大值开始，每次贪心地减去当前最大可用值，并将对应符号追加到结果中，重复直到数字归零。

由于输入范围固定为 1–3999，整个过程最多循环常数次，时间复杂度为 O(1)。

复杂度分析：

时间复杂度：O(1)，因为输入范围固定（1–3999），循环次数有上界

空间复杂度：O(1)，映射表大小固定为 13

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 sb = new StringBuilder();

        // 贪心：依次用最大可用值减去 num，直到归零
        for (int i = 0; i < values.length; i++) {
            while (num >= values[i]) {
                sb.append(symbols[i]);
                num -= values[i];
            }
        }

        return sb.toString();
    }
}

func intToRoman(num int) string {
    // 从大到小排列的值-符号映射表，包含所有特殊组合
    values := []int{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
    symbols := []string{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}

    var sb strings.Builder

    // 贪心：依次用最大可用值减去 num，直到归零
    for i, v := range values {
        for num >= v {
            sb.WriteString(symbols[i])
            num -= v
        }
    }

    return sb.String()
}

解法二：硬编码打表

核心思路：

将千位、百位、十位、个位分别建表，每一位预先列出所有可能的罗马数字字符串（0–9 共 10 项）。

直接通过整除和取模拆分各位，查表拼接即可，无需循环减法。

代码更简洁，但需要记忆 4 张表。

复杂度分析：

时间复杂度：O(1)，4 次查表操作

空间复杂度：O(1)，4 张固定大小的查找表

class Solution {
    public String intToRoman(int num) {
        // 千位对应的罗马数字（最大值 3999，千位最多到 3）
        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"};

        // 拆分各位，分别查表后拼接
        return thousands[num / 1000]
                + hundreds[num % 1000 / 100]
                + tens[num % 100 / 10]
                + ones[num % 10];
    }
}

func intToRoman(num int) string {
    // 千位对应的罗马数字（最大值 3999，千位最多到 3）
    thousands := []string{"", "M", "MM", "MMM"}
    // 百位对应的罗马数字
    hundreds := []string{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"}
    // 十位对应的罗马数字
    tens := []string{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"}
    // 个位对应的罗马数字
    ones := []string{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"}

    // 拆分各位，分别查表后拼接
    return thousands[num/1000] +
        hundreds[num%1000/100] +
        tens[num%100/10] +
        ones[num%10]
}

相似题目

题目	难度	考察点
13. 罗马数字转整数	简单	字符串 / 哈希映射
273. 整数转换英文表示	困难	字符串 / 分组处理
168. Excel 表列名称	简单	数学 / 进制转换
171. Excel 表列序号	简单	数学 / 进制转换
405. 数字转换为十六进制数	简单	数学 / 进制转换
258. 各位相加	简单	数学
263. 丑数	简单	数学 / 贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/70984495