Created
November 21, 2015 17:25
-
-
Save junminstorage/4e5c69c5d4d9e99b86d9 to your computer and use it in GitHub Desktop.
Given a array consisted of only 0 or 1, and a number N. We have N times to flip 0 to 1 in array. Find the longest continuous 1 after we flipped the N zero elements. Rotation is allowed. For example, 100100111000, n=2, the best flip is 100111111000, return 6 10001101101, n=2, the best flip is 10001111111, return 8(rotation is allowed)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public static int findContinuous1s(String s, int maxFlips){ | |
int[] max = new int[1]; | |
findContinuous1sRec(s, 0, 0, maxFlips, 0, max); | |
return max[0]; | |
} | |
public static void findContinuous1sRec(String s, int start, int current, int maxFlips, int flips, int[] max){ | |
//keep on eating up 1s if we can | |
while(current<s.length() && s.charAt(current) == '1') | |
current++; | |
if(current == s.length()){ | |
//rotation | |
int left = 0; | |
while(s.charAt(left) == '1' || flips++<maxFlips) | |
left++; | |
max[0] = Math.max(max[0], current-start + left); | |
return; | |
} | |
//current char is 0 | |
//we can flip and we decide to flip | |
if(flips<maxFlips) | |
findContinuous1sRec(s, start, current+1, maxFlips, flips+1, max); | |
//if we can't flip or we decide to not flip | |
max[0] = Math.max(max[0], current-start); | |
//set start = current+1 and continue search | |
findContinuous1sRec(s, current+1, current+1, maxFlips, flips, max); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment