算法题/滑动窗口：一次替换后的最长子数组长度

题目

给定一个包含数个0和1的数组，允许用1替换不超过k个0，找出全部都是1的最长连续子数组的长度。

示例1：

输入：Array=[0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1], k=2
输出：6
解释：替换索引位置为5和8处的0

示例2：

输入：Array=[0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1], k=3
输出：9
解释：替换索引位置6, 9, 10处的0

解答1：

Java

class ReplacingOnes {
  public static int findLength(int[] arr, int k) {
    int windowStart = 0, maxLength = 0, maxOnesCount = 0;
    // 扩大范围[windowStart, windowEnd]
    for (int windowEnd = 0; windowEnd < arr.length; windowEnd++) {
      if (arr[windowEnd] == 1)
        maxOnesCount++;

      if (windowEnd - windowStart + 1 - maxOnesCount > k) {
        if (arr[windowStart] == 1)
          maxOnesCount--;
        windowStart++;
      }

      maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
    }

    return maxLength;
  }

  public static void main(String[] args) {
    System.out.println(ReplacingOnes.findLength(new int[] { 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1 }, 2));
    System.out.println(ReplacingOnes.findLength(new int[] { 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1 }, 3));
  }
}

JavaScript

class ReplacingOnes {
  static findLength(arr, k) {
    let windowStart = 0,
      maxLength = 0,
      maxOnesCount = 0;

    for (let windowEnd = 0; windowEnd < arr.length; windowEnd++) {
      if (arr[windowEnd] === 1)
        maxOnesCount++;

      if (windowEnd - windowStart + 1 - maxOnesCount > k) {
        if (arr[windowStart] === 1)
          maxOnesCount--;
        windowStart++;
      }

      maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
    }

    return maxLength;
  }
}

console.log(ReplacingOnes.findLength([0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1], 2));
console.log(ReplacingOnes.findLength([0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1], 3));

Python

class ReplacingOnes:
    def findLength(arr, k):
        windowStart = 0
        maxLength = 0
        maxOnesCount = 0

        for windowEnd in range(len(arr)):
            if arr[windowEnd] == 1:
                maxOnesCount += 1

            if windowEnd - windowStart + 1 - maxOnesCount > k:
                if arr[windowStart] == 1:
                    maxOnesCount -= 1
                windowStart += 1

            maxLength = max(maxLength, windowEnd - windowStart + 1)

        return maxLength


print(ReplacingOnes.findLength([0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1], 2))
print(ReplacingOnes.findLength([0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1], 3))

Go

package main

import (
	"fmt"
)

func findLength(arr []int, k int) int {
	windowStart := 0
	maxLength := 0
	maxOnesCount := 0

	for windowEnd := 0; windowEnd < len(arr); windowEnd++ {
		if arr[windowEnd] == 1 {
			maxOnesCount++
		}

		if windowEnd-windowStart+1-maxOnesCount > k {
			if arr[windowStart] == 1 {
				maxOnesCount--
			}
			windowStart++
		}

		maxLength = max(maxLength, windowEnd-windowStart+1)
	}

	return maxLength
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	fmt.Println(findLength([]int{0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1}, 2))
	fmt.Println(findLength([]int{0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0,