【Leetcode】题目描述
罗马数字包含以下七种字符: 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 到 3999 的范围内。
示例:
- 整数转罗马数字[1]
输入: "LVIII" 输出: 58 解释: L = 50, V= 5, III = 3.
- 罗马数字转整数[2]
输入: 1994 输出: "MCMXCIV" 解释: M = 1000, CM = 900, XC = 90, IV = 4.
说下规则
四个规则:
- 相同的数字连写, 所表示的数等于这些数字相加得到的数。如 XXX表示 30
- 小的数字在大的数字的右边, 所表示的数等于这些数字相加得到的数 如VIII 表示8
- 小的数字(限于I, X, C)在大的数字的左边, 所表示的数等于大数减去小的数:如IV 表示4
- 在一个数的上面画一条横线, 表示这个数增值1000倍(由于题目只考虑4000以内的数,所以这条规则不用考虑。)
五个组数规则:
- I, X, C:最多只能连用3个, 如果放在大数的左边,只能用1个
- V, L, D: 不能放在大数的左边,只能使用一个
- I 只能用在V和X的左边。IV表示4, IX表示9
- X只能放在L,C左边。XL 表示40, XC表示90
- C只能用在D,M左边。CD 表示400, CM表示900
解题思路
- 整数转罗马数字[1]
此种题目较为复杂,因为不知道大数在左边还是右边,所以存在两种情况,需要判断一下:
- 小的数在左边,大的数字在右边(例:IV,参照上述6种特殊情况)
- 小的数在右边,大的数字在左边(例:VI表示6,即所有数字相加之和)
- 罗马数字转整数[2]
通过组合数字来拆分,使程序能够实现连加的方法。举个栗子:给定一个已知数字,假设为10,然后再给定一组数字(即数组[15,8,4,2,1]),组合数字的意思就是:使用当前所给值10与所给数组中所有元素进行比较,找出第一个小于或等于所给当前值10的数组元素,即8,然后从所给已知值中减去该值,用余数与数组中的下一个元素继续进行比较,同理找到小于或者等于该余数的值,然后继续循环往复,直到找不到满足该条件(当前余数不小于等于数组元素的时候)时,给定数字即为所有被减掉的数字之和。
画个图更简单:
图1.1 图解转换过程
代码展示
- 整数转罗马数字[1]
class Solution { public: int romanToInt(string s) { int tagVal[256]; tagVal['I']=1; tagVal['V']=5; tagVal['X']=10; tagVal['L']=50; tagVal['C']=100; tagVal['D']=500; tagVal['M']=1000; int val=0; for(int i=0;i<s.length();i++){ if(i+1>=s.length()||tagVal[s[i+1]]<=tagVal[s[i]]){ val += tagVal[s[i]]; }else{ val -= tagVal[s[i]]; } } return val; } };
- 罗马数字转整数[2]
class Solution { public: string intToRoman(int num) { if(num<=0) return""; string ret = ""; static int number[13]={1000,900,500,400,100,90,50,40,10,9,5,4,1}; static string flags[13]={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"}; for (int i=0;i<13&&num>0;i++){ if (num<number[i]) continue; while(num>=number[i]){ num -= number[i]; ret += flags[i]; } } return ret; } };
本文总结
在本文中,我们实际上讲解了Leetcode上的两个题目(即整数转罗马数字[1]、罗马数字转整数[2]),我们给出了本题详细的解题思路,并通过一个简单的图示对其做了更为透彻清晰的说明,在最后我们通过C++对这两个题目进行了代码实现,小伙伴们学会了吗?快去实现一下吧!