【LeetCode】12. 整数转罗马数字

12. 整数转罗马数字

题目描述

七个不同的符号代表罗马数字，其值如下：

符号 值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
罗马数字是通过添加从最高到最低的小数位值的转换而形成的。将小数位值转换为罗马数字有以下规则：

如果该值不是以 4 或 9 开头，请选择可以从输入中减去的最大值的符号，将该符号附加到结果，减去其值，然后将其余部分转换为罗马数字。
如果该值以 4 或 9 开头，使用 减法形式，表示从以下符号中减去一个符号，例如 4 是 5 (V) 减 1 (I): IV ，9 是 10 (X) 减 1 (I)：IX。仅使用以下减法形式：4 (IV)，9 (IX)，40 (XL)，90 (XC)，400 (CD) 和 900 (CM)。
只有 10 的次方（I, X, C, M）最多可以连续附加 3 次以代表 10 的倍数。你不能多次附加 5 (V)，50 (L) 或 500 (D)。如果需要将符号附加4次，请使用 减法形式。
给定一个整数，将其转换为罗马数字。

示例 1：

输入：num = 3749

输出： “MMMDCCXLIX”

解释：

3000 = MMM 由于 1000 (M) + 1000 (M) + 1000 (M)
700 = DCC 由于 500 (D) + 100 © + 100 ©
40 = XL 由于 50 (L) 减 10 (X)
9 = IX 由于 10 (X) 减 1 (I)
注意：49 不是 50 (L) 减 1 (I) 因为转换是基于小数位
示例 2：

输入：num = 58

输出：“LVIII”

解释：

50 = L
8 = VIII
示例 3：

输入：num = 1994

输出：“MCMXCIV”

解释：

1000 = M
900 = CM
90 = XC
4 = IV

提示：

• 1 <= num <= 3999

解题思路

这道题要求将整数转换为罗马数字，需要理解罗马数字的构成规则和特殊的减法表示法。这是一个数学转换和字符串构建的经典问题。

算法分析

这道题的核心思想是贪心算法，主要解法包括：

1. 贪心算法：每次选择最大的可能值进行转换（推荐）
2. 数组映射法：预定义所有可能的组合，直接查表
3. 递归方法：使用分治思想逐步转换
4. 位运算优化：按位处理，减少循环次数
5. 查表法：最直观的实现方式

问题本质分析

贪心算法详解

转换过程可视化

减法规则处理

graph TDA[减法规则] --> B[4和9的处理]B --> C[40和90的处理]C --> D[400和900的处理]B --> E[4 = IV (5-1)]B --> F[9 = IX (10-1)]C --> G[40 = XL (50-10)]C --> H[90 = XC (100-10)]D --> I[400 = CD (500-100)]D --> J[900 = CM (1000-100)]E --> K[避免重复4次]F --> KG --> KH --> KI --> KJ --> K

各种解法对比

算法流程图

flowchart TDA[开始] --> B[定义符号值数组]B --> C[初始化结果字符串]C --> D[i = 0]D --> E{i < 数组长度 && num > 0?}E -->|否| F[返回结果]E -->|是| G{num >= values[i]?}G -->|否| H[i++]G -->|是| I[添加符号到结果]I --> J[num -= values[i]]J --> GH --> EG --> K[继续检查当前值]K --> G

边界情况处理

时间复杂度分析

空间复杂度分析

关键优化点

实际应用场景

测试用例设计

代码实现要点

1. 符号数组设计：

   • 按从大到小排序
   • 包含所有基本符号和减法组合
   • 确保贪心选择的正确性

2. 贪心策略：

   • 每次选择最大的可能值
   • 重复添加符号直到无法继续
   • 处理减法规则的特殊情况

3. 字符串构建：

   • 使用strings.Builder提高效率
   • 避免频繁的字符串拼接操作
   • 动态构建结果字符串

4. 边界条件处理：

   • 处理num = 0的情况
   • 处理最大值3999的情况
   • 确保所有情况都有正确的输出

5. 性能优化：

   • 固定大小的符号数组
   • 常数时间复杂度和空间复杂度
   • 适合处理范围内的所有整数

这个问题的关键在于理解罗马数字的构成规则和掌握贪心算法的应用，通过预定义符号数组和贪心选择策略，实现高效的整数到罗马数字的转换。

完整题解代码

