[LeetCode] #698. Partition to K Equal Sum Subsets

-

題目

Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal.

直覺解

構想：

把 nums 加總後除以 k，算出每個 subsets 要達到的總和是多少。

要分成 k 個 subset，那就迭代 nums 四次。每次都從 nums[0] 開始迭代，迭代到的每個數，如果加進來不會超過 target，就把該數加進來，然後從 nums 裡把用過的數刪掉（用 for 迭代，一邊迭代一邊刪東西，會有元素在迭代過程中被跳過去，所以採用的方式是，沒被用到的數就加進去新陣列裡面，下次就迭代新陣列）。如果加到剛好等於 target，那就找到一個符合題目要求的 subset。

若符合題目要求的 subset 不足 k 個，就回傳 False。

python 3 實作（失敗）：

class Solution: 

    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool: 

        target, remainder = divmod(sum(nums), k) 

        if remainder != 0: 

            return False 

         

        subset_count = 0 

        for i in range(k): 

            total = 0 

            new_nums = [] 

            for index, num in enumerate(nums): 

                if total + num <= target: 

                    total += num 

                    if total == target: 

                        subset_count += 1 

                        new_nums.extend(nums[index+1:]) 

                        break 

                else: 

                    new_nums.append(num) 

            nums = new_nums 

             

        if subset_count == k: 

            return True 

        else: 

            return False

Submission Detail

Input:
[1,1,1,1,2,2,2,2]
4

Output: false

Expected: true

失敗原因

適當的 subset 組合是 (1, 2), (1, 2), (1, 2), (1, 2)，但我一開始找到的是組合是 (1, 1, 1), (1, 2)，所以就湊不齊 4 個 subset 了。

構想：

把 nums sort，每次加總的時候從最大的開始加。把迴圈從 for 改成 while，並且從 nums[-1] 往前迭代，這樣邊刪東西邊迭代的的時候，就不會有元素被跳過去了。

python 3 實作（失敗）：

class Solution: 

    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool: 

        target, remainder = divmod(sum(nums), k) 

        if remainder != 0: 

            return False 

         

        subset_count = 0 

        nums.sort() 

        for i in range(k): 

            total = 0 

            new_nums = [] 

            i = len(nums) - 1 

            while i >= 0: 

                if total + nums[i] <= target: 

                    total += nums[i] 

                    del nums[i] 

                    if total == target: 

                        subset_count += 1 

                i -= 1 

             

        if subset_count == k: 

            return True 

        else: 

            return False

Submission Detail

Input:
[3522,181,521,515,304,123,2512,312,922,407,146,1932,4037,2646,3871,269]
5

Output: false

Expected: true

失敗原因

適當的 subset 組合是 (4037, 407),(3871, 304, 269), (3522, 922), (2646, 521, 515, 312, 181, 146, 123), (2512, 1932)

但我找到的是 (4037, 407), (3522, 922), (2512, 1932)。在找的過程中總和不是 target 卻依然被刪掉的 subset 是 (3871, 521), (2646, 515, 312, 304, 269, 181, 146)，nums 剩下 [123]，所以就湊不齊 5 個 subset 了。

⋯⋯好吧我終於明白這一題難在哪裡了，我之前真是太天真了。不能因為加起來不會超過 target 就粗暴地直接把該數字加進去然後刪掉。

研究別人的解

來源：Python DFS

研究重點：我想到的「不要重複使用同一個 nums[i]」 的方式，是用完後就把他從 nums 裡刪掉。他沒有刪東西，那他是怎麼避免重複使用同一個 nums[i]？他怎麼確保 nums[i] 有放在合適的 subset 裡？

別人的 python 3 實作（已加上研究用的 print）：

class Solution: 

    @staticmethod 

    def canPartitionKSubsets(nums, k): 

        target, m = divmod(sum(nums), k) 

        if m: 

            return False 

        dp, n = [0]*k, len(nums) 

        nums.sort(reverse=True) 

 

        def dfs(i): 

            print('<--') 

            if i == n: 

                print('i == n', 'set(dp):', set(dp)) 

                print('-->') 

                return len(set(dp)) == 1 

            print('i:', i, 'nums[i]:', nums[i]) 

            for j in range(k): 

                dp[j] += nums[i] 

                print('j:', j, 'dp:', dp) 

                if dp[j] <= target and dfs(i+1): 

                    print('-->') 

                    return True 

                dp[j] -= nums[i] 

                if not dp[j]: 

                    print('not dp[j].', 'dp[j]:', dp[j]) 

                    print('-->') 

                    break 

            print('-->') 

            return False 

        return nums[0] <= target and dfs(0)

效能（沒有加 print 的版本）：

Runtime: 44 ms, faster than 84.28% of Python3 online submissions for Partition to K Equal Sum Subsets.
Memory Usage: 14.3 MB, less than 51.31% of Python3 online submissions for Partition to K Equal Sum Subsets.

