凌云的博客

成功=工作+游戏+少说空话

LeetCode 算法题 12. Integer to Roman

分类:algorithm| 发布时间:2016-07-01 13:26:00


题目

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

题意

将数字转换为罗马数字。

解法 1

这个比较简单,主要是要了解罗马数字的规则。

Wikipedia: Roman numerals

class Solution {
public:
    string intToRoman(int num) {
        string ret;
        while (num) {
            if (num >= 1000) {
                ret.push_back('M');
                num -= 1000;
            } else if (num >= 900) {
                ret += "CM";
                num -= 900;
            } else if (num >= 500) {
                ret.push_back('D');
                num -= 500;
            } else if (num >= 400) {
                ret += "CD";
                num -= 400;
            } else if (num >= 100) {
                ret.push_back('C');
                num -= 100;
            } else if (num >= 90) {
                ret += "XC";
                num -= 90;
            } else if (num >= 50) {
                ret.push_back('L');
                num -= 50;
            } else if (num >= 40) {
                ret += "XL";
                num -= 40;
            } else if (num >= 10) {
                ret.push_back('X');
                num -= 10;
            } else if (num >= 9) {
                ret += "IX";
                num -= 9;
            } else if (num >= 5) {
                ret.push_back('V');
                num -= 5;
            } else if (num >= 4) {
                ret += "IV";
                num -= 4;
            } else {
                ret.push_back('I');
                --num;
            }
        }

        return ret;
    }
};

这种解法可以说是比较直接和无脑的了,看效率也还可以。 当然代码就不是那么优雅了。

解法 2

可以通过查表的形式实现。

class Solution {
public:
    string intToRoman(int num) {
        int numMap[] = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1  };
        const char *strMap[] = { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };

        string ret;
        int i = 0;
        int curNum = numMap[i];
        const char *curStr = strMap[i];
        while (num) {
            if (num >= curNum) {
                ret += curStr;
                num -= curNum;
            } else {
                ++i;
                curNum = numMap[i];
                curStr = strMap[i];
            }
        }

        return ret;
    }
};