← Static tasks

487. Max Consecutive Ones II

leetcode medium

#array#csharp#leetcode#math#medium#search#two-pointers

Task

Дан бинарный массив nums, верните максимальное количество последовательных единиц в массиве, если можно перевернуть не более одного нуля.

Пример:

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

Output: 4

Explanation:

- If we flip the first zero, nums becomes [1,1,1,1,0] and we have 4 consecutive ones.

- If we flip the second zero, nums becomes [1,0,1,1,1] and we have 3 consecutive ones.

The max number of consecutive ones is 4.

C# solution

matched/original
public class Solution {
    public int FindMaxConsecutiveOnes(int[] nums) {
        int longestSequence = 0;
        for (int left = 0; left < nums.Length; left++) {
            int numZeroes = 0;
            for (int right = left; right < nums.Length; right++) {
                if (nums[right] == 0) {
                    numZeroes++;
                }
                if (numZeroes <= 1) {
                    longestSequence = Math.Max(longestSequence, right - left + 1);
                }
            }
        }
        return longestSequence;
    }
}

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 FindMaxConsecutiveOnes(vector<int>& nums) {
        int longestSequence = 0;
        for (int left = 0; left < nums.size(); left++) {
            int numZeroes = 0;
            for (int right = left; right < nums.size(); right++) {
                if (nums[right] == 0) {
                    numZeroes++;
                }
                if (numZeroes <= 1) {
                    longestSequence = max(longestSequence, right - left + 1);
                }
            }
        }
        return longestSequence;
    }
}

Java solution

matched/original
class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int longestSequence = 0;
        for (int left = 0; left < nums.length; left++) {
            int numZeroes = 0;

            for (int right = left; right < nums.length; right++) {
                if (nums[right] == 0) {
                    numZeroes += 1;
                }
                if (numZeroes <= 1) {
                    longestSequence = Math.max(longestSequence, right - left + 1);
                }
            }
        }
        return longestSequence;
    }
}

JavaScript solution

matched/original
class Solution {
    findMaxConsecutiveOnes(nums) {
        let longestSequence = 0;
        for (let left = 0; left < nums.length; left++) {
            let numZeroes = 0;
            for (let right = left; right < nums.length; right++) {
                if (nums[right] === 0) {
                    numZeroes++;
                }
                if (numZeroes <= 1) {
                    longestSequence = Math.max(longestSequence, right - left + 1);
                }
            }
        }
        return longestSequence;
    }
}

Python solution

matched/original
class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        longestSequence = 0
        for left in range(len(nums)):
            numZeroes = 0
            for right in range(left, len(nums)):
                if nums[right] == 0:
                    numZeroes += 1
                if numZeroes <= 1:
                    longestSequence = max(longestSequence, right - left + 1)
        return longestSequence

Go solution

matched/original
func findMaxConsecutiveOnes(nums []int) int {
    longestSequence := 0
    for left := 0; left < len(nums); left++ {
        numZeroes := 0
        for right := left; right < len(nums); right++ {
            if nums[right] == 0 {
                numZeroes++
            }
            if numZeroes <= 1 {
                longestSequence = max(longestSequence, right - left + 1)
            }
        }
    }
    return longestSequence
}

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

Explanation

Algorithm

Для каждого возможного начала последовательности в массиве nums начните считать количество нулей.

Для каждой последовательности проверяйте, сколько нулей содержится в ней. Если количество нулей не превышает одного, обновите максимальную длину последовательности единиц.

Продолжайте проверять все возможные последовательности в массиве, и верните максимальную длину последовательности единиц, удовлетворяющую условию.

😎