LeetCode刷算法题 - 12. Integer to Roman

写在前面:

程序员分两种，会算法的程序员和不会算法的程序员。几乎没有一个一线互联网公司招聘任何类别的技术人员是不考算法的，程序猿们都懂的，现在最权威流行的刷题平台就是 LeetCode。

Question(Medium):

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, two is written as IIin Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

Ican be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed beforeD (500)and M (1000) to make 400 and 900.

Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

Example:

Input: 3
Output: "III"

Input: 4
Output: "IV"

Input: 9
Output: "IX"

Input: 58
Output: "LVIII"
Explanation: C = 100, L = 50, XXX = 30 and III = 3.

Input: 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Solution

LeetCode刷算法题 - 13. Roman to Integer

以下代码皆是本人用 C++写的，觉得还不错的话别忘了点个赞哦。各位同学们如果有其他更高效解题思路还请不吝赐教，多多学习。

A1、整数转罗马数字

以罗马数字进制为准，进行查找替换。
算法时间复杂度 O(n)，Runtime: 55 ms，代码如下

static const auto __ = []()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    return 0;
}();

class Solution {
public:
    string intToRoman(int num) {
        vector<int> values = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
        vector<string> strs = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        
        string res;
        for (int i=0; i<values.size(); i++) {
            
            while (num/values[i]) {
                res.append(strs[i]);
                num -= values[i];
            }
        }
        return res;
    }
};

A2、整数转罗马数字

以十进制为准，对相应个、十、百、千位相应数字进行赋值，然后查找替换。
算法时间复杂度 O(n)，Runtime: 56 ms，代码如下

static const auto __ = []()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    return 0;
}();

class Solution {
public:
    string intToRoman(int num) {
        
        string M[] = {"", "M", "MM", "MMM"};
        string C[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
        string X[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
        string I[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
        
        return M[num/1000] + C[(num%1000)/100] + X[(num%100)/10] + I[num%10];
    }
    
};

引用相关

LeetCode 官网

LeetCode刷算法题 - 12. Integer to Roman