[LeetCode] #1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

-

題目

Given an array nums and an integer target.

Return the maximum number of non-empty non-overlapping subarrays such that the sum of values in each subarray is equal to target.

直覺解

構想：

我把 non-overlapping subarray 理解為「nums 中的每個成員，最多只能用在一個 subarray 裡」（後來才發現不是這個意思⋯⋯做白工啊做白工 orz）

先找出所有 subarray，再過濾出 sum 等於 target 的 non-empty subarray，為了加快查詢速度，把過濾出來的 subarray 轉為 dictionary，key 是數字，value 是數字出現幾次。用 recursion 嘗試所有可能的 non-overlapping subarray 組合，找出 maximum number。

python 3 實作（失敗）：

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        sum_eq_target = []
        for array in self.get_subarrays(nums):
            if array and sum(array) == target:
                map = {}
                for item in array:
                    map[item] = map.get(item, 0) + 1
                sum_eq_target.append(map)
        if not sum_eq_target:
            return 0
        
        nums_map = {}
        for n in nums:
            nums_map[n] = nums_map.get(n, 0) + 1
        return self.count_max_nonoverlapping(0, 0, nums_map, sum_eq_target, {})
        
    @staticmethod
    def get_subarrays(nums):
        subarrays = [[]]
        for n in nums:
            temp = []
            for array in subarrays:
                temp.append(list(array))
                copy = array.copy()
                copy.append(n)
                temp.append(copy)
            subarrays = temp
        return subarrays
    
    def count_max_nonoverlapping(self, index, count, nums_map, subarray_map, used_nums_map):
        if index == len(subarray_map):
            return count
        
        # not choose this subarray
        count_1 = self.count_max_nonoverlapping(index + 1, count, nums_map, subarray_map, used_nums_map)
        
        # add subarray
        new_used_nums_map = used_nums_map.copy()
        for key in subarray_map[index]:
            new_used_nums_map[key] = new_used_nums_map.get(key, 0) + subarray_map[index][key]
            
        # if not overlapping, choose this subarray
        is_overlapping = False
        for key, value in new_used_nums_map.items():
            if value > nums_map[key]:
                is_overlapping = True

        count_2 = -1
        if not is_overlapping:
            count_2 = self.count_max_nonoverlapping(index + 1, count + 1, nums_map, subarray_map, new_used_nums_map)
                                 
        return max(count_1, count_2)

Submission Detail

Wrong Answer

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

Output: 1

Expected: 0

失敗原因

我不太明白，為什麼 Expected 是 0。在 [1,2,3,4] 裡， 1 + 3 + 4 會等於 8 呀，而且只有這個組合會等於 target，所以不可能會有 overlapping 的問題。那為什麼答案居然不是 1？我在哪裡誤會了什麼嗎⋯⋯

研究別人的解

來源：python easy || beats 100%

研究重點：Input: [1,2,3,4], 8 的 Expected 為什麼是 0。想看更簡潔、更有效率的寫法。

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

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        f={}
        f[0]=1;s=0;ans=0
        for j in nums:
            print('j:', j, 'f:', f, 's:', s)
            s+=j
            if s-target in f:ans+=1;f={}
            f[s]=1
        print(ans)
        return ans

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

Runtime: 584 ms, faster than 97.96% of Python3 online submissions for Maximum Number of Non-Overlapping Subarrays With Sum Equals Target.
Memory Usage: 24 MB, less than 68.71% of Python3 online submissions for Maximum Number of Non-Overlapping Subarrays With Sum Equals Target.

研究感想

找到一組 non-empty non-overlapping subarray 後，會把 f reset 為 empty dictionary。

Input: nums = [-1,3,5,1,4,2,-9], target = 6 印出來的東西：

j: -1 f: {0: 1} s: 0
j: 3 f: {0: 1, -1: 1} s: -1
j: 5 f: {0: 1, -1: 1, 2: 1} s: 2
j: 1 f: {0: 1, -1: 1, 2: 1, 7: 1} s: 7
j: 4 f: {8: 1} s: 8
j: 2 f: {8: 1, 12: 1} s: 12
j: -9 f: {14: 1} s: 14
2

