题目介绍

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

解题思路

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

字符	I	V	X	L	C	D	M
数字	1	5	10	50	100	500	1000

相同的数字连写，所表示的数等于这些数字相加得到的数，如：Ⅲ = 3；
小的数字在大的数字的右边，所表示的数等于这些数字相加得到的数，如：Ⅷ = 8；Ⅻ = 12；
小的数字，（限于Ⅰ、X 和C）在大的数字的左边，所表示的数等于大数减小数得到的数，如：Ⅳ= 4；Ⅸ= 9；
正常使用时，连写的数字重复不得超过三次。

枚举法

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

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

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"]

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/