[問題] 最近面試寫到的題目

[phoenixrace (殘存亦陌路 兵敗如山倒)]

最近寫到的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://www.ptt.cc/bbs/C_and_CPP/M.1535827205.A.B9E.html
推 a29022792: 要連續？
→ a29022792: 然後我覺得會被叫去problem solve板
→ phoenixrace: sub array的定義是連續的array
→ phoenixrace: 感謝 我應該去那個板問的
→ john2007: 範例二是回傳6吧 1 2 3不算一種解嗎?
→ john2007: 如果是找sybarray數量 範例2的兩個1 應該要分開看?
→ john2007: 用有點變化的前綴和配二分搜應該可以nlogn解出來
※ 編輯: phoenixrace (129.219.21.3), 09/02/2018 05:21:09
→ phoenixrace: [1, 2, 3]也算 抱歉忽略了
→ idiont: 應該還有[1 2]跟[3]吧
感謝 已修改了
※ 編輯: phoenixrace (129.219.21.3), 09/02/2018 05:41:40
推 sunflower304: 先把array刷一次然後分成奇數跟偶數
→ sunflower304: 然後用排列組合相乘就求出來了
→ sunflower304: 應該可以再O(n)解決
→ sunflower304: 我沒試過 但直覺這樣是對的
推 sunflower304: 抱歉沒看到最多k個奇數 所以應該是O(n+k)
推 a159a: 第二個為例，數學模型應該是（x^0+x^1+x^2)(x^0+x^1)(x^0+x
→ a159a: ^1)的係數和，但因為條件是奇數，所以要先算出一三個括弧x
→ a159a: 次方小於k的係數和，那只需要做一些多項式運算，不知道這
→ a159a: 樣的方法有沒有比較快？
→ john2007: 如果相同pattern視為一種感覺滿困難的 可以請教n平方的
→ john2007: 方法嗎
推 Sirctal: 這個應該都是用back tracking的技巧來寫吧
在Prob_solv板, 有人教我怎麼扣掉重複的subarray了, 我在那裡有更新程式碼了
※ 編輯: phoenixrace (24.251.153.7), 09/02/2018 15:38:15
推 ga544523: 應該可以用two pointer維護區間奇數值 時間O(n)
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
→ ga544523: ㄜ 沒看到不能重複 當我沒說吧
推 bill1992: 我覺得應該用segment tree可以解吧   keep每個區間的奇
→ bill1992: 數數量  O(nlgn)
→ bill1992: 啊  想了一下應該On 就可以  抱歉耍蠢了