for 迴圈執行到 j 是 1 那一圈時，因為 f 裡面有 2: 1 這筆資料，所以符合 s-target in f 的條件，於是 ans += 1 並重置 f。f 裡面的 2: 1 這筆資料，是把 nums 中的 -1 和 3 相加而來的。-1 和 3 其實沒用到，真正組合起來會等於 target 的是 5 和 1。然後把 f 重置，f 裡面只剩下 8: 1 這組 key-value pair，意思是 nums 中的 -1,3,5,1 這四個數字（總和正是 8 這個 key），都不能再拿去組合「總和是 target 的 subarray」了。

s 一路把 nums 中的成員加總起來，f 負責紀錄「哪些 subarray 不能再使用」。因為不能 overlapping，所以找到一組答案，就要把 f 重置。f 只要有 key 就夠了，key 對應的 value 是多少其實無所謂，他的解姑且把 value 設成 1。

試著把 f 從 dictionary 改成 set，驗證我「f 只要有 key 就夠了」這個理解是否正確：

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        f=set()
        f.add(0);s=0;ans=0
        for j in nums:
            s+=j
            if s-target in f:ans+=1;f=set()
            f.add(s)
        return ans

效能：

Runtime: 596 ms, faster than 95.24% of Python3 online submissions for Maximum Number of Non-Overlapping Subarrays With Sum Equals Target.
Memory Usage: 23.6 MB, less than 78.91% of Python3 online submissions for Maximum Number of Non-Overlapping Subarrays With Sum Equals Target.

看來這個理解是對的。

但是我有點擔心。以 nums = [-1,3,5,1,4,2,-9], target = 6 這個 input 為例，找到 [5,1] 這個 subarray 就一口氣把 [-1,3,5,1] 設定成不能再使用，找到[4,2] 這個 subarray 就加碼把 [4,2] 也設定成不能再使用。如果 nums 裡的元素順序調換，變成 [3,5,4,1,2,-9,-1]，那是不是會變成，找到 [5,1] 這個 subarray 就一口氣把 [3,5,4,1] 設定成不能再使用，所以就找不到 [4, 2] 這個組合了。

實驗看看，nums = [3,5,4,1,2,-9,-1], target = 6 這個 input，這個解是不是還能找到兩個 ans。input 如此設定後印出來的東西：

j: 3 f: {0: 1} s: 0
j: 5 f: {0: 1, 3: 1} s: 3
j: 4 f: {0: 1, 3: 1, 8: 1} s: 8
j: 1 f: {0: 1, 3: 1, 8: 1, 12: 1} s: 12
j: 2 f: {0: 1, 3: 1, 8: 1, 12: 1, 13: 1} s: 13
j: -9 f: {0: 1, 3: 1, 8: 1, 12: 1, 13: 1, 15: 1} s: 15
j: -1 f: {6: 1} s: 6
1

好吧，這樣他就只找得到一個 ans。不過他找到的時機跟我猜的不太一樣，他是在 for 迴圈迭代到 -9 的時候，因為 f 裡面有 0 這個 key 而找到 subarray [3,5,4,1,2,-9]。我本來是猜在 for 迴圈迭代到 1 的時候，因為 f 裡面有 7 這個 key 而找到 [5,1]，顯然我猜得太美了，因為他 f 的 key 是用 s 變數一路把 nums 的成員加起來而產生的，而 7 是由 3 + 4（跳過中間的 5）而來的，但他的 s 根本就不可能跳過 5。

只不過是把 list 的成員調換順序，就得到不一樣的 output，感覺這個解應該會被 reject 啊，但是卻 submit 成功了。要嘛是我誤會題目的意思，要嘛是這一題的測試案例還不夠好。

覺得關鍵應該是 non-overlapping subarray 是什麼意思。似乎不是「每個成員最多只能使用一次」這麼簡單。好像是

  • subarray 必須是連續的區間。例如，在 [1,2,3,4] 中，[1,2], [2,3,4] 都是連續的區間（不過有 overlap 了 2 這個成員），而 [1,3,4] 不是連續的區間（因為跳過了中間的 2）

所以，Input: [1,2,3,4], 8 的 Expected 才會是 0；而我把 list 的成員調換順序，就得到不一樣的 output。這樣一來，一切靈異現象就都說得通了。

難怪別人的解可以那麼短，原來我寫的，跟別人寫的，根本不是同一個題目⋯⋯

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