最近写到的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)