PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] 面試寫到的難題 (Solved)

看板Prob_Solve (計算數學 Problem Solving)作者 (殘存亦陌路 兵敗如山倒)時間5年前 (2018/09/02 03:40), 5年前編輯推噓21(21推 0噓 25→)
留言46則, 12人參與, 6年前最新討論串1/1
最近寫到的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),這樣就可以了 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 24.251.153.7 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1535830812.A.E42.html
推
09/02 04:18, 5年前 , 1F
直覺是可以用DP做到O(nk)
09/02 04:18, 1F
推
09/02 04:23, 5年前 , 2F
直覺是先跑個O(n)把奇偶分開，奇數那邊跑DP解出k個以下奇
09/02 04:23, 2F
→
09/02 04:24, 5年前 , 3F
數所有可能，再接上偶數那邊的所有可能性
09/02 04:24, 3F
→
09/02 04:25, 5年前 , 4F
因為偶數那邊的可能性數量可以統計好不同值的個數後組合公
09/02 04:25, 4F
→
09/02 04:26, 5年前 , 5F
式解，所以實際上不需要暴力法處理，DP的部分也因為只需要
09/02 04:26, 5F
→
09/02 04:26, 5年前 , 6F
知道種類數，因此也可以省去列出可能性的步驟
09/02 04:26, 6F
→
09/02 04:27, 5年前 , 7F
等等不對，如果沒要印出所有可能性只需要知道可能性總數的
09/02 04:27, 7F
→
09/02 04:28, 5年前 , 8F
話，好像連DP都不需要嘛？
09/02 04:28, 8F
這樣可以避免duplicate subarray嗎
推
09/02 05:28, 5年前 , 9F
Subarray 是原 array 裡連續一段嗎
09/02 05:28, 9F
是連續的
推
09/02 05:52, 5年前 , 10F
binary string / suffix array / lcp array 這樣可以嗎
09/02 05:52, 10F
→
09/02 05:55, 5年前 , 11F
sort all suffixes. for each suffix, count #(odd) until
09/02 05:55, 11F
→
09/02 05:56, 5年前 , 12F
reaching k. use lcp array to speed up.
09/02 05:56, 12F
推
09/02 06:39, 5年前 , 13F
應該可以O(n)求出符合的subarray數量 再利用lcp array減掉
09/02 06:39, 13F
→
09/02 06:39, 5年前 , 14F
重複的部分 時間複雜度取決suffix array的建構複雜度 最快
09/02 06:39, 14F
→
09/02 06:39, 5年前 , 15F
是O(n)
09/02 06:39, 15F
lcp是kmp裡面那個longest prefix also suffix的那個? 假如是的話, 每一個suffix都要一個lcp?
推
09/02 07:18, 5年前 , 16F
把n個suffix排序後 兩兩相鄰的最長共同前綴 就是lcp array
09/02 07:18, 16F
推
09/02 14:29, 5年前 , 17F
here is another method without lcp:
09/02 14:29, 17F
→
09/02 14:31, 5年前 , 18F
1. prefix sum: fast get #(odd) for any interval [a,b].
09/02 14:31, 18F
→
09/02 14:32, 5年前 , 19F
2. for each suffix, binary search k, get its prefix.
09/02 14:32, 19F
→
09/02 14:33, 5年前 , 20F
3. push all substrings into a trie.
09/02 14:33, 20F
→
09/02 14:34, 5年前 , 21F
4. count number of the nodes of the trie. 全文完
09/02 14:34, 21F
感謝大家幫忙, 我之前的方法只會找所有的subarray, 可是不知道怎麼扣掉重複, 等等再把code更新一下, trie那個我等等也來試試看
→
09/02 17:00, 5年前 , 22F
輸入[1,1,1,1] k = 1 跑出負數 應該不對吧?
09/02 17:00, 22F
→
09/02 17:32, 5年前 , 23F
我也有想到trie 不過複雜度應該是O(n^2)?還是能更快？
09/02 17:32, 23F
推
09/02 17:49, 5年前 , 24F
sure. worst case O(n^2). n-k evens following by k odds.
09/02 17:49, 24F
→
09/02 20:02, 5年前 , 25F
followed
09/02 20:02, 25F
推
09/02 21:34, 5年前 , 26F
傻了，原來是連續的，完全搞錯題意XD
09/02 21:34, 26F
推
09/02 21:43, 5年前 , 27F
試了一下, len(common_prefix)會把[1,1,1],[1,1]*2都算入
09/02 21:43, 27F
推
09/02 21:45, 5年前 , 28F
輸入是[1,1,1,1] k=1
09/02 21:45, 28F
對欸, 稍微更新一下找common prefix的邏輯了, 感謝 ※ 編輯: phoenixrace (24.251.153.7), 09/03/2018 01:10:24
推
09/03 05:15, 5年前 , 29F
建一個 suffix tree 然後作 tree traversal?
09/03 05:15, 29F
推
09/03 07:18, 5年前 , 30F
樓上一句話就講完了 XD 畢竟n=1000應該可以換成suffix trie
09/03 07:18, 30F
推
09/03 11:24, 5年前 , 31F
請問suffix array 是指用甚麼部分建的?
09/03 11:24, 31F
推
09/03 11:40, 5年前 , 32F
大概理解, suffix array是甚麼, 不過不太理解怎麼
09/03 11:40, 32F
→
09/03 11:40, 5年前 , 33F
用它來加速找出odd count subarray
09/03 11:40, 33F
推
09/03 11:46, 5年前 , 34F
理解上, 是不是假如建成suffix trie, 每個tree node
09/03 11:46, 34F
→
09/03 11:47, 5年前 , 35F
有count, tree traversal 在odd count <k 就把tree
09/03 11:47, 35F
→
09/03 11:47, 5年前 , 36F
node count 加到ans?
09/03 11:47, 36F
→
09/03 11:48, 5年前 , 37F
不太了解, prefix sum, binary search k 的動作@@"
09/03 11:48, 37F
→
09/03 11:48, 5年前 , 38F
這是加速建suffix array的做法嗎?
09/03 11:48, 38F
推
09/03 12:02, 5年前 , 39F
唔 如果是distinct array, 那好像treenode不用count
09/03 12:02, 39F
推
09/03 17:04, 5年前 , 40F
google一下 發現我把suffix array跟suffix trie搞混
09/03 17:04, 40F
→
09/03 17:05, 5年前 , 41F
一直以為先有suffix array 再建立 suffix trie
09/03 17:05, 41F
→
09/03 17:08, 5年前 , 42F
不過好像有O(N)的做法可以把 suffix trie建起來
09/03 17:08, 42F
推
09/22 19:51, 5年前 , 43F
size 才1000，暴力解+string hashing +map 感覺可以
09/22 19:51, 43F
推
09/22 19:52, 5年前 , 44F
猜不太到為什麼樓主的O(n^2)過不了...就當我隨便說說吧lol
09/22 19:52, 44F
→
09/22 23:46, 5年前 , 45F
單純猜python太慢吧
09/22 23:46, 45F
推
01/06 18:21, 6年前 , 46F
簡單雙指標就可以做到O(N)
01/06 18:21, 46F
‣ 更多 phoenixrace 的文章
文章代碼(AID): #1RYkiSv2 (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 phoenixrace 的文章
文章代碼(AID): #1RYkiSv2 (Prob_Solve)