首页 > 代码库 > [LeetCode] Integer to Roman 整数转化成罗马数字
[LeetCode] Integer to Roman 整数转化成罗马数字
Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.
之前那篇文章写的是罗马数字转化成整数(http://www.cnblogs.com/grandyang/p/4120857.html)， 这次变成了整数转化成罗马数字，基本算法还是一样。由于题目中限定了输入数字的范围(1 - 3999), 使得题目变得简单了不少。
基本字符 | I | V | X | L | C | D | M |
相应的阿拉伯数字表示为 | 1 | 5 | 10 | 50 | 100 | 500 | 1000
|
例如整数 1437 的罗马数字为 MCDXXXVII， 我们不难发现，千位，百位，十位和个位上的数分别用罗马数字表示了。 1000 - M, 400 - CD, 30 - XXX, 7 - VII。所以我们要做的就是用取商法分别提取各个位上的数字，然后分别表示出来：
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 = ""; char roman[] = {‘M‘, ‘D‘, ‘C‘, ‘L‘, ‘X‘, ‘V‘, ‘I‘}; int value[] = {1000, 500, 100, 50, 10, 5, 1}; for (int n = 0; n < 7; n += 2) { int x = num / value[n]; if (x < 4) { for (int i = 1; i <= x; ++i) res += roman[n]; } else if (x == 4) res = res + roman[n] + roman[n - 1]; else if (x > 4 && x < 9) { res += roman[n - 1]; for (int i = 6; i <= x; ++i) res += roman[n]; } else if (x == 9) res = res + roman[n] + roman[n - 2]; num %= value[n]; } return res; }};
本题由于限制了输入数字范围这一特殊性，故而还有一种利用贪婪算法的解法，建立一个数表，每次通过查表找出当前最大的数，减去再继续查表。可参见 http://blog.csdn.net/havenoidea/article/details/11848921 。
[LeetCode] Integer to Roman 整数转化成罗马数字
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。