[教學] 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

For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 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:

I can 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 before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

Example 1:

Input: s = "III"
Output: 3
Explanation: III = 3.

Example 2:

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

Example 3:

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

Constraints:

1 <= s.length <= 15
s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').
It is guaranteed that s is a valid roman numeral in the range [1, 3999].

目前一樣維持每日一刷, 我都懷疑自己是不是確診還是怎樣, 最近如果不先刷一下題目, 好像腦袋都不太會開機一樣, 但如果刷太難, 又會花太多時間在這個上面, 工作又做不完, 嘖嘖, 所以目前還是以有刷就好, 能開機即可的程度, 之後再來慢慢的增加難度吧, 畢竟之前好像也刷到中上了, 簡單的其實不用花太久.

這一題很有趣, 本來我看到這題後, 第一個想法是, 我完全不用想, 就能搞出答案來, 就是對照表麻.... 從第一個對照到最後然後加起來就好, 所以我就寫出了這種程式.

int romanToInt(string s) {
   int result = 0;
   char * temp = &s[0];
   int nStrLength = s.length();
   for (int i = 0; i < nStrLength; i++)
   {
       char ch = temp[i];

       if (ch == 'I' || ch == 'i')
       {
           result += 1;
       }
       if (ch == 'V' || ch == 'v')
       {
           result += 5;
       }
       if (ch == 'X' || ch == 'x')
       {
           result += 10;
       }
       if (ch == 'L' || ch == 'l')
       {
           result += 50;
       }
       if (ch == 'C' || ch == 'c')
       {
           result += 100;
       }
       if (ch == 'D' || ch == 'd')
       {
           result += 500;
       }
       if (ch == 'M' || ch == 'm')
       {
           result += 1000;
       }
   }
   return result;
}

讀取近來依次加, 結束; 但丟到題目上去的時候發現竟然錯了??? , 然後不信邪的我還連丟兩次,

後來我才去把題目整個再好好看一次, 然後理解完規則後, 才弄出來Q_Q

好, 我們來講一下規則, 總共有三個, 簡單來說就是,

1. 羅馬數字通常由小到大書寫, 最大的符號要先出現, 接下來依次變小, 例如: 1011 = MXI

=> 這樣是完全正確的, 也是我上面那個程式會對的邏輯.

2. 接下來我們要考慮特殊情況, IM = > 1001? 按照對照表, I = 1 , M = 1000 , 所以相加等於1001嗎?

=> 好, 我就是錯在這裡, 不對, 如果由小到大的時候, I會變成負數, M會變成正數, 也就是 IM = 999 (-1 +1000) = 999

3. 最後, 我們來看一下複合的題型 IIM = 998嗎 ? , 不對, 沒有IIM這種寫法, 那要寫成998怎麼寫 ?

=> CMXCVIII => 998 => 如果按照第一個規則的話, 其實是可以變成 DCCCCLXXXXVI ( 也是很難書寫 )

=> 怎麼變成的呢 ? 來, 我算給你聽, 你就知道有夠複雜的....

首先我們要算這個, 我們必須兩位數兩位數來, 然後由左至右, 也就是先從 CM開始,

一開始CMXCVIII 的兩位, CM的話, C = 100 , M = 1000 , 按照規則2, 我們知道C是負數;

( 負數 : C , 正數 : - )

接下來我們看CMXCVIII 的 MX, M =1000, X = 10 , 由此可知, M是正數

( 負數 : C , 正數 : M )

接下來我們看CMXCVIII 的 XC, X =100, C = 100 , 由此可知, X是負數

( 負數 : CX , 正數 : M )

接下來我們看CMXCVIII 的 CV, C =100, V = 5 , 由此可知, C是正數

( 負數 : CX , 正數 : MC )

接下來我們看CMXCVIII 的 VI, V =5, I = 1 , 由此可知, V是正數

( 負數 : CX , 正數 : MCV )

接下來我們看CMXCVIII 的 II, I =1, I = 1 , 由此可知, I和I 都是正數

( 負數 : CX , 正數 : MCVII)

接下來我們把正數負數加起來, CX = (-100 + -10 ) = -110 , MCVII = ( 1000 + 100 + 5 + 1 + 1 + 1 ) = 1108 ,

1108 - (-110) = 998, 這就是答案.

所以我們按照規則, 可以將這些寫成程式, 規則就是, 我們必須兩位數兩位的來看, 要決定前面是正還是負, 要取決於前面那個數字是否大於後面的數字, 如此如此這般這般, 我們就可以把正數和負數區分出來了;

最後, 我們寫點程式吧, 下面是改完後的程式,

int romanToInt(string s) {

   map<char, int>roman
   {
       {'I',1       },
       {'V',5       },
       {'X',10       },
       {'L',50       },
       {'C',100   },
       {'D',500   },
       {'M',1000   }
   };

   int result = 0;
   for (int i = 0; i < s.length(); i++)
   {
       // 1. 確認i+1是否有超過範圍
       if (i + 1 < s.length() && roman[s[i]] < roman[s[i + 1]])
           result -= roman[s[i]];
       else
           result += roman[s[i]];
   }
   return result;
}

我們先用一個map去記住對應的對照表是如何, 然後我們有一個回圈, 裡面去判斷下一個數組是否還有值, 如果有, 去看看這個數的下一個數是不是大於前一個數, 如果是的話, 就是負數, 不是的話就是正數, 最後將這個數return 出去就是答案了.

MCMXCIV = > 1994