网站建设 实训网络营销企业网站优化
最大连续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；两种情况就刚好重合了；
修改代码
