寫在前面:

程序員分兩種，會算法的程序員和不會算法的程序員消恍。幾乎沒有一個一線互聯(lián)網(wǎng)公司招聘任何類別的技術(shù)人員是不考算法的砂吞，程序猿們都懂的预茄，現(xiàn)在最權(quán)威流行的刷題平臺就是 LeetCode。

LeetCode原題鏈接

string - C++ Reference

C++中int與string的相互轉(zhuǎn)換

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++寫的项鬼，覺得還不錯的話別忘了點個贊哦哑梳。各位同學(xué)們?nèi)绻衅渌咝Ы忸}思路還請不吝賜教，多多學(xué)習(xí)绘盟。

A1鸠真、羅馬數(shù)字轉(zhuǎn)整數(shù)

字符串轉(zhuǎn)字符列表，遍歷元素累加取和龄毡。
算法時間復(fù)雜度 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沦零、羅馬數(shù)字轉(zhuǎn)整數(shù)

優(yōu)化減少一次賦值循環(huán)祭隔。
算法時間復(fù)雜度 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;
    }
};

引用相關(guān)

LeetCode 官網(wǎng)