174 - 1004 最大连续1的个数3

https://leetcode-cn.com/problems/max-consecutive-ones-iii/solution/leetcode-485zui-da-lian-xu-1de-ge-shu-487zui-da-2/

这个大佬把我看不到的2的题目也写了，那么也来试一下吧

487 - 最大连续1的个数 2

题目

给定一个二进制数组，你可以最多将 1 个 0 翻转为 1，找出其中最大连续 1 的个数。

示例 1：

输入：[1,0,1,1,0] 输出：4 解释：翻转第一个 0 可以得到最长的连续 1。 当翻转以后，最大连续 1 的个数为 4。

注：

• 输入数组只包含 0 和 1.

• 输入数组的长度为正整数，且不超过 10,000

解答

动态规划

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        dp = [-1]*len(nums)
        if nums[0] == 1:
            dp[0] = 1
        else:
            dp[0] = 0

        count = 1
        for i in range(1, len(nums)):
            if nums[i] == 1:
                dp[i] = dp[i-1]+1
            else:
                if count != 0:
                    dp[i] = dp[i-1]+1
                    count -= 1
                else:
                    dp[i] = 0
        return max(dp)

滑动窗口

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        m, left, right = 0, 0, 0
        count = 1
        while right < len(nums):
            if nums[right] == 0:
                if count == 0:
                    while nums[left] == 1:
                        left += 1
                    left += 1
                else:
                    count -= 1
            m = (right-left+1) if (right-left+1) > m else m
            right += 1
        return m

题目

给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。

返回仅包含 1 的最长（连续）子数组的长度。

示例 1：

输入：A = [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，最长的子数组长度为 6。

示例 2：

输入：A = [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，最长的子数组长度为 10。

提示：

• 1 <= A.length <= 20000

• 0 <= K <= A.length

• A[i] 为 0 或 1

解答

滑动窗口

var longestOnes = function(A, K) {
  let i = 0,
    j = 0
  for (; j < A.length; j++) {
    if (A[j] === 0) {
      K--
    }
    if (K < 0 && A[i++] === 0) {
      K++
    }
  }
  return j - i
};

Runtime: 80 ms, faster than 76.74% of JavaScript online submissions for Max Consecutive Ones III.

Memory Usage: 37.7 MB, less than 100.00% of JavaScript online submissions for Max Consecutive Ones III.

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        i = 0
        for j in range(len(A)):
            K -= 1-A[j]
            if K < 0:
                K += 1-A[i]
                i += 1
        return j-i+1

Runtime: 616 ms, faster than 92.32% of Python3 online submissions for Max Consecutive Ones III.

Memory Usage: 13.1 MB, less than 100.00% of Python3 online submissions for Max Consecutive Ones III.