遞迴應用: 把 數字 轉成 英文表示法 Integer to English Words_Leetcode #273

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

題目敘述 Integer to English Words

給定一個整數num

請轉換成對應的的英文數字表達(One, Two, Three, ... 那種數字表達式)


測試範例:

Example 1:

Input: num = 123
Output: "One Hundred Twenty Three"

Example 2:

Input: num = 12345
Output: "Twelve Thousand Three Hundred Forty Five"

Example 3:

Input: num = 1234567
Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"
 

約束條件

Constraints:

  • 0 <= num <= 2^31 - 1

輸入的整數是32bit整數範圍內


觀察 英文數字表達式的範圍

大方向是3位數一組,區分為 千Thousand、百萬Million、十億Billion

對應到10^3, 10^6, 10^9


小細節是未滿20的小數字,英文有專門一一對應的稱呼

1 One

2 Two

3 Three

...

10 Ten

11 Eleven

12 Twelve

...

19 Nineteen


另外,20, 30, 40, ..., 90 有各自的稱呼

20 Twenty

30 Thirty

40 Forty

...

90 Ninety


演算法 遞迴分解


承接觀察點的思考

逢三位數分解一次,對應到千Thousand百萬Million十億Billion。

接著特別針對小區間1~19 還有 20, 30, 40, ..., 90 的數字進行特別處理


從高位數往低位數分解,找到對應的英文單字,分解到零的時候,整個轉換過程結束。


程式碼 遞迴分解

class Solution:
def numberToWords(self, num):

small_number = 'One Two Three Four Five Six Seven Eight Nine Ten Eleven Twelve ' \
'Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen'.split()

tens = 'Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety'.split()

def words(n):

if n < 20:
return small_number[n-1:n]

