13. Roman to Integer

1.問題

2.想法

• 提問

• function header, parameter

• test input

  • 前一個比後一個大的序列

  • 大小穿插

• 說明想法

  • 只要i + 1 > i, 則 sum += (v[i + 1] - v[i]);

• 測試計算複雜度: O(n)

3.程式碼

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

};