LeetCode 面试经典 150_数组/字符串_整数转罗马数字（18_12_C++_中等）（模拟）(对各位进行拆解)

题目描述：

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

字符	数值
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 (C ) + 100 (C )
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、将整数与罗马数字的对应关系列列出来。
{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”}
例： 假设 num = 58

• 先检查是否大于或等于 1000
• 再检查是否大于或等于 900
• 再检查是否大于或等于 500
• 再检查是否大于或等于 400
• 再检查是否大于或等于 100
• 再检查是否大于或等于 90
• 再检查是否大于或等于 50，减去 50，结果 num = 8，添加 “L”。
• 再检查是否大于或等于 40
• 再检查是否大于或等于 10
• 再检查是否大于或等于 9
• 再检查是否大于或等于 5，减去 5，结果 num = 3，添加 “V”。
• 再检查是否大于或等于 4
• 再检查是否大于或等于 1，减去 1，结果 num = 2，添加 “I”。减去 1，结果 num = 1，添加 “I”。减去 1，结果 num = 1，添加 “I”。

2、复杂度分析：
① 时间复杂度：O(1)，因循环执行次数有限。
② 空间复杂度：O(1)。

思路二（对各位进行拆解）：

1、因 1 <= num <= 3999，所以可以建立一个 千位、百位、十位、个位的对应关系
千位 = {“”, “M”, “MM”, “MMM”}
百位 = {“”, “C”, “CC”, “CCC”, “CD”, “D”, “DC”, “DCC”, “DCCC”, “CM”}
十位 = {“”, “X”, “XX”, “XXX”, “XL”, “L”, “LX”, “LXX”, “LXXX”, “XC”}
个位 = {“”, “I”, “II”, “III”, “IV”, “V”, “VI”, “VII”, “VIII”, “IX”}

2、复杂度分析
① 时间复杂度：O(1)。
② 空间复杂度：O(1)。

代码实现

代码实现（思路一（模拟））：

class Solution1 {
public:string intToRoman(int num) {// 定义一个常量数组 valueSymbols，其中每个元素是一个pair<int, string>// 存储的是整数和对应的罗马数字符号对const pair<int,string> valueSymbols[]= {{1000, "M"},     // 1000 对应 "M"{900,  "CM"},    // 900 对应 "CM"{500,  "D"},     // 500 对应 "D"{400,  "CD"},    // 400 对应 "CD"{100,  "C"},     // 100 对应 "C"{90,   "XC"},    // 90 对应 "XC"{50,   "L"},     // 50 对应 "L"{40,   "XL"},    // 40 对应 "XL"{10,   "X"},     // 10 对应 "X"{9,    "IX"},    // 9 对应 "IX"{5,    "V"},     // 5 对应 "V"{4,    "IV"},    // 4 对应 "IV"{1,    "I"},     // 1 对应 "I"};string roman = "";  // 用于保存最终的罗马数字字符串// 当 num > 0 时继续循环，将 num 转换为罗马数字while (num > 0) {// 遍历 valueSymbols 数组，按照从大到小的顺序检查每个值for (const auto &[value, symbol] : valueSymbols) {   //结构化绑定只能在-std=c++17中使用// 如果当前的 num 大于或等于该值，则减去该值，并将相应的符号添加到结果字符串中while (num >= value) {num -= value;       // 从 num 中减去该值roman += symbol;    // 将符号添加到 roman 字符串中}}}// 返回最终生成的罗马数字字符串return roman;}
};

代码实现（思路二（对各位进行拆解））：

class Solution2 {
public:string intToRoman(int num) {const string thousands[] = {"", "M", "MM", "MMM"};const string hundreds[]  = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};const string tens[]      = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};const 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];}
};

以思路一为例进行调试

#include<iostream>
using namespace std;class Solution1 {
public:string intToRoman(int num) {// 定义一个常量数组 valueSymbols，其中每个元素是一个pair<int, string>// 存储的是整数和对应的罗马数字符号对const pair<int,string> valueSymbols[]= {{1000, "M"},     // 1000 对应 "M"{900,  "CM"},    // 900 对应 "CM"{500,  "D"},     // 500 对应 "D"{400,  "CD"},    // 400 对应 "CD"{100,  "C"},     // 100 对应 "C"{90,   "XC"},    // 90 对应 "XC"{50,   "L"},     // 50 对应 "L"{40,   "XL"},    // 40 对应 "XL"{10,   "X"},     // 10 对应 "X"{9,    "IX"},    // 9 对应 "IX"{5,    "V"},     // 5 对应 "V"{4,    "IV"},    // 4 对应 "IV"{1,    "I"},     // 1 对应 "I"};string roman = "";  // 用于保存最终的罗马数字字符串// 当 num > 0 时继续循环，将 num 转换为罗马数字while (num > 0) {// 遍历 valueSymbols 数组，按照从大到小的顺序检查每个值for (const auto &[value, symbol] : valueSymbols) {   //结构化绑定只能在-std=c++17中使用// 如果当前的 num 大于或等于该值，则减去该值，并将相应的符号添加到结果字符串中while (num >= value) {num -= value;       // 从 num 中减去该值roman += symbol;    // 将符号添加到 roman 字符串中}}}// 返回最终生成的罗马数字字符串return roman;}
};int main(int argc, char const *argv[])
{int num=3749;Solution1 s;cout<<s.intToRoman(num)<<endl;return 0;
}

LeetCode 面试经典 150_数组/字符串_整数转罗马数字（18_12)原题链接
欢迎大家和我沟通交流(✿◠‿◠)