應用題 從羅馬數字轉成阿拉伯數字 Leetcode 13: Roman to Integer

更新於 發佈於 閱讀時間約 4 分鐘

這題的題目在這裡:

題目會給定我們一組羅馬數字,要求我們把它轉換為對應十進位表示法的阿拉伯數字。


測試範例

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].

演算法

把原本題目給的羅馬數字和十進位數字的關係建立成一張映射表(字典)。

Symbol       Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

遇到對應的符號,就把對應的十進位數字做相加。

唯一一個實作的細節是,遇到逆序排列(小的羅馬數字在前,大的羅馬數字在後)的情況時,要記得把小的那項*2補扣掉

例如,遇到IV時,IV是逆續,所以要把比較小的那項I*2補扣掉

IV = 10 + 50 - 2*10 = 60 - 20 = 40


程式碼

class Solution:
 def romanToInt(self, s: str) -> int:
  
  # key: roman symbol
  # value: decimal value
  mapping_table = {
       'I': 1,
       'V': 5,
       'X': 10,
       'L': 50,
       'C': 100,
       'D': 500,
       'M': 1000
      }
  
  # integer value
  number = 0
  
  # scan each roman symbol
  for idx, char in enumerate(s):
   
   # add corresponding value
   number += mapping_table[char]
   
   if idx and ( mapping_table[char] > mapping_table[ s[idx-1] ] ):
    
    # adjustment for IV, IX, XL, XC, CD, CM
    number -= 2 * mapping_table[ s[idx-1] ]
    
  
  return number



複雜度分析

時間複雜度: O( n)
從左到右,每個羅馬數字掃描過一遍。

空間複雜度: O(1)
都是臨時變數,所占用的記憶體空間為常數級別O(1)


關鍵知識點

想到用字典(雜湊映射表),去儲存每個羅馬數字和十進位表示裡面對應到的阿拉伯數字的映射關係。

另外,還有一個實作的細節是,遇到逆序排列(小羅馬數字的在前,大的羅馬數字在後)的情況時,要記得把小的那項*2補扣掉


Reference:

[1] Python O(n) by dictionary and math [w/ Hint] - Roman to Integer - LeetCode

