作者phoenixrace (残存亦陌路 兵败如山倒)
看板Prob_Solve
标题[问题] 面试写到的难题
时间Sun Sep 2 03:40:10 2018
最近写到的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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1535830812.A.E42.html
1F：推 peter506g: 直觉是可以用DP做到O(nk) 09/02 04:18
2F：推 ddavid: 直觉是先跑个O(n)把奇偶分开，奇数那边跑DP解出k个以下奇 09/02 04:23
3F：→ ddavid: 数所有可能，再接上偶数那边的所有可能性 09/02 04:24
4F：→ ddavid: 因为偶数那边的可能性数量可以统计好不同值的个数後组合公 09/02 04:25
5F：→ ddavid: 式解，所以实际上不需要暴力法处理，DP的部分也因为只需要 09/02 04:26
6F：→ ddavid: 知道种类数，因此也可以省去列出可能性的步骤 09/02 04:26
7F：→ ddavid: 等等不对，如果没要印出所有可能性只需要知道可能性总数的 09/02 04:27
8F：→ ddavid: 话，好像连DP都不需要嘛？ 09/02 04:28
这样可以避免duplicate subarray吗
9F：推 c225: Subarray 是原 array 里连续一段吗 09/02 05:28
是连续的
10F：推 DJWS: binary string / suffix array / lcp array 这样可以吗 09/02 05:52
11F：→ DJWS: sort all suffixes. for each suffix, count #(odd) until 09/02 05:55
12F：→ DJWS: reaching k. use lcp array to speed up. 09/02 05:56
13F：推 idiont: 应该可以O(n)求出符合的subarray数量 再利用lcp array减掉 09/02 06:39
14F：→ idiont: 重复的部分 时间复杂度取决suffix array的建构复杂度 最快 09/02 06:39
15F：→ idiont: 是O(n) 09/02 06:39
lcp是kmp里面那个longest prefix also suffix的那个? 假如是的话, 每一个suffix都要一个lcp?
16F：推 idiont: 把n个suffix排序後 两两相邻的最长共同前缀 就是lcp array 09/02 07:18
17F：推 DJWS: here is another method without lcp: 09/02 14:29
18F：→ DJWS: 1. prefix sum: fast get #(odd) for any interval [a,b]. 09/02 14:31
19F：→ DJWS: 2. for each suffix, binary search k, get its prefix. 09/02 14:32
20F：→ DJWS: 3. push all substrings into a trie. 09/02 14:33
21F：→ DJWS: 4. count number of the nodes of the trie. 全文完 09/02 14:34
感谢大家帮忙, 我之前的方法只会找所有的subarray, 可是不知道怎麽扣掉重复, 等等再把code更新一下, trie那个我等等也来试试看
22F：→ john2007: 输入[1,1,1,1] k = 1 跑出负数 应该不对吧? 09/02 17:00
23F：→ idiont: 我也有想到trie 不过复杂度应该是O(n^2)?还是能更快？ 09/02 17:32
24F：推 DJWS: sure. worst case O(n^2). n-k evens following by k odds. 09/02 17:49
25F：→ DJWS: followed 09/02 20:02
26F：推 ddavid: 傻了，原来是连续的，完全搞错题意XD 09/02 21:34
27F：推 kokal: 试了一下, len(common_prefix)会把[1,1,1],[1,1]*2都算入 09/02 21:43
28F：推 kokal: 输入是[1,1,1,1] k=1 09/02 21:45
对欸, 稍微更新一下找common prefix的逻辑了, 感谢
※ 编辑: phoenixrace (24.251.153.7), 09/03/2018 01:10:24
29F：推 FRAXIS: 建一个 suffix tree 然後作 tree traversal? 09/03 05:15
30F：推 DJWS: 楼上一句话就讲完了 XD 毕竟n=1000应该可以换成suffix trie 09/03 07:18
31F：推 powertodream: 请问suffix array 是指用甚麽部分建的? 09/03 11:24
32F：推 powertodream: 大概理解, suffix array是甚麽, 不过不太理解怎麽 09/03 11:40
33F：→ powertodream: 用它来加速找出odd count subarray 09/03 11:40
34F：推 powertodream: 理解上, 是不是假如建成suffix trie, 每个tree node 09/03 11:46
35F：→ powertodream: 有count, tree traversal 在odd count <k 就把tree 09/03 11:47
36F：→ powertodream: node count 加到ans? 09/03 11:47
37F：→ powertodream: 不太了解, prefix sum, binary search k 的动作@@" 09/03 11:48
38F：→ powertodream: 这是加速建suffix array的做法吗? 09/03 11:48
39F：推 powertodream: 唔 如果是distinct array, 那好像treenode不用count 09/03 12:02
40F：推 powertodream: google一下 发现我把suffix array跟suffix trie搞混 09/03 17:04
41F：→ powertodream: 一直以为先有suffix array 再建立 suffix trie 09/03 17:05
42F：→ powertodream: 不过好像有O(N)的做法可以把 suffix trie建起来 09/03 17:08
43F：推 JameC: size 才1000，暴力解+string hashing +map 感觉可以 09/22 19:51
44F：推 JameC: 猜不太到为什麽楼主的O(n^2)过不了...就当我随便说说吧lol 09/22 19:52
45F：→ oToToT: 单纯猜python太慢吧 09/22 23:46
46F：推 rareone: 简单双指标就可以做到O(N) 01/06 18:21