研究感想

我的寫法是，蒐集完一個 subset 裡要放哪些 nums[i] 之後，再蒐集下一個 subset 裡要放哪些 nums[i]，所以我的 for 迴圈順序是，外圈迭代 range(k)，內圈迭代 range(len(nums))。他則是把一個 nums[i] 放進合適的 subset 後，再把下一個 nums[i] 放進合適的 subset，所以他的做法是，最外層用遞迴函式遍歷 nums，遞迴函式裡面的 for 迴圈則迭代 range(k)>。因為他最外層是迭代 nums，所以他要從 sum 裡面把 nums[i] 減掉就不會重複使用 nums[i] 了，不需要做到「把 nums[i] 從 nums 裡刪掉」的地步。

先把 nums[i] 暫時先放在第一個「加進去後總和不會超過 target」的 subset 裡，然後確定 nums[i+1] 也有合適的 subset 可以安置以後，才真正確定下來 nums[i] 的確要放在這個 subset 裡。如果發現 nums[i+1] 沒有合適的 subset 可以安置，那 nums[i] 就要放到別的 subset 裡。

如果 i == n，代表 nums 裡的所有數字都被放在某個 subset 裡了，此時就檢查是否每個 subset 的總和都相等。若相等的話，len(set(dp)) 會是 1。

關於 if not dp[j]: break

試著把此行程式碼刪掉，結果效能變成了 Runtime: 2448 ms, faster than 9.12% of Python3 online submissions。看來這一行應該是為效能而增加的，例如盡快脫離不可能的 subset 組合。

試著用 nums = [2, 2, 2, 2, 2, 2], k = 4 這組 input，觀察這行程式碼如何增進效能。

subset 裡面連第一個數字都放不進去的時候，會用到這行程式碼。主要是因為 dfs(i+1) 是 false 而放不進去。不可能是因為總和大於 target 而放不進去，因為如果 nums[i] 本身就大於 target 的話，這個函式早在 return nums[0] <= target and dfs(0) 時就 return False 了，根本沒辦法執行到 if not dp[j]: break 這一行。過程如下列程式碼註釋處：

def dfs(i): 

      if i == n: 

          return len(set(dp)) == 1 

      for j in range(k): 
 
          dp[j] += nums[i] # dp[j] 原本是 0，現在加上了 nums[i] 

          if dp[j] <= target and dfs(i+1): 

              return True 

          dp[j] -= nums[i] # nums[i] 不適合放在 j 這個 subset，所以把 nums[i] 減掉，變回 0 

          if not dp[j]: break # 0 是 falsy，所以符合 if 設定的條件 

      return False

放數字到 subset 時，是前面的 subset 都放不進去，才輪得到放在後面的 subset。前面的 subset 都放不進去 nums[i] 了，後面的 subset 在 sum 明明是 0 （代表還沒有放任何數字）的情況下卻也放不進去的話，代表 nums[i] 是真的放不進任何一個 subset，所以 return False。

研究別人的解

來源：Python Solution

別人的 python 3 實作：

class Solution: 

    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool: 

         

        target, remainder = divmod(sum(nums), k) 

         

        if remainder: return False  

         

        def searchSubsets(subsets): 

            if not nums: return True  

             

            v = nums.pop() 

             

            for i, val in enumerate(subsets): 

                if val + v <= target: 

                    subsets[i] += v 

                    if searchSubsets(subsets): 

                        return True 

                    # backtrack 

                    subsets[i] -= v 

                if not subsets: 

                    break 

             

            # backtrack 

            nums.append(v) 

            # This combination did not work return False and backtrack or go back to calling function 

            return False  

         

        nums.sort() 

         

        if nums and nums[-1] > target: 

            return False 

        if nums and nums[-1] == target: 

            nums.pop() 

            k -= 1 

         

        return searchSubsets([0] * k)

效能：

Runtime: 1696 ms, faster than 15.16% of Python3 online submissions for Partition to K Equal Sum Subsets.
Memory Usage: 14.5 MB, less than 15.44% of Python3 online submissions for Partition to K Equal Sum Subsets.

研究感想

解題構想跟上一個解差不多。在實作上不太一樣的地方：

  • 上一個解：if i == n: return len(set(dp)) == 1
    這一個解：if not nums: return True

    把上一個解改成 if i == n: return True 的話也能 submit 成功

  • 上一個解：if not dp[j]: break
    這一個解：if not subsets: break

    把這一個解改成 if not subsets[i]: break 的話效能改善很多：
    Runtime: 36 ms, faster than 96.35% of Python3 online submissions for Partition to K Equal Sum Subsets.
    Memory Usage: 14.2 MB, less than 75.37% of Python3 online submissions for Partition to K Equal Sum Subsets.

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