elif n < 100:
return [ tens[n//10 - 2] ] + words(n%10)

elif n < 1000:
return [ small_number[n//100-1] ] + ['Hundred'] + words(n%100)

else:
for p, w in enumerate(('Thousand', 'Million', 'Billion'), 1):

if n < 1000**(p+1):
return words(n//1000**p) + [w] + words(n%1000**p)

return ' '.join(words(num)) or 'Zero'

複雜度分析

時間複雜度: O(log n)

整數n用十進位表達,最多需要log10 n個數字,至多log n回合可以轉換完畢。


空間複雜度: O(log n)

整數n用十進位表達,最多需要log10 n個數字,至多log n回合可以轉換完畢。

遞迴深度最深為O( log n)


Reference

[1] Integer to English Words - LeetCode

留言
avatar-img
留言分享你的想法!
avatar-img
小松鼠的演算法樂園
96會員
427內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
2024/09/26
Leetcode 729. My Calendar I 給定一個行事曆的class定義和行程安排的介面interface。 請完成下列function 1.建構子MyCalendar() 初始化MyCalendar物件 2.boolean book(int start, int end) 插入新行程
Thumbnail
2024/09/26
Leetcode 729. My Calendar I 給定一個行事曆的class定義和行程安排的介面interface。 請完成下列function 1.建構子MyCalendar() 初始化MyCalendar物件 2.boolean book(int start, int end) 插入新行程
Thumbnail
2024/09/10
Insert Greatest Common Divisors in Linked List 題目給定一個鏈結串列, 請在兩兩節點之間加入一個新節點,新節點的值為兩者之間的最大公因數。 最後返回新串列的head node作為答案。
Thumbnail
2024/09/10
Insert Greatest Common Divisors in Linked List 題目給定一個鏈結串列, 請在兩兩節點之間加入一個新節點,新節點的值為兩者之間的最大公因數。 最後返回新串列的head node作為答案。
Thumbnail
2024/09/02
 Binary Tree Inorder Traversal 題目給定一個二元樹的根結點。 請輸出中序拜訪(In-order traversal)的拜訪序列。 中序拜訪的定義: 1.拜訪左子樹。 2.拜訪目前的節點。 3.拜訪右子樹。
Thumbnail
2024/09/02
 Binary Tree Inorder Traversal 題目給定一個二元樹的根結點。 請輸出中序拜訪(In-order traversal)的拜訪序列。 中序拜訪的定義: 1.拜訪左子樹。 2.拜訪目前的節點。 3.拜訪右子樹。
Thumbnail
看更多
你可能也想看
Thumbnail
透過蝦皮分潤計畫,輕鬆賺取零用金!本文分享5-6月實測心得,包含數據流程、實際收入、平臺優點及注意事項,並推薦高分潤商品,教你如何運用空閒時間創造被動收入。
Thumbnail
透過蝦皮分潤計畫,輕鬆賺取零用金!本文分享5-6月實測心得,包含數據流程、實際收入、平臺優點及注意事項,並推薦高分潤商品,教你如何運用空閒時間創造被動收入。
Thumbnail
單身的人有些會養寵物,而我養植物。畢竟寵物離世會傷心,植物沒養好再接再厲就好了~(笑)
Thumbnail
單身的人有些會養寵物,而我養植物。畢竟寵物離世會傷心,植物沒養好再接再厲就好了~(笑)
Thumbnail
不知你有沒有過這種經驗?衛生紙只剩最後一包、洗衣精倒不出來,或電池突然沒電。這次一次補貨,從電池、衛生紙到洗衣精,還順便分享使用心得。更棒的是,搭配蝦皮分潤計畫,愛用品不僅自己用得安心,分享給朋友還能賺回饋。立即使用推薦碼 X5Q344E,輕鬆上手,隨時隨地賺取分潤!
Thumbnail
不知你有沒有過這種經驗?衛生紙只剩最後一包、洗衣精倒不出來,或電池突然沒電。這次一次補貨,從電池、衛生紙到洗衣精,還順便分享使用心得。更棒的是,搭配蝦皮分潤計畫,愛用品不僅自己用得安心,分享給朋友還能賺回饋。立即使用推薦碼 X5Q344E,輕鬆上手,隨時隨地賺取分潤!
Thumbnail
身為一個典型的社畜,上班時間被會議、進度、KPI 塞得滿滿,下班後只想要找一個能夠安靜喘口氣的小角落。對我來說,畫畫就是那個屬於自己的小樹洞。無論是胡亂塗鴉,還是慢慢描繪喜歡的插畫人物,那個專注在筆觸和色彩的過程,就像在幫心靈按摩一樣,讓緊繃的神經慢慢鬆開。
Thumbnail
身為一個典型的社畜,上班時間被會議、進度、KPI 塞得滿滿,下班後只想要找一個能夠安靜喘口氣的小角落。對我來說,畫畫就是那個屬於自己的小樹洞。無論是胡亂塗鴉,還是慢慢描繪喜歡的插畫人物,那個專注在筆觸和色彩的過程,就像在幫心靈按摩一樣,讓緊繃的神經慢慢鬆開。
Thumbnail
題目敘述 Integer to English Words 給定一個整數num 請轉換成對應的的英文數字表達(One, Two, Three, ... 那種數字表達式)
Thumbnail
題目敘述 Integer to English Words 給定一個整數num 請轉換成對應的的英文數字表達(One, Two, Three, ... 那種數字表達式)
Thumbnail
題目敘述 題目會告訴我們一組英文和數字之間的轉換編碼規則,還有一個輸入字串s,問我總共有多少合法的解碼方式? 要特別留意,輸入字串可能包含有leading zero,導致無法解碼。 轉換規則如下: A <-> 1 B <-> 2 C <-> 3 ... Z <-> 26 詳細的題
Thumbnail
題目敘述 題目會告訴我們一組英文和數字之間的轉換編碼規則,還有一個輸入字串s,問我總共有多少合法的解碼方式? 要特別留意,輸入字串可能包含有leading zero,導致無法解碼。 轉換規則如下: A <-> 1 B <-> 2 C <-> 3 ... Z <-> 26 詳細的題
Thumbnail
題目敘述 題目會給我們一個整數,要求我們計算出這個整數的二進位表示法裡面,有幾個bit1? 例如 5 = 二進位的 101 => 有2個 bit1,答案為2 英文版的題目敘述在這裡
Thumbnail
題目敘述 題目會給我們一個整數,要求我們計算出這個整數的二進位表示法裡面,有幾個bit1? 例如 5 = 二進位的 101 => 有2個 bit1,答案為2 英文版的題目敘述在這裡
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
題目會給定一個存有整數的陣列,要求我們依照下列規則進行排序,由小排到大,升序排列。
Thumbnail
題目會給定一個存有整數的陣列,要求我們依照下列規則進行排序,由小排到大,升序排列。
Thumbnail
這題的題目會給我們一個輸入整數,要求我們判斷這個整數是否可以用2^k 的形式來表達 (二的冪)?
Thumbnail
這題的題目會給我們一個輸入整數,要求我們判斷這個整數是否可以用2^k 的形式來表達 (二的冪)?
Thumbnail
這題的題目會給我們一個輸入整數,要求我們判斷這個整數是否可以用4^k 的形式來表達?
Thumbnail
這題的題目會給我們一個輸入整數,要求我們判斷這個整數是否可以用4^k 的形式來表達?
Thumbnail
題目會給定我們一組十進位表示法的阿拉伯數字,要求我們把它轉換為對應的羅馬數字。
Thumbnail
題目會給定我們一組十進位表示法的阿拉伯數字,要求我們把它轉換為對應的羅馬數字。
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News