题目如下:
Given an array A of 0s and 1s, we may change up to K values from 0 to 1.
- Return the length of the longest (contiguous) subarray that contains only 1s.
- Example 1:
- Input: A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
- Output: 6
- Explanation:
- [1,1,1,0,0,1,1,1,1,1,1]
- Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
- Example 2:
- Input: A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
- Output: 10
- Explanation:
- [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
- Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
- Note:
- 1 <= A.length <= 20000
- 0 <= K <= A.length
- A[i] is 0 or 1
解题思路: 如果我们把所有 0 所在位置对应的下标存入一个数组 inx_0 中, 例如 Example 2 的 inx_0 = [0,1,4,5,9,12,13,14], 因为最多把 K 个 0 变成 1, 要构造出最长的全为 1 的连续子数组, 那么很显然所有进行反转操作的 0 所对应下标在 inx_0 中必须是连续的. 接下来开始遍历数组 A, 在 K 大于 0 的条件下, 遇到 1 则 count_1 加 1, 遇到 0 的话则 K 减 1 并且 count_1 加 1(表示这个 0 反转成 1); 如果在 K=0 的情况下遇到 0, 那么需要去掉第一个 0 变成的 1 和这个 0 之前连续的 1 的数量, 即 count 减 1(减去第一个 0 变成 1 的计数), 再减去第一个 0 前面连续的 1 的数量 i, 记为 count_1 减 i. 记录 count_1 出现的最大值, 直到数组 A 遍历完成为止.
代码如下:
- class Solution(object):
- def longestOnes(self, A, K):
- """
- :type A: List[int]
- :type K: int
- :rtype: int
- """
- count_1 = 0
- zero_inx = []
- res = 0
- zero_before = -1
- for i in range(len(A)):
- if A[i] == 1:
- count_1 += 1
- else:
- zero_inx.append(i)
- if K> 0:
- K -= 1
- count_1 += 1
- elif K == 0:
- res = max(res,count_1)
- first_0 = zero_inx.pop(0)
- count_1 -= (first_0 - zero_before - 1)
- zero_before = first_0
- res = max(res, count_1)
- return res
来源: http://www.bubuko.com/infodetail-2975340.html