LeetCode 12. Integer to Roman

问题链接

题目解析

将普通数字转换成罗马数字。

解题思路

先简单了解一下什么是罗马数字。

基本字符：I，V，X，L，C，D，M
相应的阿拉伯数字表示为：1，5，10，50，100，500，1000

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

这道题比上一题LeetCode 13. Roman to Integer难一些，需要知道一些特性。由于题目的输入范围只在1~3999，并不是很大，所以本题有多种解法。

先讲最正规的做法，其实罗马数字也是按位来表示数字的，我们只要提取出每一位上的数字，就可以用固定的罗马数字表示它。比如：（100，C）、（200，CC）、（300，CCC）、（400，CD）、（500，D）、（600，DC）、（700，DCC）、（800，DCCC）、（900，CM）。其他位也是如此。

由于这里情况较少，可以直接全部存下来，针对每一位直接表示。当然你也可以把这九种情况分成四类：100_{300、400、500}800、900，分别表示，效果相同。

参考代码

class Solution {
public:
    string intToRoman(int num) {
        string res = "";
        vector<string> v1{"", "M", "MM", "MMM"};
        vector<string> v2{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
        vector<string> v3{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
        vector<string> v4{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
        return v1[num/1000] + v2[(num%1000) / 100] + v3[(num%100) / 10] + v4[num%10];
    }
};

解法二：贪心

由于限制了输入数字范围，有一种利用贪心算法的解法，建立一个对应数组，每次通过查表找出当前可以减去的最大数，将之减去再继续查表。参考代码：

class Solution {
public:
    string intToRoman(int num) {
        string res = "";
        vector<int> Number{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        vector<string> Roman{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        for (int i = 0; i < 13; i++) {
            while (num >= Number[i]) {
                num -= Number[i];
                res += Roman[i];
            }
        }
        return res;
    }
};

相似问题：LeetCode 13. Roman to Integer

LeetCode All in One题解汇总（持续更新中...）

本文版权归作者AlvinZH和博客园所有，欢迎转载和商用，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利.