首页 > 代码库 > leetcode第一刷_Integer to Roman
leetcode第一刷_Integer to Roman
这道题当时不会写,是参照discuss写的。
首先要弄明白罗马数字的规则,这个在国外难道是常识吗,为什么题干一点都没讲。。
4000以下一共有下面几种符号:"M", "D", "C", "L", "X", "V", "I",对应到我们十进制为:1000, 500, 100, 50, 10, 5, 1。还有一条非常重要的规则,就是同样的字符最多重复出现三次。这就决定了数位上带4和9的跟普通的数值不一样。数位上4的做法是在比当前数位大5倍的字符左边放一个当前数位表示1的那个字符,例如个位上的四是IV,十位上的四是XL等等。9跟四类似,只不过是在比当前数位大10倍的那个字符左边放一个当前数位表示1的那个字符。
好,下面讲一下怎样把一个数字num转化成罗马数字res。我们从千位开始往前看,如果当前的底比num要大,按理说应该减小底的,但是有个情况,就是下一位如果是个9的且当前位置是以1开头的数字,比如1000,100等,那么res下一个数位应该用base+2 base的形式来表示。如果当前base是以1开头的且num的当前数位是4的时候,res的这个位应该用base base-1。除了是4的这种情况,且当前数位比base要大,那么就在res后面加上base。如果这些情况都不满足,也即base并不是以1开头的或者后面接的不是9,都是直接减少base。要注意,每当更新了res之后,要把用掉的那部分数从num中减掉。
说了这么多,其实还是代码直观一些:
string bit[7] = {"M", "D", "C", "L", "X", "V", "I"}; int mref[7] = {1000, 500, 100, 50, 10, 5, 1}; class Solution { public: string intToRoman(int num) { string res = ""; int base = 0; while(num){ if(base%2==0 && num/mref[base]==4){ res += bit[base]; res += bit[base-1]; num -= 4*mref[base]; }else if(num>=mref[base]){ res += bit[base]; num -= mref[base]; }else if(base%2==0 && num/mref[base+2]==9){ res += bit[base+2]; res += bit[base]; num -= mref[base+2]*9; }else{ base++; } } return res; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。