[LeetCode] #1553. Minimum Number of Days to Eat N Oranges

-

題目

There are n oranges in the kitchen and you decided to eat some of these oranges every day as follows:

  • Eat one orange.

  • If the number of remaining oranges (n) is divisible by 2 then you can eat n/2 oranges.

  • If the number of remaining oranges (n) is divisible by 3 then you can eat 2*(n/3) oranges.

You can only choose one of the actions per day.

Return the minimum number of days to eat n oranges.

直覺解

構想：

每天，看哪個方式可以吃最多橘子，就用那個吃法。但是這題是 Hard，總覺得事情沒有這麼簡單⋯⋯

python 3 實作（失敗）：

class Solution: 

    def minDays(self, n: int) -> int: 

        days = 0 

         

        while n > 0: 

            if n % 3 == 0: 

                n = n // 3 

            elif n % 2 == 0: 

                n = n >> 1 

            else: 

                n -= 1 

            days += 1 

         

        return days

Submission Detail

Wrong Answer

Input: 10

Output: 5

Expected: 4

失敗原因

我吃橘子的顆數是：5, 1, 2, 1, 1，花了五天。解答吃橘子的顆數是：1, 6, 2, 1，只花了四天。

並不是簡單的「每天都選三個方法中，能吃最多橘子的方法」，要為「將來能吃更多橘子」製造機會。

構想：

先用上一個版本的解，算出 days 的最大值 max_days。用 recursion 嘗試所有吃橘子的組合，如果花的時間超過 max_days 就放棄這個組合。

python 3 實作（失敗）：

