[LeetCode] Roman to Integer

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

Example 1:

Input: "III"
Output: 3

Example 2:

Input: "IV"
Output: 4

Example 3:

Input: "IX"
Output: 9

Example 4:

Input: "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 5:

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

解題思路：

個人覺得剛開始覺得這題在程式邏輯上，蠻無趣的，因為難的不在寫 code ，在於尋找 pattern ，但仔細沈澱了一下，發現難道這世界不就是這樣嗎？使用者的消費習慣，做事的邏輯都是透過個人尋找的 pattern，再去做 rule-based 研究出來的，看來我還是太嫩了，輕瞧了這題了，陷入個人的思維陷阱了。

1. 那這題的思路就是有兩種，從後向前掃描，遇到前面數大於等於後面的最大數的時候，相加；遇到前面數小於後面的最大數的時候，相減。
2. 從前向後掃描，遇到後面數大於等於前面的最大數的時候，相減；遇到後面數小於前面的最大數的時候，相加。

另外可以知道一個特性，當羅馬數字會減時，只會看當下的那個數字跟他右邊的數字，但相加可以一直往右加好幾個。

• Runtime: 36 ms, faster than 89.55%
• Memory Usage: 12.7 MB, less than 45.32%

右邊算到左邊

• Runtime: 40 ms, faster than 80.13%
• Memory Usage: 12.7 MB, less than 47.16%

參考：

• Roman to Integer [easy] (Python)