遞迴應用: 把 數字 轉成 英文表示法 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
題目敘述 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