Fork me on GitHub

Integer to Roman

题目介绍

LeetCode 12. Integer to Roman,题目的意思将整数转换为对应的罗马数字,范围 1~3999。

解题思路

首先肯定先了解下罗马数字的构成规则:

字符 I V X L C D M
数字 1 5 10 50 100 500 1000
  1. 相同的数字连写,所表示的数等于这些数字相加得到的数,如:Ⅲ = 3;
  2. 小的数字在大的数字的右边,所表示的数等于这些数字相加得到的数, 如:Ⅷ = 8;Ⅻ = 12;
  3. 小的数字,(限于Ⅰ、X 和C)在大的数字的左边,所表示的数等于大数减小数得到的数,如:Ⅳ= 4;Ⅸ= 9;
  4. 正常使用时,连写的数字重复不得超过三次。

枚举法

很容易想到因为限定了数字范围,不妨按位转换,罗列出个十百千位对应的数字。

  • M: Nil, M, MM, MMM
  • C: Nil, C, CC, CCC, CD, D, DC, DCC, DCCC, CM
  • X: Nil, X, XX, XXX, XL, L, LX, LXX, LXXX, XC
  • I: Nil, I, II, III, IV, V, VI, VII, VIII, IX
1
2
3
4
5
6
7
8
9
10
class Solution {
func intToRoman(_ num: Int) -> String {
let M = ["", "M", "MM", "MMM"]
let C = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"]
let X = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"]
let I = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]
return M[num/1000] + C[num/100%10] + X[num/10%10] + I[num%10]
}
}

贪心算法

在看过 Discuss 之后发现贪心算法,每次都去减去当前范围最大值。

  • let int = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
  • let roman = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
func intToRoman(_ num: Int) -> String {
var val = num
var res = ""
let int = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
let roman = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
for index in 0...12 {
while (val >= int[index]) {
val -= int[index]
res += roman[index]
}
}
return res
}
}

版权声明



Ivan’s Blog by Ivan Ye is licensed under a Creative Commons BY-NC-ND 4.0 International License.
叶帆创作并维护的叶帆的博客博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证

本文首发于Ivan’s Blog | 叶帆的博客博客( http://yeziahehe.com ),版权所有,侵权必究。

本文链接:http://yeziahehe.com/2017/11/12/IntegerToRoman/