# 13. Roman to Integer

## 1.問題

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LLZiZdqjc48ZMCm65Me%2F-LLZNrz2UkVDEB3KoXoZ%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-09-04%20%E4%B8%8B%E5%8D%887.41.30.png?alt=media\&token=072884f5-a779-4e89-8cd2-6c2098c3114b)

## 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;    
    }

};
```
