MaxConsecutiveOnesII [source code]
public class MaxConsecutiveOnesII {
static
/******************************************************************************/
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int N = nums.length;
int len1 = -1, len2 = -1, res = -1;
for (int i = 0; i < N; i++) {
if (nums[i] == 1) { //is this 1 in len1 or len2
if (len2 < 0) {
if (len1 < 0)
len1++;
len1++;
res = len1;
} else {
len2++;
res = Math.max(res, len1 + len2);
}
} else {
if (i == 0 || (i > 0 && nums[i - 1] == 0))
continue;
if (i + 1 < N && nums[i + 1] == 1) {
if (len2 < 0) {
len2++;
} else {
len1 = len2;
len2 = 0;
}
} else { //[i + 1] is 0 or is out of bound
len1 = 0;
len2 = 0;
}
}
}
if (res == -1)
return 1;
if ((len2 < 0 && N > res) || len2 >= 0)
res++;
return res;
}
}
/******************************************************************************/
public static void main(String[] args) {
MaxConsecutiveOnesII.Solution tester = new MaxConsecutiveOnesII.Solution();
int[][] inputs = {
{1,0,1,1,0}, {4},
{0,0,1,1,1,0,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,0,1}, {11},
{1}, {1},
{0}, {1},
{0,0},{1},
{0,1},{2},
};
for (int i = 0; i < inputs.length / 2; i++) {
int[] nums = inputs[2 * i];
int ans = inputs[1 + 2 * i][0];
System.out.println(Printer.separator());
int output = tester.findMaxConsecutiveOnes(nums);
System.out.println(
Printer.wrapColor(Printer.array(nums), "magenta") +
" -> " + output +
Printer.wrapColor(", expected: " + ans, ans == output ? "green" : "red")
);
}
}
}
首先拿到题目的感觉好像不是一个难题, 就是一直走, 记录run of 1的长度, 然后碰到0就看是不是只有一个0, 如果是只有一个0, 那么就继续往后记录; 当然这个算法现在看起来好像有点naive, 不过还是从这种笨办法开始, 然后找到这个方法的问题之后, 才能逐渐靠近真正的解法;
大概想了一下一个算法, 基础还是分段算法来考虑1run的计算; 不过这个是一个computation的思路, 真正要转化成算法或者说代码, 你要考虑的是每一个iteration, 更具体的说, 是每一个index的entry你怎么处理;
这个Follow-Up的的意思大概应该就是不能用split这种提前知道了整个string的方法来做, 而只能用一个stream的方法来做;
整个算法其实本身的核心逻辑并不算复杂, 就是考虑类似111011011011110111这样的, separator只有一个0的部分, 这样一个block, 我们计算每一个1run的长度, 然后计算最长的连续两个run长度之和; block与block之间的分块是采用, 比如有超过一个0, 就是分块了, 这个时候所有的变量重置, 除了res;
最后是速度是12ms (57%), 这个有点奇怪, 因为感觉这个算法不可能再快了;
另外也还是Google题目一贯的特点, 最后有大量不好处理的Corner Case;
我这个算法就是一个很僵的历史信息路的分段算法的解法, 看了discussion才知道这个问题的更好的一个理解方式: sliding window. 其实我们要找的就是a window that contains at most 1 zero. 理解了这个思路之后, 比我的思路厉害的一个地方在于, 这样的一个算法可以extend到不仅是flip1zero, 而是可以任意个zero;
这个解法就比较有点学以致用的意思了; 只能说这个题目题型的cue藏得有点深, 如果不是往这个方向上面响, 真的是想不到; 另外这里这个Follow-Up的目的也就比较清晰了, 其实就是为了给sliding window算法出难题的;
@yuxiangmusic said in Java clean solution easily extensible to flipping k zero and follow-up handled:
The idea is to keep a window
[l, h]that contains at mostkzeroThe following solution does not handle follow-up, because
nums[l]will need to access previous input stream
Time: O(n) Space: O(1)```java
public int findMaxConsecutiveOnes(int[] nums) {
int max = 0, zero = 0, k = 1; // flip at most k zero
for (int l = 0, h = 0; h < nums.length; h++) {
if (nums[h] == 0)
zero++;
while (zero > k)
if (nums[l++] == 0)
zero--;
max = Math.max(max, h - l + 1);
}
return max;
}
还是比较标准的sliding window的算法, 没有什么太特别的地方;
另外可以看到用sliding window做还有一个好处, 当我们拓展到k的时候, 这个k甚至不用是consecutive的; 想要达到同样的一个目的, 用普通的历史信息流就复杂的多;
> Now let's deal with follow-up, we need to store up to ```k``` indexes of zero within the window ```[l, h]``` so that we know where to move ```l``` next when the window contains more than ```k``` zero. If the input stream is infinite, then the output could be extremely large because there could be super long consecutive ones. In that case we can use ```BigInteger``` for all indexes. For simplicity, here we will use ```int
Time: O(n) Space: O(k)public int findMaxConsecutiveOnes(int[] nums) { int max = 0, k = 1; // flip at most k zero Queue<Integer> zeroIndex = new LinkedList<>(); for (int l = 0, h = 0; h < nums.length; h++) { if (nums[h] == 0) zeroIndex.offer(h); if (zeroIndex.size() > k) l = zeroIndex.poll() + 1; max = Math.max(max, h - l + 1); } return max; }Note that setting
k = 0will give a solution to the earlier version Max Consecutive OnesFor
k = 1we can apply the same idea to simplify the solution. Hereqstores the index of zero within the window[l, h]so its role is similar toQueuein the above solutionpublic int findMaxConsecutiveOnes(int[] nums) { int max = 0, q = -1; for (int l = 0, h = 0; h < nums.length; h++) { if (nums[h] == 0) { l = q + 1; q = h; } max = Math.max(max, h - l + 1); } return max; }
这个人的Follow-Up写的思路还是很清晰的: Follow-Up, 首先要分析, 在Follow-Up给你的这个条件当中, 什么样的difficulty会导致之前的算法不可行;
一个优化:
@iaming said in Java clean solution easily extensible to flipping k zero and follow-up handled:
@yuxiangmusic You dont need max for every number, just do it when 0 is seen. Reduced to 8 ms, beats 98%.
int prev = -1, cur = -1, ans = 0;
for (int i = 0; i < nums.length; ++i) {
if (nums[i] == 0) {
ans = Math.max(ans, i - prev - 1);
prev = cur;
cur = i;
}
}
return Math.max(ans, nums.length - prev - 1);
有人认为, 如果我们真的需要处理的是一个无穷的stream, 那么就连l和h这样的index都有可能overflow; 这个是作者的回应:
@yuxiangmusic said in Java clean solution easily extensible to flipping k zero and follow-up handled:
@0x0101 In the most extreme case, even the output
maxcan overflow because there could be super long consecutive ones. In that case we have to useBigIntegernot only forlandhbut also for the output.Since the length of
numswill not exceedInteger.MAX_VALUEwe knowlandhwill never overflow for this problem. If we really want to deal with infinite input stream, then the method should be changed to:public BigInteger findMaxConsecutiveOnes(InputStream in);
真正自己面试的时候如果产生这种疑惑还是好好问一下. 如果脑子里有这个错误的观念, 这个问题就真的没有办法解决了;
上面的sliding window的解法其实也是做到了O(N)时间和O(1)空间的(在k等于1的情况下);
这里是另外一个做到了0(N)时间和O(1)空间的解法:
public int findMaxConsecutiveOnes(int[] nums) {
int maxConsecutive = 0, zeroLeft = 0, zeroRight = 0;
for (int i=0;i<nums.length;i++) {
zeroRight++;
if (nums[i] == 0) {
zeroLeft = zeroRight;
zeroRight = 0;
}
maxConsecutive = Math.max(maxConsecutive, zeroLeft+zeroRight);
}
return maxConsecutive;
}
这个解法的核心思路其实是跟我的一样的, 就是分析1run, 或者说分析1run之间的separator是几个0; 但是他这个代码, 完成了同样的事情, 代码本身却比我的代码要elegant的多; 不仅是正常的逻辑elegant很多, 就连最后的那些乱七八糟让我头疼很久的Corner Case, 他这里也都直接全部都解决了; 包括最后如果我们得到的结果是两个1run的长度之和, 我的做法还要最后考虑是否需要+1, 他这个就不需要考虑, 直接就能完成;
这个算法因为非常的简练, 所以一开始没有看懂, 用一个例子来帮忙理解:
0 0 1 1 0 1 1 1 0 0 1 1 1 1 0 //entry
0 1 1 1 1 3 3 3 3 4 1 1 1 1 1 5 //zeroLeft
0 0 0 1 2 0 1 2 3 0 0 1 2 3 4 0 //zeroRight
again, 还是要掌握这种iteration trace的写法; 这里我下面两个变量记录的其实是当前entry的iteration的end, 也就是下一个entry的iteration的beginning的时刻的状态;
作者自己并没有给出什么解释, 这个是下面回复里面的一个解释:
@gatechyy said in Java Concise O(n) Time O(1) Space:
zero right can be considered as 1 accumulated. If the gap between 1 and 1 is only 1(zero), zeroleft can be a temp storage to store how many 1 has been calculated, and then move on accumulate. But if there are 2 or more 0 gap, after the 1st 0, left will only be used to the flipped single 1.
这个讲的大体意思是对的, 你可以看, 在大部分时候(不是在11.11011..11的第二个1run里面的时候), left其实就存了一个1, 这个其实就是我自己的做法里面的那个+1, 他预存在left里面了而已; 而当我们在11..11011..11的情况下的时候, 两个变量之间的关系就跟我的len1和len2是差不多的;
这样一说好像这个算法不是很特别, 但是他这里比较厉害的地方是研究出了这几种情况下的数量关系, 直接整合起来就能统一处理; 总感觉这样一个算法背后应该是有一个什么理念的, 但是想不到; 如果你自己举几个特殊的例子, 就知道他这里的数值计算的原理, 比如1101111, 这种只有一个0的, right计算的其实是1run的长度, 加上一个trailing zero, 也就是110的长度, 然后碰到0的时候, 这个110的长度扔到left里面去, right变成0, 后面继续统计后面的1111长度, 这样最后max里面存的就是1101111整个的长度; 如果这个时候后面再来一个00, 那么, 在第一个0, 11110的长度就被扔到left里面, 然后right这个时候是做好准备下面重新开始count下一个1run的; 但是到了第二个0, 没有1, 这个时候right手上的一个1就直接扔到left里面; 假如我们后面再来一些1, 这个时候我们的max里面计算的是什么呢? 也就是110111100[11..11]括号部分的位置的时候? 你可以说是left记录的是0(the second of 00)的长度, 然后right记录的肯定还是1run的长度; 你也可以认为left记录的其实是0 ones and 1 zero组成的长度;
所以其实这里right和left首先, 是同一个概念, 只不过left是缓存而已; 然后这个同一个概念是什么? 就是length of 11..110 ending at each 0, 这里前面的1run长度可以等于0;
这样一来好像可以解释算法的核心概念了, 但是真正这个人自己怎么想到这样的一个算法的, 还是不得而知;
这个是我自己在下面发的解释:
Any 1/0 string with at least one trailing 0 can be seeing as repeating of a pattern: a ones followed by 1 zero. We denote such a pattern by p(a). Eg:
p(1) =def= 10
p(3) =def= 1110
p(5) =def= 111110
p(0) =def= 0
pay attention to the last one. Also note that, each occurrence of 0 signals the end of such a pattern.
And such a string 0011011100 can be seen as p(0) + p(0) + p(2) + p(3) + p(0). Reminder, count a pattern at its trailing 0.
In OP's solution, the two variables zeroLeft and zeroRight serve these purposes: for each iteration, or index i
zeroLeft: the length of pattern that ends no later thani.zeroRight: the length of the run of1ifiis in one. 0 otherwise.
Here is a trace for your convenience :
0 0 1 1 0 1 1 1 0 0 1 1 1 1 0 //entry
0 1 1 1 1 3 3 3 3 4 1 1 1 1 1 5 //zeroLeft
0 0 0 1 2 0 1 2 3 0 0 1 2 3 4 0 //zeroRight
So, at each i that is 1, we consider zeroLeft + zeroRight because for an example like 110111, we are considering len(p(2)) + len(run(3)) (run(3) as 3 consecutive 1s).
The code's logic:
For each index i:
if nums[i] is 0: calculate the length of the pattern that ends at nums[i] , and put it into zeroLeft. Reset zeroRight because we are no longer in a run;
if nums[i] is 1: increment zeroRight which records run length, and try to update max with (zeroLeft + zeroRight);
Of course, OP wrote his code in another way, but I think that is the logic here. I solved this problem with a similar approach (considering the separating zeroes), but OP's code is way more elegant than mine.
Again, this is only my way of interpreting this program, and it's highly unlikely this is the thinking process of OP himself. The concept of a pattern is coined not necessarily. I do hope this will aid in the process of you finding your own way of interpretation.
另外, 这一题的模板sliding window解法:
public class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int j=0;
int len=0;
int zero=0;
for(int i=0;i<nums.length;i++){
if(nums[i]==0){
zero++;
}
while(zero>1){
if(nums[j]==0){
zero--;
}
j++;
}
len=Math.max(i-j+1,len);
}
return len;
}
}
这个是另外一个挺有意思的解法:
@shawngao said in Java DP O(n) Solution:
The idea is to use an extra array
dpto store number of1to its left and right. Then the answer is theMAXofdp[i] + 1of allnums[i] == 0.
public class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int result = 0, n = nums.length, count = 0;
int[] dp = new int[n];
for (int i = 0; i < n; i++) {
dp[i] = count;
if (nums[i] == 1) {
count++;
result = Math.max(count, result);
}
else count = 0;
}
count = 0;
for (int i = n - 1; i >= 0; i--) {
dp[i] += count;
if (nums[i] == 1) count++;
else count = 0;
}
for (int i = 0; i < n; i++) {
if (nums[i] == 0) {
result = Math.max(result, dp[i] + 1);
}
}
return result;
}
}
这个解法的思路跟前面两种主流思路其实都不一样(一个是sliding window, 一个就是分段), 虽然这个人自己说这个解法是一个DP, 不过我感觉并不是. 这个解法本身就是他看到了问题的一个本质之后的一个intuition之后写的一个解法. 总体来说还是挺聪明的, 虽然好像不能解决Follow-Up? 因为Follow-Up定义的是一个stream, 他这个要一个双向扫描了;
另外这个解法很类似之前的一个product except for itself的题目, 那个题目当时的思路就觉得挺有意思的; 这个题目的这个解法感觉没有那个题目的时候的那么精妙, 不过也是很聪明的一个思路;
Problem Description
Given a binary array, find the maximum number of consecutive 1s in this array if you can flip at most one 0.
Example 1:
Input: [1,0,1,1,0]
Output: 4
Explanation: Flip the first zero will get the the maximum number of consecutive 1s.
After flipping, the maximum number of consecutive 1s is 4.
Note:
- The input array will only contain 0 and 1.
- The length of input array is a positive integer and will not exceed 10,000
Follow up:
What if the input numbers come in one by one as an infinite stream? In other words, you can't store all numbers coming from the stream as it's too large to hold in memory. Could you solve it efficiently?
Difficulty:Medium
Total Accepted:7.1K
Total Submissions:15.6K
Contributor: Stomach_ache
Companies
google
Related Topics
two pointers
Similar Questions
Max Consecutive Ones