max_consecutive_ones_iii

View Source

 1# @leet start
 2class Solution:
 3    def longestOnes(self, nums: list[int], k: int) -> int:
 4        """
 5        This question asks us to find the longest sequence of consecutive 1s
 6        if you're allowed to flip at most `k` 0s.
 7        The way we can solve this is by using a sliding window -- we open up a
 8        window, and then count the number of zeroes in the window, disregarding
 9        ones.
10        If we hit more zeroes in our window than k, we keep incrementing our left
11        pointer until there are less than k zeroes.
12        At the end of each loop, we count the max of `i - j + 1` and return
13        the max of that at the end.
14        """
15        zero_count, max_so_far, j = 0, 0, 0
16        for i, num in enumerate(nums):
17            if num == 0:
18                zero_count += 1
19                while zero_count > k:
20                    if nums[j] == 0:
21                        zero_count -= 1
22                    j += 1
23            max_so_far = max(max_so_far, i - j + 1)
24        return max_so_far
25
26
27# @leet end
28
29
30def test():
31    assert 2 + 2 == 4

class Solution: View Source

 3class Solution:
 4    def longestOnes(self, nums: list[int], k: int) -> int:
 5        """
 6        This question asks us to find the longest sequence of consecutive 1s
 7        if you're allowed to flip at most `k` 0s.
 8        The way we can solve this is by using a sliding window -- we open up a
 9        window, and then count the number of zeroes in the window, disregarding
10        ones.
11        If we hit more zeroes in our window than k, we keep incrementing our left
12        pointer until there are less than k zeroes.
13        At the end of each loop, we count the max of `i - j + 1` and return
14        the max of that at the end.
15        """
16        zero_count, max_so_far, j = 0, 0, 0
17        for i, num in enumerate(nums):
18            if num == 0:
19                zero_count += 1
20                while zero_count > k:
21                    if nums[j] == 0:
22                        zero_count -= 1
23                    j += 1
24            max_so_far = max(max_so_far, i - j + 1)
25        return max_so_far

def longestOnes(self, nums: list[int], k: int) -> int: View Source

 4    def longestOnes(self, nums: list[int], k: int) -> int:
 5        """
 6        This question asks us to find the longest sequence of consecutive 1s
 7        if you're allowed to flip at most `k` 0s.
 8        The way we can solve this is by using a sliding window -- we open up a
 9        window, and then count the number of zeroes in the window, disregarding
10        ones.
11        If we hit more zeroes in our window than k, we keep incrementing our left
12        pointer until there are less than k zeroes.
13        At the end of each loop, we count the max of `i - j + 1` and return
14        the max of that at the end.
15        """
16        zero_count, max_so_far, j = 0, 0, 0
17        for i, num in enumerate(nums):
18            if num == 0:
19                zero_count += 1
20                while zero_count > k:
21                    if nums[j] == 0:
22                        zero_count -= 1
23                    j += 1
24            max_so_far = max(max_so_far, i - j + 1)
25        return max_so_far

This question asks us to find the longest sequence of consecutive 1s if you're allowed to flip at most k 0s. The way we can solve this is by using a sliding window -- we open up a window, and then count the number of zeroes in the window, disregarding ones. If we hit more zeroes in our window than k, we keep incrementing our left pointer until there are less than k zeroes. At the end of each loop, we count the max of i - j + 1 and return the max of that at the end.

def test(): View Source

31def test():
32    assert 2 + 2 == 4