最大连续1的个数
最大连续1的个数
题目描述
题目解析
- 给我们一个元素全是0或者1的数组,和一个整数 k ,然后让我们在数组选出最多的 k 个0;
- 这里翻转最多 k 个0的意思,是翻转 0 的个数<= k,而不是一定要翻转 k 个0;
- 然后把这 k 个0翻转成1,翻转完成后,找出数组中,连续1的最大个数。
算法原理
如果按照这个题,直接去把0翻转成1,我们会发现这个操作非常麻烦,因为如果后续还要枚举数组中别的0,就要先把刚刚翻转过的1翻转回0,代码也不好写;
通过上述两个例子,求最大连续1的个数的过程中,我们并没有真正地对0进行翻转,所以我们是可以不用翻转的;
我们只需要在数组中,找一段元素连续为0的区域,并且0的个数不超过k即可;
换而言之,只要这段区域的0的个数不超过k,那么就是一定可以成功翻转的,我们没必要真正地去翻转。
所以上述的问题可以转换成:找出最长子数组,0的个数不超过k个;
解法一:暴力枚举 + zero计数器
- 既然要找最长子数组,我们就固定一个起点,然后不断枚举所有0的个数不超过k的子数组;
- 并且返回所有子数组中,长度最大的子数组即可。
在暴力枚举的过程中,我们需要定义一个变量,来计数子数组中0的个数;
我们所有的优化方法,都是建立在暴力枚举的基础上,来做优化的,所以要考虑清楚暴力枚举的要点和细节,再在这些细节和要点上总结规律,并作出优化。
如果是暴力枚举的话,此时在 right 到达合适的位置后,left++,right = left,并且重复上面的过程;
但是我们可以发现,在后续的left 向后枚举的过程中,只要 left还在前面3个1的位置,right 能到达的最远位置是不变的;
我们要对上述枚举的细节做优化。
解法二:滑动窗口
left 移动到能让 zero=2 的位置,此时只需要让 right 继续向后挪动
- left = 0, right =0 ;
- 进窗口 (right=1,无视;right = 0,zero++);
- 判段(zero > k) (3和4是循环)
- 出窗口(left = 1,无视;left = 0,zero--);
- 更新结果
编写代码
时间复杂度:
虽然有两层循环,但是根据实际过程,时间复杂度 O(N);
空间复杂度:
只定义了有限的变量,所以是O(1)
将 x 减到0的最小操作数
将 x 减到0的最小操作数
题目描述
转换思路:找到数组中,长度最长,且和为 sum - x 的子数组
如果我们直接按照题目的要求,每次操作都删除数组最左边,或者最右边的元素,使得 x=0,那么这道题的操作是非常麻烦的,因为能删除的方法非常多;
如果正面比较难,我们就使用“正难则反”的方法,这是非常重要的一点;
当我们计算数组两边的区间比较难找,我们可以转换思路,求中间的这一个连续的区间之和
- 我们只需要在数组中间找一段连续的区域,这段区域所有元素之和 target 等于 sum - x 即可;
- 题目要求的是最小操作数,所以是要找 左边区间 和 右边区间 的元素个数之和最小的情况即可;
- 进而转换为,在这个数组中,找到一块连续的区域,这个区域的所有元素之和,等于sum-x;
- 并且这个连续的区域是要最长的,长度设置为 len;
- 找到最长的 len,返回 length - len 即可
解法:滑动窗口
随机定义一个数组,来发现规律
定义 sum1 变量,来标记 right 和 left 中间这段区域的和;
在 right 向后遍历的时候:
- 当 sum1 > target 时,固定 right,移动 left
- 当 sum1 = target 时,先更新 len,再移动 right,
- 如果出现 sum1 >= target 的情况,按照上面的步骤处理
证明 right 不需要往后移动:
此时 right 会停下,是因为刚刚好改变 sum1 和 target 的关系,再更新 len 之后,left++;
此时 left 在更新之后,left 和 right 中间的区域之和一定是小于 target 的,所以 right 不需要 --;
- left = 0, right =0 ;
- 进窗口(sum1 += num[right++]);
- 判断sum1 > target(注意:sum = target 是我们要的结果,而判断是用来调整结果的,所以不写=)
- 出窗口(sum1 -=nums[left++]),3 和 4 是循环
- 更新结果 (判断 sum1 是等于还是小于 target,==才更新结果);
编写代码
上述情况是因为,在刚刚好遍历完成所有数组元素,sum1 才刚好等于 target 的,此时 len虽然还是0,但是只要最终结果返回 n - len ,依旧是正确答案;
但是也有在遍历完所有数组元素,sum1 都不能等于 target 的,所以要在返回结果时判断;
而上述示例二在执行到 return 时,刚好 len 也是0,但是要返回 -1;两种情况就刚好重合了;
修改代码