ETH官方钱包

前往
大廳
主題

LeetCode - 1004. Max Consecutive Ones III 解題心得

Not In My Back Yard | 2021-10-20 00:00:06 | 巴幣 100 | 人氣 424

題目連結:


題目意譯:
給定一個二元陣列 nums 以及一整數 k,回傳如果你能翻轉最多 k 個 0 的話陣列中最大的連續 1 之數量。

限制:
1 ≦ nums.length ≦ 10 ^ 5
nums[i] 只會是 0 或 1。
0 ≦ k ≦ nums.length



範例測資:
範例 1:
輸入: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
輸出: 6
解釋: [1,1,1,0,0,1,1,1,1,1,1]
粗體數字代表從 0 翻轉為 1。最長的子陣列以底線標示。

範例 2:
輸入: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
輸出: 10
解釋: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗體數字代表從 0 翻轉為 1。最長的子陣列以底線標示。


解題思維:
基於這題找連續 1 的長度。

但是當我們遇到 0 的時候我們可以選擇將其變成 1(只要目前已操作數不為 k)。而我們可以看到這些操作應盡量聚在一起(也就是被變化的 0 應盡量靠近彼此)才能使連續 1 盡量地長。

當我們已經變過 k 個 0 為 1 時,此時可以把最久遠一次的操作取消掉,改為變化當前位置的 0。

然後看上述過程中最長的連續 1 之長度即為所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作