|
| 1 | +#!/usr/bin/python3 |
| 2 | +""" |
| 3 | +Given an array A of 0s and 1s, we may change up to K values from 0 to 1. |
| 4 | +
|
| 5 | +Return the length of the longest (contiguous) subarray that contains only 1s. |
| 6 | +
|
| 7 | +
|
| 8 | +
|
| 9 | +Example 1: |
| 10 | +
|
| 11 | +Input: A = [1,1,1,0,0,0,1,1,1,1,0], K = 2 |
| 12 | +Output: 6 |
| 13 | +Explanation: |
| 14 | +[1,1,1,0,0,1,1,1,1,1,1] |
| 15 | +Bolded numbers were flipped from 0 to 1. The longest subarray is underlined. |
| 16 | +Example 2: |
| 17 | +
|
| 18 | +Input: A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3 |
| 19 | +Output: 10 |
| 20 | +Explanation: |
| 21 | +[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1] |
| 22 | +Bolded numbers were flipped from 0 to 1. The longest subarray is underlined. |
| 23 | +
|
| 24 | +
|
| 25 | +Note: |
| 26 | +1 <= A.length <= 20000 |
| 27 | +0 <= K <= A.length |
| 28 | +A[i] is 0 or 1 |
| 29 | +""" |
| 30 | +fromtypingimportList |
| 31 | + |
| 32 | + |
| 33 | +classSolution: |
| 34 | +deflongestOnes(self,A:List[int],K:int)->int: |
| 35 | +""" |
| 36 | + len(gap) |
| 37 | + But there is multiple gap need to fill, and which gaps to fill is |
| 38 | + undecided. Greedy? No. DP? |
| 39 | +
|
| 40 | + Sliding Window: Find the longest subarray with at most K zeros. |
| 41 | + """ |
| 42 | +i,j=0,0 |
| 43 | +cnt_0=0 |
| 44 | +n=len(A) |
| 45 | +ret=0 |
| 46 | +whilei<nandj<n: |
| 47 | +whilej<n: |
| 48 | +ifA[j]==0andcnt_0<K: |
| 49 | +j+=1 |
| 50 | +cnt_0+=1 |
| 51 | +elifA[j]==1: |
| 52 | +j+=1 |
| 53 | +else: |
| 54 | +break |
| 55 | + |
| 56 | +ret=max(ret,j-i) |
| 57 | +ifA[i]==0: |
| 58 | +cnt_0-=1 |
| 59 | +i+=1 |
| 60 | + |
| 61 | +returnret |
| 62 | + |
| 63 | + |
| 64 | +if__name__=="__main__": |
| 65 | +assertSolution().longestOnes([1,1,1,0,0,0,1,1,1,1,0],2)==6 |