最近寫到的OA題目, 可是有testcase超時, 不知道有沒有人有啥想法
題目:
有一個array, 你要找出所有不同subarray的數量, 每個sub arrays最多包含k個奇數數字.
範例 1:
array = [1, 2, 3, 4] & k = 1
總個會有[1], [2], [3], [4], [1, 2], [2, 3], [3, 4], [2, 3, 4]這八種, 要return 8
範例 2:
array = [1, 1, 2, 3] & k = 2
會有[1], [1, 1], [1, 1, 2], [1, 2], [2], [2, 3], [3], [1, 2, 3] 要return 8種
p.s
array不是sorted的
array的size在1~1000之間
我的解法是暴力解O(n^2),可是有些testcase會超時, 不知道有沒有O(n)還是O(nlogn)解
法的
更新1:
範例2, 會有兩組[1], [1], 但要求是distinct subarray, 所以 [1], [1]算一組
更新2:
subarray是原本array連續的部分.
更新3:
範例2有錯, 已經修改了
更新4:
用了suffix arrays sorted的方法,array大小是1000的時候耗時0.02s, brute force是5.6s
感謝大家幫忙
更新5:
https://repl.it/@Lancer_Liou/BrilliantCurvyBrain
之前的code [1, 1, 1, 1]會多扣掉一些, 真正的要減掉的應該是 number of deduct arrays = min(longest common prefix, the length of the longest string which contain at most k odd num),這樣就可以了

直覺是可以用DP做到O(nk)

直覺是先跑個O(n)把奇偶分開，奇數那邊跑DP解出k個以下奇數所有可能，再接上偶數那邊的所有可能性因為偶數那邊的可能性數量可以統計好不同值的個數後組合公式解，所以實際上不需要暴力法處理，DP的部分也因為只需要知道種類數，因此也可以省去列出可能性的步驟等等不對，如果沒要印出所有可能性只需要知道可能性總數的話，好像連DP都不需要嘛？

Subarray 是原 array 裡連續一段嗎

是連續的

binary string / suffix array / lcp array 這樣可以嗎sort all suffixes. for each suffix, count #(odd) untilreaching k. use lcp array to speed up.

應該可以O(n)求出符合的subarray數量 再利用lcp array減掉重複的部分 時間複雜度取決suffix array的建構複雜度 最快是O(n)把n個suffix排序後 兩兩相鄰的最長共同前綴 就是lcp array

here is another method without lcp:1. prefix sum: fast get #(odd) for any interval [a,b].2. for each suffix, binary search k, get its prefix.3. push all substrings into a trie.4. count number of the nodes of the trie. 全文完

輸入[1,1,1,1] k = 1 跑出負數 應該不對吧?

我也有想到trie 不過複雜度應該是O(n^2)?還是能更快？

sure. worst case O(n^2). n-k evens following by k odds.followed

傻了，原來是連續的，完全搞錯題意XD

試了一下, len(common_prefix)會把[1,1,1],[1,1]*2都算入輸入是[1,1,1,1] k=1

建一個 suffix tree 然後作 tree traversal?

樓上一句話就講完了 XD 畢竟n=1000應該可以換成suffix trie

請問suffix array 是指用甚麼部分建的?大概理解, suffix array是甚麼, 不過不太理解怎麼用它來加速找出odd count subarray理解上, 是不是假如建成suffix trie, 每個tree node有count, tree traversal 在odd count <k 就把treenode count 加到ans?不太了解, prefix sum, binary search k 的動作@@"這是加速建suffix array的做法嗎?唔 如果是distinct array, 那好像treenode不用countgoogle一下 發現我把suffix array跟suffix trie搞混一直以為先有suffix array 再建立 suffix trie不過好像有O(N)的做法可以把 suffix trie建起來

size 才1000，暴力解+string hashing +map 感覺可以猜不太到為什麼樓主的O(n^2)過不了...就當我隨便說說吧lol

單純猜python太慢吧

直覺是可以用DP做到O(nk)

直覺是先跑個O(n)把奇偶分開，奇數那邊跑DP解出k個以下奇數所有可能，再接上偶數那邊的所有可能性因為偶數那邊的可能性數量可以統計好不同值的個數後組合公式解，所以實際上不需要暴力法處理，DP的部分也因為只需要知道種類數，因此也可以省去列出可能性的步驟等等不對，如果沒要印出所有可能性只需要知道可能性總數的話，好像連DP都不需要嘛？

Subarray 是原 array 裡連續一段嗎

binary string / suffix array / lcp array 這樣可以嗎sort all suffixes. for each suffix, count #(odd) untilreaching k. use lcp array to speed up.

應該可以O(n)求出符合的subarray數量 再利用lcp array減掉重複的部分 時間複雜度取決suffix array的建構複雜度 最快是O(n)把n個suffix排序後 兩兩相鄰的最長共同前綴 就是lcp array

here is another method without lcp:1. prefix sum: fast get #(odd) for any interval [a,b].2. for each suffix, binary search k, get its prefix.3. push all substrings into a trie.4. count number of the nodes of the trie. 全文完

輸入[1,1,1,1] k = 1 跑出負數 應該不對吧?

我也有想到trie 不過複雜度應該是O(n^2)?還是能更快？

sure. worst case O(n^2). n-k evens following by k odds.followed

傻了，原來是連續的，完全搞錯題意XD

試了一下, len(common_prefix)會把[1,1,1],[1,1]*2都算入輸入是[1,1,1,1] k=1

建一個 suffix tree 然後作 tree traversal?

樓上一句話就講完了 XD 畢竟n=1000應該可以換成suffix trie

請問suffix array 是指用甚麼部分建的?大概理解, suffix array是甚麼, 不過不太理解怎麼用它來加速找出odd count subarray理解上, 是不是假如建成suffix trie, 每個tree node有count, tree traversal 在odd count <k 就把treenode count 加到ans?不太了解, prefix sum, binary search k 的動作@@"這是加速建suffix array的做法嗎?唔 如果是distinct array, 那好像treenode不用countgoogle一下 發現我把suffix array跟suffix trie搞混一直以為先有suffix array 再建立 suffix trie不過好像有O(N)的做法可以把 suffix trie建起來

size 才1000，暴力解+string hashing +map 感覺可以猜不太到為什麼樓主的O(n^2)過不了...就當我隨便說說吧lol

單純猜python太慢吧

簡單雙指標就可以做到O(N)