1004. Max Consecutive Ones III

leetcode medium

#array#csharp#leetcode#math#medium#sliding-window#two-pointers

Task

Если задан двоичный массив nums и целое число k, верните максимальное количество последовательных 1 в массиве, если можно перевернуть не более k 0.

Пример:

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2

Output: 6

C# solution

matched/original

public class Solution {
    public int LongestOnes(int[] nums, int k) {
        int left = 0, maxOnes = 0, zeroCount = 0;
        for (int right = 0; right < nums.Length; right++) {
            if (nums[right] == 0) {
                zeroCount++;
            }
            while (zeroCount > k) {
                if (nums[left] == 0) {
                    zeroCount--;
                }
                left++;
            }
            maxOnes = Math.Max(maxOnes, right - left + 1);
        }
        return maxOnes;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int LongestOnes(vector<int>& nums, int k) {
        int left = 0, maxOnes = 0, zeroCount = 0;
        for (int right = 0; right < nums.size(); right++) {
            if (nums[right] == 0) {
                zeroCount++;
            }
            while (zeroCount > k) {
                if (nums[left] == 0) {
                    zeroCount--;
                }
                left++;
            }
            maxOnes = max(maxOnes, right - left + 1);
        }
        return maxOnes;
    }
}

Java solution

matched/original

public class Solution {
    public int longestOnes(int[] nums, int k) {
        int left = 0, maxOnes = 0, zeroCount = 0;

        for (int right = 0; right < nums.length; right++) {
            if (nums[right] == 0) {
                zeroCount++;
            }

            while (zeroCount > k) {
                if (nums[left] == 0) {
                    zeroCount--;
                }
                left++;
            }

            maxOnes = Math.max(maxOnes, right - left + 1);
        }

        return maxOnes;
    }
}

Python solution

matched/original

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        left = 0
        max_ones = 0
        zero_count = 0

        for right in range(len(nums)):
            if nums[right] == 0:
                zero_count += 1

            while zero_count > k:
                if nums[left] == 0:
                    zero_count -= 1
                left += 1

            max_ones = max(max_ones, right - left + 1)

        return max_ones

Go solution

matched/original

func longestOnes(nums []int, k int) int {
    left, maxOnes, zeroCount := 0, 0, 0

    for right := 0; right < len(nums); right++ {
        if nums[right] == 0 {
            zeroCount++
        }

        while zeroCount > k {
            if nums[left] == 0 {
                zeroCount--
            }
            left++
        }

        maxOnes = max(maxOnes, right - left + 1)
    }

    return maxOnes
}

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

Explanation

Algorithm

Инициализация оконного подхода:

Используйте два указателя для создания скользящего окна. Инициализируйте левый указатель в начале массива, правый указатель будет двигаться по массиву. Создайте переменную для подсчета количества нулей в текущем окне.

Перемещение правого указателя и обновление окна:

Перемещайте правый указатель по массиву, обновляя количество нулей в текущем окне. Если количество нулей превышает k, сдвиньте левый указатель вправо до тех пор, пока количество нулей снова не станет допустимым (меньше или равно k).

Подсчет максимального количества последовательных единиц:

На каждом шаге обновляйте максимальное количество последовательных единиц, сравнивая текущую длину окна (разница между правым и левым указателями) с текущим максимумом.

😎