PTT數位生活區 / C_and_CPP (C/C++)

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

看板C_and_CPP (C/C++)作者 (殘存亦陌路 兵敗如山倒)時間7年前 (2018/09/02 02:40), 7年前編輯推噓7(7推 0噓 19→)
留言26則, 9人參與, 7年前最新討論串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~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
推
09/02 03:01, 7年前 , 1F
要連續？
09/02 03:01, 1F
→
09/02 03:01, 7年前 , 2F
然後我覺得會被叫去problem solve板
09/02 03:01, 2F
→
09/02 03:38, 7年前 , 3F
sub array的定義是連續的array
09/02 03:38, 3F
→
09/02 03:38, 7年前 , 4F
感謝 我應該去那個板問的
09/02 03:38, 4F
→
09/02 04:01, 7年前 , 5F
範例二是回傳6吧 1 2 3不算一種解嗎?
09/02 04:01, 5F
→
09/02 04:09, 7年前 , 6F
如果是找sybarray數量 範例2的兩個1 應該要分開看?
09/02 04:09, 6F
→
09/02 04:36, 7年前 , 7F
用有點變化的前綴和配二分搜應該可以nlogn解出來
09/02 04:36, 7F
※ 編輯: phoenixrace (129.219.21.3), 09/02/2018 05:21:09
→
09/02 05:21, 7年前 , 8F
[1, 2, 3]也算 抱歉忽略了
09/02 05:21, 8F
→
09/02 05:30, 7年前 , 9F
應該還有[1 2]跟[3]吧
09/02 05:30, 9F
感謝 已修改了 ※ 編輯: phoenixrace (129.219.21.3), 09/02/2018 05:41:40
推
09/02 11:02, 7年前 , 10F
先把array刷一次然後分成奇數跟偶數
09/02 11:02, 10F
→
09/02 11:02, 7年前 , 11F
然後用排列組合相乘就求出來了
09/02 11:02, 11F
→
09/02 11:03, 7年前 , 12F
應該可以再O(n)解決
09/02 11:03, 12F
→
09/02 11:03, 7年前 , 13F
我沒試過 但直覺這樣是對的
09/02 11:03, 13F
推
09/02 11:06, 7年前 , 14F
抱歉沒看到最多k個奇數 所以應該是O(n+k)
09/02 11:06, 14F
推
09/02 11:27, 7年前 , 15F
第二個為例，數學模型應該是（x^0+x^1+x^2)(x^0+x^1)(x^0+x
09/02 11:27, 15F
→
09/02 11:27, 7年前 , 16F
^1)的係數和，但因為條件是奇數，所以要先算出一三個括弧x
09/02 11:27, 16F
→
09/02 11:27, 7年前 , 17F
次方小於k的係數和，那只需要做一些多項式運算，不知道這
09/02 11:27, 17F
→
09/02 11:27, 7年前 , 18F
樣的方法有沒有比較快？
09/02 11:27, 18F
→
09/02 12:17, 7年前 , 19F
如果相同pattern視為一種感覺滿困難的 可以請教n平方的
09/02 12:17, 19F
→
09/02 12:17, 7年前 , 20F
方法嗎
09/02 12:17, 20F
推
09/02 14:43, 7年前 , 21F
這個應該都是用back tracking的技巧來寫吧
09/02 14:43, 21F
在Prob_solv板, 有人教我怎麼扣掉重複的subarray了, 我在那裡有更新程式碼了 ※ 編輯: phoenixrace (24.251.153.7), 09/02/2018 15:38:15
推
09/02 15:38, 7年前 , 22F
應該可以用two pointer維護區間奇數值 時間O(n)
09/02 15:38, 22F
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
→
09/02 15:41, 7年前 , 23F
ㄜ 沒看到不能重複 當我沒說吧
09/02 15:41, 23F
推
09/02 23:45, 7年前 , 24F
我覺得應該用segment tree可以解吧 keep每個區間的奇
09/02 23:45, 24F
→
09/02 23:45, 7年前 , 25F
數數量 O(nlgn)
09/02 23:45, 25F
→
09/02 23:46, 7年前 , 26F
啊 想了一下應該On 就可以 抱歉耍蠢了
09/02 23:46, 26F
‣ 更多 phoenixrace 的文章
文章代碼(AID): #1RYjq5kU (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 phoenixrace 的文章
文章代碼(AID): #1RYjq5kU (C_and_CPP)