package mainimport ("fmt""strings"
)// intToRoman 整数转罗马数字 - 贪心算法
// 时间复杂度: O(1)，因为罗马数字有固定的最大值
// 空间复杂度: O(1)
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 result strings.Builder// 贪心算法：每次选择最大的可能值for i := 0; i < len(values) && num > 0; i++ {// 当当前值小于等于剩余数字时，重复添加对应的符号for num >= values[i] {result.WriteString(symbols[i])num -= values[i]}}return result.String()
}// intToRomanOptimized 优化版本 - 使用数组映射
// 时间复杂度: O(1)
// 空间复杂度: O(1)
func intToRomanOptimized(num int) string {// 使用数组映射，避免循环查找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]
}// intToRomanRecursive 递归方法 - 分治思想
// 时间复杂度: O(log num)
// 空间复杂度: O(log num)
func intToRomanRecursive(num int) string {if num == 0 {return ""}// 定义罗马数字映射romanMap := map[int]string{1:    "I",4:    "IV",5:    "V",9:    "IX",10:   "X",40:   "XL",50:   "L",90:   "XC",100:  "C",400:  "CD",500:  "D",900:  "CM",1000: "M",}// 找到小于等于num的最大罗马数字值maxValue := 0for value := range romanMap {if value <= num && value > maxValue {maxValue = value}}// 递归处理剩余部分return romanMap[maxValue] + intToRomanRecursive(num-maxValue)
}// intToRomanBitwise 位运算优化版本
// 时间复杂度: O(1)
// 空间复杂度: O(1)
func intToRomanBitwise(num int) string {var result strings.Builder// 处理千位for num >= 1000 {result.WriteString("M")num -= 1000}// 处理百位if num >= 900 {result.WriteString("CM")num -= 900} else if num >= 500 {result.WriteString("D")num -= 500for num >= 100 {result.WriteString("C")num -= 100}} else if num >= 400 {result.WriteString("CD")num -= 400} else {for num >= 100 {result.WriteString("C")num -= 100}}// 处理十位if num >= 90 {result.WriteString("XC")num -= 90} else if num >= 50 {result.WriteString("L")num -= 50for num >= 10 {result.WriteString("X")num -= 10}} else if num >= 40 {result.WriteString("XL")num -= 40} else {for num >= 10 {result.WriteString("X")num -= 10}}// 处理个位if num >= 9 {result.WriteString("IX")num -= 9} else if num >= 5 {result.WriteString("V")num -= 5for num >= 1 {result.WriteString("I")num -= 1}} else if num >= 4 {result.WriteString("IV")num -= 4} else {for num >= 1 {result.WriteString("I")num -= 1}}return result.String()
}// intToRomanTable 查表法 - 最直观的实现
// 时间复杂度: O(1)
// 空间复杂度: O(1)
func intToRomanTable(num int) string {// 预定义所有可能的罗马数字组合romanTable := []struct {value  intsymbol string}{{1000, "M"},{900, "CM"},{500, "D"},{400, "CD"},{100, "C"},{90, "XC"},{50, "L"},{40, "XL"},{10, "X"},{9, "IX"},{5, "V"},{4, "IV"},{1, "I"},}var result strings.Builder// 遍历表，构建结果for _, item := range romanTable {for num >= item.value {result.WriteString(item.symbol)num -= item.value}}return result.String()
}func main() {// 测试用例1num1 := 3749result1 := intToRoman(num1)fmt.Printf("示例1: num = %d\n", num1)fmt.Printf("输出: \"%s\"\n", result1)fmt.Printf("期望: \"MMMDCCXLIX\"\n")fmt.Printf("结果: %t\n", result1 == "MMMDCCXLIX")fmt.Println()// 测试用例2num2 := 58result2 := intToRoman(num2)fmt.Printf("示例2: num = %d\n", num2)fmt.Printf("输出: \"%s\"\n", result2)fmt.Printf("期望: \"LVIII\"\n")fmt.Printf("结果: %t\n", result2 == "LVIII")fmt.Println()// 测试用例3num3 := 1994result3 := intToRoman(num3)fmt.Printf("示例3: num = %d\n", num3)fmt.Printf("输出: \"%s\"\n", result3)fmt.Printf("期望: \"MCMXCIV\"\n")fmt.Printf("结果: %t\n", result3 == "MCMXCIV")fmt.Println()// 额外测试用例num4 := 3999result4 := intToRoman(num4)fmt.Printf("额外测试: num = %d\n", num4)fmt.Printf("输出: \"%s\"\n", result4)fmt.Printf("期望: \"MMMCMXCIX\"\n")fmt.Printf("结果: %t\n", result4 == "MMMCMXCIX")fmt.Println()num5 := 1result5 := intToRoman(num5)fmt.Printf("额外测试: num = %d\n", num5)fmt.Printf("输出: \"%s\"\n", result5)fmt.Printf("期望: \"I\"\n")fmt.Printf("结果: %t\n", result5 == "I")fmt.Println()// 测试优化版本fmt.Println("=== 优化版本测试 ===")result1Opt := intToRomanOptimized(num1)result2Opt := intToRomanOptimized(num2)fmt.Printf("优化版本示例1: %s\n", result1Opt)fmt.Printf("优化版本示例2: %s\n", result2Opt)fmt.Printf("结果一致: %t\n", result1Opt == result1 && result2Opt == result2)fmt.Println()// 测试递归版本fmt.Println("=== 递归版本测试 ===")result1Rec := intToRomanRecursive(num1)result2Rec := intToRomanRecursive(num2)fmt.Printf("递归版本示例1: %s\n", result1Rec)fmt.Printf("递归版本示例2: %s\n", result2Rec)fmt.Printf("结果一致: %t\n", result1Rec == result1 && result2Rec == result2)fmt.Println()// 测试位运算版本fmt.Println("=== 位运算版本测试 ===")result1Bit := intToRomanBitwise(num1)result2Bit := intToRomanBitwise(num2)fmt.Printf("位运算版本示例1: %s\n", result1Bit)fmt.Printf("位运算版本示例2: %s\n", result2Bit)fmt.Printf("结果一致: %t\n", result1Bit == result1 && result2Bit == result2)fmt.Println()// 测试查表版本fmt.Println("=== 查表版本测试 ===")result1Tab := intToRomanTable(num1)result2Tab := intToRomanTable(num2)fmt.Printf("查表版本示例1: %s\n", result1Tab)fmt.Printf("查表版本示例2: %s\n", result2Tab)fmt.Printf("结果一致: %t\n", result1Tab == result1 && result2Tab == result2)fmt.Println()// 边界值测试fmt.Println("=== 边界值测试 ===")boundaryTests := []int{1,    // 最小值4,    // 减法形式9,    // 减法形式40,   // 减法形式90,   // 减法形式400,  // 减法形式900,  // 减法形式1000, // 基本符号3999, // 最大值}for _, test := range boundaryTests {result := intToRoman(test)fmt.Printf("num = %d, roman = %s\n", test, result)}
}