作者phoenixrace (残存亦陌路 兵败如山倒)
看板C_and_CPP
标题[问题] 最近面试写到的题目
时间Sun Sep 2 02:40:02 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~n之间
我的解法是暴力解O(n^2),可是有些testcase会超时, 不知道有没有O(n)还是O(nlogn)解法的
更新1:
要求是distinct subarray, 所以范例2 会有两个array [1], [1], 这样算一组
更新2:
范例2有错更新一下
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 24.251.153.7
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1535827205.A.B9E.html
1F：推 a29022792: 要连续？ 09/02 03:01
2F：→ a29022792: 然後我觉得会被叫去problem solve板 09/02 03:01
3F：→ phoenixrace: sub array的定义是连续的array 09/02 03:38
4F：→ phoenixrace: 感谢 我应该去那个板问的 09/02 03:38
5F：→ john2007: 范例二是回传6吧 1 2 3不算一种解吗? 09/02 04:01
6F：→ john2007: 如果是找sybarray数量 范例2的两个1 应该要分开看? 09/02 04:09
7F：→ john2007: 用有点变化的前缀和配二分搜应该可以nlogn解出来 09/02 04:36
※ 编辑: phoenixrace (129.219.21.3), 09/02/2018 05:21:09
8F：→ phoenixrace: [1, 2, 3]也算 抱歉忽略了 09/02 05:21
9F：→ idiont: 应该还有[1 2]跟[3]吧 09/02 05:30
感谢 已修改了
※ 编辑: phoenixrace (129.219.21.3), 09/02/2018 05:41:40
10F：推 sunflower304: 先把array刷一次然後分成奇数跟偶数 09/02 11:02
11F：→ sunflower304: 然後用排列组合相乘就求出来了 09/02 11:02
12F：→ sunflower304: 应该可以再O(n)解决 09/02 11:03
13F：→ sunflower304: 我没试过 但直觉这样是对的 09/02 11:03
14F：推 sunflower304: 抱歉没看到最多k个奇数 所以应该是O(n+k) 09/02 11:06
15F：推 a159a: 第二个为例，数学模型应该是（x^0+x^1+x^2)(x^0+x^1)(x^0+x 09/02 11:27
16F：→ a159a: ^1)的系数和，但因为条件是奇数，所以要先算出一三个括弧x 09/02 11:27
17F：→ a159a: 次方小於k的系数和，那只需要做一些多项式运算，不知道这 09/02 11:27
18F：→ a159a: 样的方法有没有比较快？ 09/02 11:27
19F：→ john2007: 如果相同pattern视为一种感觉满困难的 可以请教n平方的 09/02 12:17
20F：→ john2007: 方法吗 09/02 12:17
21F：推 Sirctal: 这个应该都是用back tracking的技巧来写吧 09/02 14:43
在Prob_solv板, 有人教我怎麽扣掉重复的subarray了, 我在那里有更新程式码了
※ 编辑: phoenixrace (24.251.153.7), 09/02/2018 15:38:15
22F：推 ga544523: 应该可以用two pointer维护区间奇数值 时间O(n) 09/02 15:38
Yes, the only thing I don't know is how to remove the duplicate arrays. Some people in the Prob_solv told me how to do that!!
※ 编辑: phoenixrace (24.251.153.7), 09/02/2018 15:41:07
23F：→ ga544523: ㄜ 没看到不能重复 当我没说吧 09/02 15:41
24F：推 bill1992: 我觉得应该用segment tree可以解吧 keep每个区间的奇 09/02 23:45
25F：→ bill1992: 数数量 O(nlgn) 09/02 23:45
26F：→ bill1992: 啊 想了一下应该On 就可以 抱歉耍蠢了 09/02 23:46