1. 问题背景与需求解析
罗马数字作为古罗马文明的计数系统，至今仍在钟表、书籍版权页等场景中使用。力扣第12题"整数转罗马数字"要求我们将阿拉伯数字（1-3999）转换为对应的罗马数字表示。这道题看似简单，但实际涉及算法设计中的贪心策略应用和特殊规则处理。
罗马数字由7个基本符号组成：I(1)、V(5)、X(10)、L(50)、C(100)、D(500)、M(1000)。其组合规则有两条核心原则：
- 相同符号连写表示相加（如III=3）
- 小数字在大数字左边表示相减（如IV=4）
在实际编码中，我们还需要处理像4(IV)、9(IX)这样的特殊组合情况。这道题的价值在于训练开发者对问题规则的抽象能力，以及如何选择高效算法实现转换。
2. 罗马数字转换的核心算法
2.1 贪心算法选择依据
面对整数转罗马数字的问题，我们首先考虑的是算法选择。贪心算法之所以适合这个场景，是因为罗马数字的表示具有"尽可能使用较大符号"的特性。例如：
- 1994的正确表示是MCMXCIV（M=1000, CM=900, XC=90, IV=4）
- 而非更冗长的MDCCCCLXXXXIIII
贪心策略在这里体现为：每次尽可能选择当前能用的最大面值符号，然后减去该值继续处理余数。这种选择具有局部最优性，且最终能达成全局最优解。
2.2 数据结构设计
为实现贪心策略，我们需要预先定义罗马数字的所有可能组合（包括常规和特殊组合），并按值从大到小排序：
cpp复制const vector<pair<int, string>> valueSymbols = {
{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"}
};
这个结构的设计考虑了几点：
- 包含了所有基础符号和特殊组合（4、9系列）
- 按数值降序排列，便于贪心选择
- 使用pair将数值与符号关联，方便迭代处理
3. C++实现详解
3.1 完整代码实现
cpp复制#include <vector>
#include <string>
using namespace std;
string intToRoman(int num) {
const vector<pair<int, string>> valueSymbols = {
{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"}
};
string roman;
for (const auto& [value, symbol] : valueSymbols) {
while (num >= value) {
num -= value;
roman += symbol;
}
if (num == 0) break;
}
return roman;
}
3.2 关键代码解析
-
数据结构初始化：
valueSymbols使用const修饰确保不被修改- 使用C++17的结构化绑定语法
[value, symbol]提高可读性
-
核心循环逻辑：
cpp复制while (num >= value) { num -= value; roman += symbol; }- 当当前数值大于等于符号值时，循环减去该值并追加符号
- 例如处理2000：第一次循环减去1000(M)两次
-
提前终止优化：
cpp复制if (num == 0) break;- 当余数为0时提前终止循环，避免不必要的迭代
4. 算法复杂度与优化
4.1 时间复杂度分析
该算法的时间复杂度主要取决于：
- 数值大小：最坏情况下需要处理所有符号（如3888→MMMDCCCLXXXVIII）
- 符号表长度：固定13个元素
实际时间复杂度为O(1)，因为：
- 数值上限固定（3999）
- 符号表长度固定
- 最坏情况下总操作次数也是常数级别
4.2 空间复杂度
- 符号表占用固定空间：O(1)
- 结果字符串长度与输入相关，但最大长度固定（最长15字符：MMMDCCCLXXXVIII）
因此空间复杂度也是O(1)
4.3 可能的优化方向
-
查表法：
- 预先生成1-3999的所有罗马数字
- 直接通过数组索引获取结果
- 优点：O(1)时间复杂度
- 缺点：占用较多内存（约60KB）
-
硬编码特殊位：
cpp复制string thousands[] = {"", "M", "MM", "MMM"}; string hundreds[] = {"", "C", "CC", /*...*/, "CM"}; // 类似定义tens和ones return thousands[num/1000] + hundreds[(num%1000)/100] + tens[(num%100)/10] + ones[num%10];- 分位处理，代码更直观
- 但扩展性较差（如要支持更大数字需修改代码）
5. 边界条件与测试案例
5.1 关键测试用例
| 输入 | 预期输出 | 测试要点 |
|---|---|---|
| 3 | III | 最小值边界 |
| 4 | IV | 特殊减法规则 |
| 9 | IX | 特殊减法规则 |
| 58 | LVIII | 多符号组合 |
| 1994 | MCMXCIV | 复杂组合情况 |
| 3999 | MMMCMXCIX | 最大值边界 |
5.2 常见错误排查
-
遗漏特殊组合：
- 忘记处理4(IV)、9(IX)等特殊情况
- 表现为：4输出为IIII，应为IV
-
符号顺序错误：
- 符号表未按值降序排列
- 导致错误结果，如1994可能输出为MDCCCCLXXXXIIII
-
数值范围检查：
- 题目限定1-3999，但代码未做输入验证
- 建议添加：
cpp复制if (num < 1 || num > 3999) return "";
6. 扩展思考与实际应用
6.1 罗马数字的现代应用
虽然罗马数字不再是主流计数系统，但仍可见于：
- 钟表表盘编号
- 书籍前言页码
- 电影版权年份显示
- 体育赛事届数标识（如Super Bowl LVII）
理解其转换规则有助于处理这些场景的数据解析需求。
6.2 类似问题练习
掌握此题后，可以尝试解决相关变种：
- 罗马数字转整数（力扣13题）
- 扩展支持更大的罗马数字（如使用上划线表示×1000）
- 开发双向转换工具类
6.3 算法思想延伸
贪心算法在此题的适用性源于罗马数字的构造规则。类似适用贪心策略的问题包括：
- 找零钱问题
- 区间调度问题
- Huffman编码
关键识别特征是：局部最优选择能导致全局最优解。