LeetCode刷算法题 - 13. Roman to Inte

写在前面:

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

LeetCode原题链接

string - C++ Reference

C++中int与string的相互转换

C++ Map常见用法说明

Question(Easy):

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 a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Example:

Input: "III"
Output: 3

Input: "IV"
Output: 4

Input: "IX"
Output: 9

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

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

Solution

LeetCode刷算法题 - 12. Integer to Roman

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

A1、罗马数字转整数

字符串转字符列表，遍历元素累加取和。
算法时间复杂度 O(n)，Runtime: 136 ms，代码如下

class Solution {
public:
    int romanToInt(string s) {
        map <char, int> map = {
            {'I',1},
            {'V',5},
            {'X',10},
            {'L',50},
            {'C',100},
            {'D',500},
            {'M',1000}
        };
        vector<int> obj;
        for (int i=0; i<s.size(); i++) {
            obj.push_back(map[s.at(i)]);
        }
        int sum = 0;
        for (int i=0; i<obj.size()-1; i++) {
            if (obj[i]<obj[i+1]) {
                sum -= obj[i];
            } else{
                sum += obj[i];
            }
        }
        sum += obj.back();
        return sum;
    } 
};

A2、罗马数字转整数

优化减少一次赋值循环。
算法时间复杂度 O(n)，Runtime: 67 ms，代码如下

class Solution {
public:
    int romanToInt(string s) {
        map <char, int> map = {
            {'I',1},
            {'V',5},
            {'X',10},
            {'L',50},
            {'C',100},
            {'D',500},
            {'M',1000}
        };
        int sum = 0;
        sum += map[s.back()];
        
        for (int i=(int)s.size()-1; i>0; i--) {
            int left = map[s.at(i-1)];
            int right = map[s.at(i)];
            if (left < right) {
                sum -= left;
            } else{
                sum += left;
            }
        }
        return sum;
    }
};

引用相关

LeetCode 官网