題目描述：

七個不同的符號代表羅馬數字，其值如下：

字符	數值
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)原題鏈接
歡迎大家和我溝通交流(????)