iT邦幫忙

第 12 屆 iT 邦幫忙鐵人賽

DAY 11
0
自我挑戰組

[LeetCode with JavaScript] 一起來刷 LeetCode吧 ~~~ (ノ>ω<)ノ系列 第 11

[LeetCode with JavaScript] Day 11: Roman to Integer

觀前提醒:

  1. 我預設大家已經先思考並分析過題目,沒啥想法才開始 google 找解題靈感。若無,建議每題先花 1~2 顆番茄鐘的時間來分析題目比較好。可參考番茄鐘工作法
  2. 承上,既然已經有思考過了,那我這邊直接 po 題目 + 解題想法 + code +心得 。若已經在 code 內有足夠的註解了,那我可能解題想法 & 心得的部分就不會寫太多,免得干擾你的思考。
  3. 所有解法都是已經取得系統的 Accepted,但或許不是最優解法,請多包涵。
  4. 若對於解法不太懂,可以嘗試用 Chrome 的 debugger 來試跑看看 (教學文)
  5. 最後,歡迎在下面留言指教~教學相長才會進步歐~/images/emoticon/emoticon41.gif

題目

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 II in 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:

  • 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. Input is guaranteed to be within the range from 1 to 3999.

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.

解題想法

可參考以下圖片(來源:Hua Hua)
img

  • 使用一個 map 來儲存羅馬符號跟數字之間的對應關係,在一般的情況下(ex. III, VI),可以直接將羅馬符號轉換成數字。
  • 不過如果出現 IV,XC 這種組合,就要另外處理,這種組合的特色是後面的符號會大於前面的符號,且數字會變成從後一字元,減去前一字元。(“ab” pattern, b is larger than a)(The value changes from a+b to b-a)
  • 承上,若要解決此問題。需要建立一個迴圈。第一步驟:每個字元依序扔進map中,找出對應的數值並加總到sum上
  • 第二步驟,在每次加總後,檢查現在字元(currChar)是否比前一字元(preChar)為大(ab pattern)。若有,就直接減去兩倍的前一字元(preChar)。讓數值從 a+b 變成 b-a。
  • 把 currChar 的字元,賦值給 preChar,讓下一個新循環的 currChar,可以繼續跟 preChar 做比較。這樣就可以達到每次都能兩兩字元相比較的效果。

CODE

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function (s) {
  const map = {
    I: 1,
    V: 5,
    X: 10,
    L: 50,
    C: 100,
    D: 500,
    M: 1000,
  };
  let sum = 0;
  let preChar = "";
  for (let currChar of s) {
    sum += map[currChar];
    if (preChar !== "" && map[currChar] > map[preChar]) {
      sum -= 2 * map[preChar];
    }
    preChar = currChar;
  }
  return sum;
};

心得

這題也是一開始我覺得簡單,先建立好 map,然後只要把字串從左到右所對應的數值,通通加總起來就能收工。
但後來實作才發現,有一個很不好解決的地方。就是那 IV (4)、IX (9) 、IC(99)這類的,這是右邊的數字扣除左邊的數字來實現的。我也是看了花花大的影片,才天靈蓋一拍想到還能用 "a+b後,減去兩倍 a,得到 b-a"這種方式,來達到同樣效果。真的太猛啦XD


謝謝大家的收看,LeetCode 小學堂我們下次見~/images/emoticon/emoticon29.gif


上一篇
[LeetCode with JavaScript] Day 10: Valid Palindrome
下一篇
[LeetCode with JavaScript] Day 12: Merge Sorted Array
系列文
[LeetCode with JavaScript] 一起來刷 LeetCode吧 ~~~ (ノ>ω<)ノ30

尚未有邦友留言

立即登入留言