LeetCode

LeetCode-12 整数转罗马数字

nkul · 9月5日 · 2020年 · 39次已读
个位123456789
IIIIIIIVVVIVIIVIIIIX
十位102030405060708090
XXXXXXXXLLLXLXXLXXXXC
百位100200300400500600700800900
CCCCCCCDDDCDCCDCCCCM
千位100020003000
MMMMMMM

对于一个数按照上面表格填写即可。

进一步优化,发现表格有迹可循。比较特殊的列是1,4,5,9 ,百千也是一样!

[1,4)之间每多1字母就重复一次,[5,9)也是一样!

这样的话,
1、如果每有一个1000,就多1个M,对应到代码就是while(num>1000)num-1000,res+=”M”;
2、类似的大于9(单位)就加上对应的字母,大于5(单位)小于9(单位),加上对应的字母!

res = “”, num = 2864

numres
-1000=1864M
-1000=864MM
-500=364MMD
-100=264MMDC
-100=164MMDCC
-100=64MMDCCC
-50=14MMDCCCL
-10=4MMDCCCLX
-4=0MMDCCCLXIV
class Solution {
public:
    string intToRoman(int num) {
        int vals[] = {
            1000,
            900,500,400,100,
            90,50,40,10,
            9,5,4,1
        };
        string resp[] = {
            "M",
            "CM","D","CD","C",
            "XC","L","XL","X",
            "IX","V","IV","I"
        };
        string res;
        for(int i=0;i<13;i++){
            while(num >= vals[i]){
                res += resp[i];
                num -= vals[i];
            }
        }
        return res;
    }
};


0 条回应

必须 注册 为本站用户, 登录 后才可以发表评论!