應用題 從羅馬數字轉成阿拉伯數字 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
89會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
avatar-img
發表第一個留言支持創作者!
題目會給我們一個山形的輸入陣列,和目標值target,要求我們找出目標值所在的陣列索引。如果出現兩次,返回比較小的那一個,也就是比較靠左的那個索引值。 山形的意思就是說,從最左側到山頂最大值都是遞增,從山頂最大值到右側都是遞減。
題目會給我們一組定義好的Stack 堆疊的介面,要求底層用兩個或一個Queue來實現。 也就是說,要求我們用一個或兩個FIFO的Queues去實作出一個LIFO的Stack
題目會給我們一組定義好的Queue 佇列的介面,要求底層用兩個stack來實現。 也就是說,要求我們用兩個LIFO的stacks去實作出一個FIFO的Queue
題目敘述 這題是一個經典的資料結構實作題,要求我們實作指定長度為k的環狀佇列。 請記得,佇列最重要的特質就是先進先出 First In First Out 又簡稱為 FIFO
題目會給定一個字串s,把裡面的星號*視為鍵盤上的backspace,往前(往左方)吃掉最靠近的字元。 請位最後全部操作完以後,剩下的字串內容為何? 例如: abc**,最後剩下a。 說明: bc分別被右邊的星號給吃掉。
題目會給定一個字串s,裡面都是由() [] {}打散交錯而成。 問我們給定的輸入字串s裡面,最長的合法括弧配對字串長度是多少? 例如 s = "()()" ,最長的合法括弧配對字串長度為4
題目會給我們一個山形的輸入陣列,和目標值target,要求我們找出目標值所在的陣列索引。如果出現兩次,返回比較小的那一個,也就是比較靠左的那個索引值。 山形的意思就是說,從最左側到山頂最大值都是遞增,從山頂最大值到右側都是遞減。
題目會給我們一組定義好的Stack 堆疊的介面,要求底層用兩個或一個Queue來實現。 也就是說,要求我們用一個或兩個FIFO的Queues去實作出一個LIFO的Stack
題目會給我們一組定義好的Queue 佇列的介面,要求底層用兩個stack來實現。 也就是說,要求我們用兩個LIFO的stacks去實作出一個FIFO的Queue
題目敘述 這題是一個經典的資料結構實作題,要求我們實作指定長度為k的環狀佇列。 請記得,佇列最重要的特質就是先進先出 First In First Out 又簡稱為 FIFO
題目會給定一個字串s,把裡面的星號*視為鍵盤上的backspace,往前(往左方)吃掉最靠近的字元。 請位最後全部操作完以後,剩下的字串內容為何? 例如: abc**,最後剩下a。 說明: bc分別被右邊的星號給吃掉。
題目會給定一個字串s,裡面都是由() [] {}打散交錯而成。 問我們給定的輸入字串s裡面,最長的合法括弧配對字串長度是多少? 例如 s = "()()" ,最長的合法括弧配對字串長度為4
你可能也想看
Google News 追蹤
Thumbnail
這個秋,Chill 嗨嗨!穿搭美美去賞楓,裝備款款去露營⋯⋯你的秋天怎麼過?秋日 To Do List 等你分享! 秋季全站徵文,我們準備了五個創作主題,參賽還有機會獲得「火烤兩用鍋」,一起來看看如何參加吧~
https://flipedu.parenting.com.tw/article/003994 [人間省思] [語文X數理] 昌平國小老師馬恬舒認為小孩寫數學應用題遭遇困難,原因有很多,可能是對應用題的情境不理解,也許是生活經驗不足、也許是閱讀理解能力不好、更也許是題目本身的問題、當然也有可能是
Thumbnail
這篇文章,會帶著大家複習以前學過的BFS框架, 並且以圖論的應用題與概念為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個演算法框架。 BFS 框架 + 演算法 虛擬碼 # Queue 通常初始化成根結點,作為起點 BFS_queue = deque([root])​ # 先
Thumbnail
這篇文章,會帶著大家複習以前學過的遞回框架, 並且鏈結串列的概念與應用為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個演算法框架。 遞回框架 尋找共通模式(common pattern),對應到演算法的General case 確立初始條件(initial conditio
Thumbnail
About this ebook arrow_forward最詳細的初級英檢口說參考書! 幫你馬上抓住英文口說測驗重點! 從最基礎的發音、語調到長句、短文答題策略 需要知道的應試技巧都在這一本! 完全掌握英檢出題方向,厚植考生實戰能力
Thumbnail
題目會給定我們一組十進位表示法的阿拉伯數字,要求我們把它轉換為對應的羅馬數字。
昨天進行一個小考,來檢視學生學習的成效如何。發現,應用問題有「亂寫」狀況。「亂寫」,只是表示學生寫錯,不是計算錯誤那種類型,而是被除數跟除數搞錯。 心想著,除了重新檢討這個數學問題的意思之外,還有什麼是老師可以做的,來幫助學生更能理解數學。晚上睡前,就胡思亂想了起來。
Thumbnail
AI的簡介:人工智能(Artificial Intelligence,簡稱AI)已經深入我們的日常生活,改變了我們的生活方式,並為我們帶來了更多便利。這篇文章將探討人工智能在生活中的多個應用,並簡單介紹幾款具有代表性的AI應用程序,讓你更了解這項令人振奮的AI技術。
Thumbnail
在ChatGPT橫空出世的當下😮,如何提一個好問題或是下一個好指令,成為人們的新技能🎯,但是身為老師的您,真的會問好問題嗎🤔?還有良好的提問技巧您掌握住了嗎🎓? 在課堂上,問題提問是一個重要的環節,有助於引導學生思考和參與🌟。 以下是一些常用的提問公式,以及在課堂上的應用和範例📚。
Thumbnail
雖然純詞性類已經淡出了會考選擇題的出題舞台,但在我的系統裡,詞性卻是重要的「解題武器」之一;這個武器的優勢是,他不是用事先背起來的、而是可以現場判斷,只要多加練習,有些題目「不用知道答案,也可以得分」。
Thumbnail
在台灣,常常使用含糊不清且引人注目的方式以吸引眼球,這現象在 Wikipedia 的「台灣媒體亂象」一頁也有特別說明。 那麼,ChatGPT能否替代人類新聞標題寫手,並具有多強的能力呢?本文將深入探討。
Thumbnail
這個秋,Chill 嗨嗨!穿搭美美去賞楓,裝備款款去露營⋯⋯你的秋天怎麼過?秋日 To Do List 等你分享! 秋季全站徵文,我們準備了五個創作主題,參賽還有機會獲得「火烤兩用鍋」,一起來看看如何參加吧~
https://flipedu.parenting.com.tw/article/003994 [人間省思] [語文X數理] 昌平國小老師馬恬舒認為小孩寫數學應用題遭遇困難,原因有很多,可能是對應用題的情境不理解,也許是生活經驗不足、也許是閱讀理解能力不好、更也許是題目本身的問題、當然也有可能是
Thumbnail
這篇文章,會帶著大家複習以前學過的BFS框架, 並且以圖論的應用題與概念為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個演算法框架。 BFS 框架 + 演算法 虛擬碼 # Queue 通常初始化成根結點,作為起點 BFS_queue = deque([root])​ # 先
Thumbnail
這篇文章,會帶著大家複習以前學過的遞回框架, 並且鏈結串列的概念與應用為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個演算法框架。 遞回框架 尋找共通模式(common pattern),對應到演算法的General case 確立初始條件(initial conditio
Thumbnail
About this ebook arrow_forward最詳細的初級英檢口說參考書! 幫你馬上抓住英文口說測驗重點! 從最基礎的發音、語調到長句、短文答題策略 需要知道的應試技巧都在這一本! 完全掌握英檢出題方向,厚植考生實戰能力
Thumbnail
題目會給定我們一組十進位表示法的阿拉伯數字,要求我們把它轉換為對應的羅馬數字。
昨天進行一個小考,來檢視學生學習的成效如何。發現,應用問題有「亂寫」狀況。「亂寫」,只是表示學生寫錯,不是計算錯誤那種類型,而是被除數跟除數搞錯。 心想著,除了重新檢討這個數學問題的意思之外,還有什麼是老師可以做的,來幫助學生更能理解數學。晚上睡前,就胡思亂想了起來。
Thumbnail
AI的簡介:人工智能(Artificial Intelligence,簡稱AI)已經深入我們的日常生活,改變了我們的生活方式,並為我們帶來了更多便利。這篇文章將探討人工智能在生活中的多個應用,並簡單介紹幾款具有代表性的AI應用程序,讓你更了解這項令人振奮的AI技術。
Thumbnail
在ChatGPT橫空出世的當下😮,如何提一個好問題或是下一個好指令,成為人們的新技能🎯,但是身為老師的您,真的會問好問題嗎🤔?還有良好的提問技巧您掌握住了嗎🎓? 在課堂上,問題提問是一個重要的環節,有助於引導學生思考和參與🌟。 以下是一些常用的提問公式,以及在課堂上的應用和範例📚。
Thumbnail
雖然純詞性類已經淡出了會考選擇題的出題舞台,但在我的系統裡,詞性卻是重要的「解題武器」之一;這個武器的優勢是,他不是用事先背起來的、而是可以現場判斷,只要多加練習,有些題目「不用知道答案,也可以得分」。
Thumbnail
在台灣,常常使用含糊不清且引人注目的方式以吸引眼球,這現象在 Wikipedia 的「台灣媒體亂象」一頁也有特別說明。 那麼,ChatGPT能否替代人類新聞標題寫手,並具有多強的能力呢?本文將深入探討。