class Solution: 

    minDays(self, n: int) -> int: 

        max_days = 0 

        number_of_oranges = n 

        while n > 0: 

            if n % 3 == 0: 

                n = 2 * (n // 3) 

            elif n % 2 == 0: 

                n = n >> 1 

            else: 

                n -= 1 

            max_days += 1 

         

        return self.recursion(number_of_oranges, 0, max_days) 

     

    def recursion(self, n: int, days, max_days: int) -> int: 

        if n == 0: 

            return days 

        if days >= max_days: 

            return max_days 

         

        days += 1 

        action1_days = self.recursion(n - 1, days, max_days) 

        action2_days = self.recursion(n >> 1, days, max_days) if n % 2 == 0 else max_days 

        action3_days = self.recursion(n // 3, days, max_days) if n % 3 == 0 else max_days 

         

        return min(action1_days, action2_days, action3_days)

Submission Detail

Time Limit Exceeded

Last executed input: 9314

失敗原因

算太久了。

構想：

「嘗試所有可能的吃橘子方式」看來是不行的，會算太久。嘗試更改吃橘子的順序。

python 3 實作（失敗）：

class Solution: 

    def minDays(self, n: int) -> int: 

        days = 0 

        while n > 0: 

            remainder = n % 3 

            if remainder == 0: 

                n = 1 * (n // 3) 

            elif remainder == 2 and n % 2 == 0: 

                n = n >> 1 

            else: 

                n -= 1 

            days += 1 

         

        return days

Submission Detail

Wrong Answer

Input: 16

Output: 6

Expected: 5

失敗原因

我吃橘子的顆數是：1, 10, 1, 1, 2, 1，花了六天。解答吃橘子的顆數是：8, 4, 2, 1, 1，只花了五天。

input 是 16（24）的時候，可以一直採用「吃一半」的方式，而不需要額外浪費一天用「吃一個」去調整橘子的數量以符合 2 或 3 的倍數。

input 是 10 的時候，吃一個就可以把橘子數量調整成 9（32），就可以一直採用「吃 2 / 3」的方式，而不需要額外浪費一天用「吃一個」去調整橘子的數量以符合 2 或 3 的倍數。

所以這其實是類似 n = (1 * x) + 2y * 3z，然後要取最小的 x + y + z 這樣的概念？

研究別人的解

來源：C++/Java/Python 5 lines

研究重點：想看更簡潔、更有效率的寫法。

別人的 python 3 實作：

from functools import lru_cache 

class Solution: 

    @lru_cache() 

    def minDays(self, n: int) -> int: 

        if n <= 1: 

            return n; 

        return 1 + min(n % 2 + self.minDays(n // 2), n % 3 + self.minDays(n // 3));

效能：

Runtime: 44 ms, faster than 67.61% of Python3 online submissions for Minimum Number of Days to Eat N Oranges.
Memory Usage: 14 MB, less than 99.69% of Python3 online submissions for Minimum Number of Days to Eat N Oranges.

研究感想

用 + n % 2（或 n % 3）取代「把 n 取成 2 或 3 的倍數」。這樣就不會像我的解那樣，花很多時間在「一天吃一個橘子」的步驟裡了。

用 lru_cache 記憶某些 input 的 return 值，以後遇到相同 input 時就不需要再重算一次。

試著優化我的 recursion 解：

from functools import lru_cache 

class Solution: 

    def minDays(self, n: int) -> int: 

        max_days = 0 

        number_of_oranges = n 

        while n > 0: 

            if n % 3 == 0: 

                n = 2 * (n // 3) 

            elif n % 2 == 0: 

                n = n >> 1 

            else: 

                n -= 1 

            max_days += 1 

         

        return self.recursion(number_of_oranges, 0, max_days) 

     

    @lru_cache() 

    def recursion(self, n: int, days, max_days: int) -> int: 

        if n == 1: 

            return days + 1 

        if days >= max_days: 

            return max_days 

         

        days += 1 

        action2_days = self.recursion(n >> 1, days + (n % 2), max_days)  

        action3_days = self.recursion(n // 3, days + (n % 3), max_days)  

        return min(action2_days, action3_days)

效能：

Runtime: 892 ms, faster than 5.03% of Python3 online submissions for Minimum Number of Days to Eat N Oranges.
Memory Usage: 14.3 MB, less than 88.68% of Python3 online submissions for Minimum Number of Days to Eat N Oranges.

我覺得我和他的解概念應該差不多啊，我甚至還有檢查 max_days 提早結束遞迴，為什麼我的會慢這麼多？繼續做實驗。聽說遞回函式，如果遞迴的方式是 return 自己的話，通常編譯器會做一些優化避免記憶體被函式塞爆。試試看 retunr recursion 的寫法，並且取消 max_days 的檢查：

from functools import lru_cache 

class Solution: 

    def minDays(self, n: int) -> int: 

        return self.recursion(n, 0) 

     

    @lru_cache() 

    def recursion(self, n: int, days) -> int: 

        print(n) 

        if n <= 1: 

            return days + n 

 

        return min(self.recursion(n >> 1, days + 1 + (n % 2)), self.recursion(n // 3, days + 1 + (n % 3)))

效能：

Runtime: 832 ms, faster than 5.03% of Python3 online submissions for Minimum Number of Days to Eat N Oranges.
Memory Usage: 14.1 MB, less than 94.97% of Python3 online submissions for Minimum Number of Days to Eat N Oranges.

取消 max_days 的檢查之後，居然還變快一點點，真是太不給我面子了。繼續做實驗，這次改成取消 days 這個參數。

from functools import lru_cache 

class Solution: 

    def minDays(self, n: int) -> int: 

        return self.recursion(n) 

     

    @lru_cache() 

    def recursion(self, n: int) -> int: 

        if n <= 1: 

            return n 

 

        return 1 + min(n % 2 + self.recursion(n >> 1), n % 3 + self.recursion(n // 3))

效能：

Runtime: 32 ms, faster than 98.74% of Python3 online submissions for Minimum Number of Days to Eat N Oranges.
Memory Usage: 14.1 MB, less than 94.97% of Python3 online submissions for Minimum Number of Days to Eat N Oranges.

一個 days 參數就有這麼驚人的變化，到底是為什麼啊⋯⋯跟 lru_cache 的特性有關嗎？

根據 通過原始碼學習@functools.lru_cache 這篇文章，看起來，lru_cache 是用輸入函式的參數當做快取的 key。所以多了一個參數 day，如果 n 相同但 days 不同，會被當成不同的 key，就要再重算一次；而且快取的 maxsize 預設是 128，如果紀錄了很多 n 相同但 days 不同 的 key，會多佔空間。

接下來試著不用 lru_cache。自己手刻 dp。既然用了 dp，其實就不用檢查 max_days 了。

他的快取的紀錄方式，key 代表橘子總共有幾顆， value 代表要用幾天吃完。我的 dp 紀錄方式，key 是 (n, days)，因為我的算法會提前把 days 加一天，所以 dp 的 key 解讀方式是「用 days - 1 的時間把橘子吃到剩下 n 顆」。每一筆 key-value 代表「用 key 所描述的方式吃橘子的話，把 input 這麼多的橘子吃完需要 value 天」。 這個紀錄方式，讀起來真是有夠複雜的⋯⋯

class Solution: 

    def __init__(self): 

        self.dp = {} 

         

    def minDays(self, n: int) -> int: 

        return self.recursion(n, 0) 

     

    def recursion(self, n: int, days) -> int: 

        if n <= 1: 

            return days + n 

         

        if self.dp.get((n, days)) is None: 

            days += 1 

            action2_days = self.recursion(n >> 1, days + (n % 2))  

            action3_days = self.recursion(n // 3, days + (n % 3))  

            self.dp[(n, days)] = min(action2_days, action3_days) 

        return self.dp[(n, days)]

效能：

Runtime: 2576 ms, faster than 5.03% of Python3 online submissions for Minimum Number of Days to Eat N Oranges.
Memory Usage: 14.4 MB, less than 77.04% of Python3 online submissions for Minimum Number of Days to Eat N Oranges.

取消 days 這個參數：

class Solution: 

    def __init__(self): 

        self.dp = {} 

         

    def minDays(self, n: int) -> int: 

        if n <= 1: 

            return n 

         

        if self.dp.get(n) is None: 

            self.dp[n] = 1 + min(n % 2 + self.minDays(n >> 1), n % 3 + self.minDays(n // 3)) 

        return self.dp[n]

效能：

Runtime: 36 ms, faster than 95.22% of Python3 online submissions for Minimum Number of Days to Eat N Oranges.
Memory Usage: 14 MB, less than 98.73% of Python3 online submissions for Minimum Number of Days to Eat N Oranges.

研究別人的解

來源：Python 3 Dynamic Programming

研究重點：不用 recursion 的做法。

別人的 python 3 實作：

class Solution: 

    def minDays(self, n: int) -> int: 

        dp_dict = {n: 0} 

        queue = [n] 

 

        while queue: 

            num = queue.pop( 0 ) 

            new_num = num // 2 

            if new_num: 

                new_dp = dp_dict[num] + 1 + num % 2 

            else: 

                new_dp = dp_dict[num] + num % 2 

            if new_num not in dp_dict or new_dp < dp_dict[new_num]: 

                dp_dict[new_num] = new_dp 

                if new_num and new_num not in queue: 

                    queue.append( new_num ) 

            new_num = num // 3 

            if new_num: 

                new_dp = dp_dict[num] + 1 + num % 3 

            else: 

                new_dp = dp_dict[num] + num % 3 

            if new_num not in dp_dict or new_dp < dp_dict[new_num]: 

                dp_dict[new_num] = new_dp 

                if new_num and new_num not in queue: 

                    queue.append( new_num ) 

        return dp_dict[0]

效能：

Runtime: 40 ms, faster than 81.85% of Python3 online submissions for Minimum Number of Days to Eat N Oranges.
Memory Usage: 14.2 MB, less than 88.54% of Python3 online submissions for Minimum Number of Days to Eat N Oranges.

研究感想

他的 dp_dict， key-value 代表「花了 value 這麼多天，把橘子吃到剩下 key 顆」。

因為不像遞回那樣，可以設定 n >= 1 時 return n，所以計算 new_dp 時，要根據 new_dp 是否為零，判斷要不要多加 1。發現可以更快吃完橘子的話，會更新 dp_dict，所以不需要保證把紀錄寫進 dp_dict 時，就必須是最小天數。

研究別人的解非遞迴解後，自己寫一個非遞迴解

構想：

dp 的紀錄方式，key 代表橘子總共有幾顆， value 代表要用幾天吃完。因為一但把紀錄寫進 dp，就不會再更新了，所以一開始寫進去的時候，就必須保證是最小天數，導致需要把 num 從 stack 拿出來又放回去（因為目前的資訊不足以算出最小天數，所以放回去）。

python 3 實作：

class Solution: 

    def __init__(self): 

        self.dp = {0: 0, 1: 1} 

         

    def minDays(self, n: int) -> int: 

        stack = [n] 

         

        while stack: 

            num = stack.pop() 

            if self.dp.get(num) is not None: 

                continue 

                 

            num_div_2 = num >> 1 

            num_div_3 = num // 3 

            if self.dp.get(num_div_2) is not None and self.dp.get(num_div_3) is not None: 

                num_div_2_dp = self.dp[num_div_2] + num % 2 + bool(num_div_2) 

                num_div_3_dp = self.dp[num_div_3] + num % 3 + bool(num_div_3) 

                self.dp[num] = min(num_div_2_dp, num_div_3_dp) 

                continue 

             

            stack.append(num) 

            if self.dp.get(num_div_2) is None: 

                stack.append(num_div_2) 

            if self.dp.get(num_div_3) is None: 

                stack.append(num_div_3) 

                 

        return self.dp[n]

效能：

Runtime: 56 ms, faster than 37.90% of Python3 online submissions for Minimum Number of Days to Eat N Oranges.
Memory Usage: 14.2 MB, less than 88.54% of Python3 online submissions for Minimum Number of Days to Eat N Oranges.

Comments

Post a Comment

Popular posts from this blog

資料關聯

-
以飲料店的商品種類為例，假設我們現在有飲料和杯子兩種資料。 飲料： id name 1 綠茶 2 紅茶 3 青草茶 杯子： id size 1 500 2 600 3 700 一對一（One to One） 若飲料和杯子是一對一的關係，那麼情況就類似這樣： 綠茶只用 500 cc 的杯子裝 紅茶只用 600 cc 的杯子裝 青草茶只用 700 cc 的杯子裝 一種飲料只有一個尺寸的杯子，而且一個尺寸的杯子也只對應到一種飲料。在這種情況下要建立關聯，有下列兩種方式，擇一即可。這兩種做法在技術上效果是一樣的，不過語意解讀上可能不太一樣。 把關聯欄位加在飲料（語意上，是飲料有杯子這個屬性） 把關聯欄位加在杯子（語意上，是杯子有飲料這個屬性） 把關聯欄位加在飲料的資料表： id name cup_id 1 綠茶 1 2 紅茶 2 3 青草茶 3 把關聯欄位加在杯子的資料表： id size drink_id 1 500 1 2 600 2 3 700 3 一對多（One to Many） 若飲料和杯子是一對多的關係，那麼情況就類似這樣： 綠茶用 500 cc、700 cc 的杯子裝 紅茶只用 600 cc 的杯子裝 一種飲料有許多尺寸的杯子，而且一個尺寸的杯子只對應到一種飲料。 或者是這樣： 綠茶、紅茶、青草茶都只用 500 cc 的杯子裝 一個尺寸的杯子對應到許多種飲料，而且一種飲料只有一個尺寸的杯子。 在這種情況下要建立關聯，一般會選擇加在多的那一邊。如果加在少的那一
Read more

程式設計相關社群、活動

-
網頁開發 網頁開發雜記 PJCHENder網頁開發咩腳 Backend 台灣 (Backend Tw) Taiwan Backend Group Backend.tw (友善版) Google Chrome Developers 語言 Python Taiwan JavaScript.tw Kotlin： Kraftsman：Coding 職人塾 資安 網路攻防戰 資安解壓縮 Infosec Decompress DEVCORE 如何成為駭客 (資安研討會、社群與網路資源篇) Cymetrics Tech Blog （有胡立大大） 台灣電腦網路危機處理暨協調中心 UCCU Hacker HITCON GIRLS 資安人科技網 個人或公司 資料科學家的工作日常 Ant Yi-Feng Tzeng 偷米騎巴哥 John Liu 的軟體工程思維 Will 保哥的技術交流中心 新加坡商鈦坦科技 Line 的技術部落格 區塊鏈李婷婷 、 FB 、 line 群 管理 TGONetworks 91 敏捷開發之路 技術管理者交流社團 課程 軟體開發學習資訊分享 Udemy 限時免費課程 cs50 中文討論區 Lidemy 鋰學院 商業思維學院 未分類 NEX Foundation 台灣未來基金會 iThome FB Daodu Tech 科技島讀 ∞ Lab 無限大實驗室．金融科技第一站 DevOps Taiwan Chatbot Developers Taiwan 軟體開發的疑難雜症交流區 年會 Hacks In Taiwan 台灣駭客年會 FB 台灣資安大會 cybersec 2021 開源人年會 COSCUP 2021 Python 年會 PyCon 2021 ModernWeb 開發者年會 2021 Javascript 開發者年會 FB: JSDC Taiwan 敏捷年會 Agile Summit 20
Read more

TCP/ IP 通訊協定

-
為什麼要有通訊協定 不同機器之間，若要能夠溝通的話，需要大家都使用相同的語言。所有人都遵守通訊協定，就不會出現語言隔閡。 什麼是 TCP/ IP 通訊協定 要實現「不同機器之間能夠溝通」，從硬體到軟體，有許多工作要完成。為了讓這份工作比較容易進行，所以將工作拆分成好幾個部分，各自獨立完成；以後若要維護的話，哪個部分有問題，只要維修那個部分就好，不必把所有部分都拿出來檢查，降低維修難度。 至於工作到底要怎麼拆分，不同的模型有不同的建議。OSI（Open System Interconnection）模型切成七層工作，DoD（Department of Defense Model）模型則是切成四層，每一層都有不同的通訊協定。雖然目前實作上通常不是採用 OSI 模型，但為了方便理解「不同機器之間能夠溝通」的機制，通常會用 OSI 模型講解，也會試著將 DoD 模型對應到 OSI 模型。 DoD 模型中有許多通訊協定，不過以 TCP、IP 這兩個通訊協定最具有代表性，所以 DoD 模型又稱為 TCP/ IP 模型。TCP 協定對應到 OSI 模型中的傳送層，IP 協定則是對應到網路層。 TCP、IP 通訊協定負責什麼工作 TCP 協定 發送端的 TCP，和接收端的 TCP，會先進行三向交握，確認彼此能夠順利傳輸資料，才正式開始傳輸資料。 我們可以把要傳輸的資料想像成要郵寄的包裹，郵寄時，包裹會有尺寸或重量的限制，同樣地，傳輸的資料也會有大小的限制。如果資料太大了，TCP 會拆分成小包裹，並且幫每個小包裹編號（以便接收端最後能把小包裹還原成大包裹），並注意是否每一個小包裹都成功送達，若沒有成功送達，TCP 會再補上缺少的小包裹。如果資料太小了，TCP 會幫包裹灌水，以符合大小的下限。 IP 協定 IP 位址就像收件地址，以便確認要將包裹送去哪個主機。IP 位址目前有兩種版本，IPv4 用 32 位元儲存地址，IPv6 用 128 位元儲存地址。所以 IPv6 有比較多的地址可以分配給不同的主機。 IPv4 以 IPv4 而言，位址可以切成兩個部分，第一部分代表 Net ID，第二部分代表 Host ID。相同的 Net ID，代表主機位在相同的 IP 網段，相同 IP 網段的主機之間可以用廣播的方式傳遞資料，而不必透過路由。可以從 N
Read more