留言
avatar-img
留言分享你的想法!
avatar-img
小松鼠的演算法樂園
95會員
427內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
2024/10/06
題目敘述 Rank Transform of an Array 給定一個陣列arr,請根據數字的大小給予序號,序號值介於1~len( set(arr) )之間。 最大的數字給予最大的序號。 次大的數字給予次大的序號。 ...依此類推 最小的數字給予最小的序號1。
Thumbnail
2024/10/06
題目敘述 Rank Transform of an Array 給定一個陣列arr,請根據數字的大小給予序號,序號值介於1~len( set(arr) )之間。 最大的數字給予最大的序號。 次大的數字給予次大的序號。 ...依此類推 最小的數字給予最小的序號1。
Thumbnail
2024/10/01
題目敘述 Check If Array Pairs Are Divisible by k 給定一個長度為偶數的整數陣列arr,和一個整數k 。 我們想把陣列元素兩兩一組組成pair,使得每個pair的總和可以被k整除。 如果做得到,返回True。 如果不行,返回False。
Thumbnail
2024/10/01
題目敘述 Check If Array Pairs Are Divisible by k 給定一個長度為偶數的整數陣列arr,和一個整數k 。 我們想把陣列元素兩兩一組組成pair,使得每個pair的總和可以被k整除。 如果做得到,返回True。 如果不行,返回False。
Thumbnail
2024/09/29
My Calendar II 給定一個行事曆的class定義和行程安排的介面。 請完成下列function 1.建構子MyCalendarTwo() 2.boolean book(int start, int end) 在行事曆加入一項新行程,起始時間為start, 結束時間為end。
Thumbnail
2024/09/29
My Calendar II 給定一個行事曆的class定義和行程安排的介面。 請完成下列function 1.建構子MyCalendarTwo() 2.boolean book(int start, int end) 在行事曆加入一項新行程,起始時間為start, 結束時間為end。
Thumbnail
看更多
你可能也想看
Thumbnail
「欸!這是在哪裡買的?求連結 🥺」 誰叫你太有品味,一發就讓大家跟著剁手手? 讓你回購再回購的生活好物,是時候該介紹出場了吧! 「開箱你的美好生活」現正召喚各路好物的開箱使者 🤩
Thumbnail
「欸!這是在哪裡買的?求連結 🥺」 誰叫你太有品味,一發就讓大家跟著剁手手? 讓你回購再回購的生活好物,是時候該介紹出場了吧! 「開箱你的美好生活」現正召喚各路好物的開箱使者 🤩
Thumbnail
介紹朋友新開的蝦皮選物店『10樓2選物店』,並分享方格子與蝦皮合作的分潤計畫,註冊流程簡單,0成本、無綁約,推薦給想增加收入的讀者。
Thumbnail
介紹朋友新開的蝦皮選物店『10樓2選物店』,並分享方格子與蝦皮合作的分潤計畫,註冊流程簡單,0成本、無綁約,推薦給想增加收入的讀者。
Thumbnail
題目敘述 Integer to English Words 給定一個整數num 請轉換成對應的的英文數字表達(One, Two, Three, ... 那種數字表達式)
Thumbnail
題目敘述 Integer to English Words 給定一個整數num 請轉換成對應的的英文數字表達(One, Two, Three, ... 那種數字表達式)
Thumbnail
題目敘述 題目會給定我們一個整數陣列nums,要求我們把裡面的0做元素交換,把0都搬到陣列的右邊。題目要求必須in-place在原本的陣列裡面做操作,不可以額外建立新的陣列。 題目的原文敘述 測試範例 Example 1: Input: nums = [0,1,0,3,12] Outpu
Thumbnail
題目敘述 題目會給定我們一個整數陣列nums,要求我們把裡面的0做元素交換,把0都搬到陣列的右邊。題目要求必須in-place在原本的陣列裡面做操作,不可以額外建立新的陣列。 題目的原文敘述 測試範例 Example 1: Input: nums = [0,1,0,3,12] Outpu
Thumbnail
題目敘述 題目會給我們一個陣列,要求我們返回 兩數之和=target所在的陣列索引值。 題目還額外保證,一定剛好有一組解。 測試範例 Example 1: Input: nums = [2,7,11,15], target = 9 Output: [0,1]
Thumbnail
題目敘述 題目會給我們一個陣列,要求我們返回 兩數之和=target所在的陣列索引值。 題目還額外保證,一定剛好有一組解。 測試範例 Example 1: Input: nums = [2,7,11,15], target = 9 Output: [0,1]
Thumbnail
這題的題目會給我們一個輸入整數,要求我們判斷這個整數是否可以用2^k 的形式來表達 (二的冪)?
Thumbnail
這題的題目會給我們一個輸入整數,要求我們判斷這個整數是否可以用2^k 的形式來表達 (二的冪)?
Thumbnail
這題的題目會給我們一個輸入整數,要求我們判斷這個整數是否可以用4^k 的形式來表達?
Thumbnail
這題的題目會給我們一個輸入整數,要求我們判斷這個整數是否可以用4^k 的形式來表達?
Thumbnail
題目會給定我們一組十進位表示法的阿拉伯數字,要求我們把它轉換為對應的羅馬數字。
Thumbnail
題目會給定我們一組十進位表示法的阿拉伯數字,要求我們把它轉換為對應的羅馬數字。
Thumbnail
題目會給定我們一組羅馬數字,要求我們把它轉換為對應十進位表示法的阿拉伯數字。
Thumbnail
題目會給定我們一組羅馬數字,要求我們把它轉換為對應十進位表示法的阿拉伯數字。
Thumbnail
Roman to Integer : 將羅馬數字轉換成阿拉伯數字。
Thumbnail
Roman to Integer : 將羅馬數字轉換成阿拉伯數字。
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News