[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

Alpha Camp 全端開發課程學習心得

-
我喜歡邏輯，在哲學系求學時期，我花最多時間的科目，是形式邏輯。但是我一直不明白這個我相對擅長的科目，到底能用在什麼地方。我的邏輯能力，並沒有好到足夠讓我走上學術研究的路，那麼，或許我可以試著寫程式？ 學生時期的我，自認沒有錢，但是有時間。捨不得花錢去上程式設計課程，寧願自己找資源學習。去上過一些免費的程式入門課程，c++ 和 python，對我而言不是很難，但是學完之後，我還是看不出來，要怎麼靠學到的東西解決生活中遇到的問題，漸漸地就沒有動力繼續學下去。 直到出社會，存了點錢，也漸漸體會到時間的重要，終於捨得花錢投資自己，到 Alpha Camp 上專業的課程，而不是無頭蒼蠅自己亂找一通，省下許多時間，也看到自己學的東西是真的能用的，讓我有動力繼續學下去。 我還記得學到串接 api 的時候，心裡真是太激動了。以前在學免費課程時，就隱約有種「我寫的程式，範圍只侷限在我的電腦上」的貧瘠感覺，而在知道了 api 後，發現「我寫的程式可以跟世界接上線了」，頓時覺得自己非常富有。不過，後來才知道，串別人的 api 服務通常是要付費的。 大概是受了形式邏輯的影響，我在學習程式語言時，總是試圖去辨認，哪些東西是比較基本的，基本的東西是透過什麼樣的規則組合出複雜的東西。例如，變數、array、for 迴圈和 function 是基本的東西，可以用這些基本的東西組合出 array 的 reduce 方法，像這樣： function mimicReduce(array, reducerFunction, initialValue) {     if (initialValue) {         let accumulator = initialValue         for (let i = 0; i < array.length; i++) {             accumulator = reducerFunction(accumulator, array[i])         }         return accumulator     } else {         let accumulator = array[0]         for (let i = 1; i < array.length; i
Read more

在 javascript 用 regular expression 為金額加上千位數分隔符號

-
 為了方便使用者快速判斷金額，所以想加上千位數分隔符號。例如： 3000 --> 3,000 3000000 --> 3,000,000 搜尋資料後，結論： 如果數字有小數點的話，可以用  const amount = '3000.00' amount.replace(/\B(?<!\.\d*)(?=(\d{3})+(?!\d))/g, ',') 參考資料： Javascript之數值千分位符號（Comma）的顯示 如果沒有小數點的話，可以用  const amount = '3000' amount.replace(/\B(?=(\d{3})+(?!\d))/g, ',') 參考資料： [Javascrpt]轉換數字成含千分位的文字   不過這個鬼畫符的語法我完全看不懂，查資料的時候一度不肯相信這是真正的程式碼呢⋯⋯因緣際會在讀書會中，得到 Helix 同學提示的關鍵字「 regular expression」，決定試著弄懂，「amount.replace(/\B(?=(\d{3})+(?!\d))/g, ',')」到底是什麼意思。 一、 String.prototype.replace() - MDN 範例：我不小心把 world 拼成 word，想要把句子裡所有的 word 都替換成  world。 const text = 'Hello word! Hello word!' console.log(text.replace('word', 'world')) 結果印出 Hello world! Hello word! 很不幸地，只有第一個錯字有替換，其他錯字都被放生了。如果想要替換全部的 word，就要這樣寫： const text = 'Hello word! Hello word!' console.log(text.replace( /word/ g , ' world '))
Read more

shop_platform - sqlalchemy.exc.TimeoutError

-
發生的問題 啟動伺服器後，第二十一次請求「需要查詢資料庫」的頁面時，會出現「sqlalchemy.exc.TimeoutError: QueuePool limit of size 10 overflow 10 reached, connection timed out, timeout 30.00 (Background on this error at: https://sqlalche.me/e/14/3o7r )」的錯誤訊息。如果請求是不需要查詢資料庫的（例如靜態檔案或前往登入頁面），就不會發生此錯誤。 把 size 和 overflow 設定成更小的數字，可以更快重現這個錯誤 。 感覺起來，就像查詢完資料庫以後，沒有把 connection 釋出一樣，導致「size + overflow」是多少，就只能查詢多少次資料庫。 發現瀏覽器每向伺服器請求一次「需要查詢資料庫」的頁面，在 MySQL Workbench 用 show PROCESSLIST; 指令的查詢結果就會多出一筆資料，筆數達到 size + overflow 時，若再次請求「需要查詢資料庫」的頁面，就會噴 QueuePool limit of size 10 overflow 10 reached 的錯誤。關閉伺服器時，那幾筆資料才會被刪除。 嘗試過但失敗的方法 app.run(debug=False) 自己註冊一個關閉 session 的函式 @app.teardown_appcontext # 改成 @app.teardown_request 也沒用 def teardown_db(exception): db.session.remove() # 改成 db.session.close() 也沒用 print('***** session.remove') # 這一行有印出來，所以此函式有被執行 把 FLASK_ENV=development 拿掉 ，於是 FLASK_ENV 變成預設的 production app.config["SQLALCHEMY_COMMIT_ON_TEARDOWN"] = True 終於成功的方法 第一種方法：用 Ap
Read more