[問題] 最長的連續假期

作者: stdlib (我是新手)   2018-11-19 04:44:04
Q: 給定一個 bool array,0代表放假日,1代表要上班
以及給一個年假天數 v,試求出請了 v 天假後,最長的連續假期天數為何
Example:
Input: {1, 0, 0, 1, 1, 0, 0, 1, 1} ; v=2
Output: 6,請了 2 天假之後 (把 1 標成 0),
陣列會變成 {1, 0, 0, 0, 0, 0, 0, 1, 1},有 6 個連續的 0。
Input: {0, 1, 1, 0, 1, 0, 1, 1, 1, 0} ; v=3
Output: 6,把前 3 個 1 標成 0,
陣列會變成 {0, 0, 0, 0, 0, 0, 1, 1, 1, 0},有 6 個連續的 0。
感謝各位大神
作者: s89162504 (阿本)   2018-11-19 17:03:00
相當於求 連續和為v的最長陣列 對吧!?簡單用個two pointer就行了吧如果目前連續和比v小就head往前走如果連續和超過v就tail往前y
作者: cutekid (可愛小孩子)   2018-11-19 19:21:00
推樓上 s 大,超過 v 時,tail往前直到遇到 1 為止
作者: HanaYukii (ShioRin)   2018-12-03 14:39:00
每個起點二分搜

Links booklink

Contact Us: admin [ a t ] ucptt.com