每日一題
題目說明
12.整數轉羅馬數字
羅馬數字包含以下七種字符： I， V， X， L，C，D 和 M，
字符 數值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 羅馬數字 2 寫做 II ，即為兩個并列的 1，12 寫做 XII ，即為 X + II ，
27 寫做 XXVII, 即為 XX + V + II ，
通常情況下，羅馬數字中小的數字在大的數字的右邊，
但也存在特例，例如 4 不寫做 IIII，而是 IV，
數字 1 在數字 5 的左邊，所表示的數等于大數 5 減小數 1 得到的數值 4 ，
同樣地，數字 9 表示為 IX，這個特殊的規則只適用于以下六種情況：
I 可以放在 V (5) 和 X (10) 的左邊，來表示 4 和 9，
X 可以放在 L (50) 和 C (100) 的左邊，來表示 40 和 90，
C 可以放在 D (500) 和 M (1000) 的左邊，來表示 400 和 900，
給你一個整數，將其轉為羅馬數字，
示例 1:
輸入: num = 3
輸出: “III”
示例 2:
輸入: num = 4
輸出: “IV”
示例 3:
輸入: num = 9
輸出: “IX”
示例 4:
輸入: num = 58
輸出: “LVIII”
解釋: L = 50, V = 5, III = 3.
示例 5:
輸入: num = 1994
輸出: “MCMXCIV”
解釋: M = 1000, CM = 900, XC = 90, IV = 4.
作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/integer-to-roman/solution/zheng-shu-zhuan-luo-ma-shu-zi-by-leetcod-75rs/
來源：力扣（LeetCode）
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，
演算法思路
羅馬數字：
羅馬數字由 7 個不同的單字母符號組成，每個符號對應一個具體的數值，此外，減法規則（如問題描述中所述）給出了額外的 6 個復合符號，這給了我們總共 13 個獨特的符號（每個符號由 1 個或 2 個字母組成），如下圖所示，
我們用來確定羅馬數字的規則是：
對于羅馬數字從左到右的每一位，選擇盡可能大的符號值，
對于 140，最大可以選擇的符號值為 C=100，
接下來，對于剩余的數字 40，最大可以選擇的符號值為 XL=40，
因此，140 的對應的羅馬數字為 C+XL=CXL，
模擬：
我們可以按照羅馬數字的規則建立一個字典，大概內容如下：
{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"},
遍歷 字典 中的每個數值-符號對，若當前數值value 不超過 num，則從 num 中不斷減去 value，直至 num 小于 value，然后遍歷下一個數值-符號對，若遍歷中 num 為 0 則跳出回圈，
代碼實作
const 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"},
};
class Solution {
public:
string intToRoman(int num)
{
string roman;
for (const auto[value, symbol] : valueSymbols)
{
while (num >= value)
{
num -= value;
roman += symbol;
}
if (num == 0)
{
break;
}
}
return roman;
}
};
復雜度分析
-
時間復雜度：O(1)，由于 valueSymbols 長度是固定的，且這 13 字符中的每個字符的出現次數均不會超過 3，因此回圈次數有一個確定的上限，對于本題給出的資料范圍，回圈次數不會超過 15 次，
-
空間復雜度：O(1)，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/347070.html
標籤：其他