asp网站设计要求,苏州网架公司,美食网页设计作品欣赏,网站源码修改后怎么提交最大连续1的个数 最大连续1的个数 题目描述 题目解析
给我们一个元素全是0或者1的数组#xff0c;和一个整数 k #xff0c;然后让我们在数组选出最多的 k 个0#xff1b;这里翻转最多 k 个0的意思#xff0c;是翻转 0 的个数 k#xff0c;而不是一定要翻转 k … 最大连续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 到达合适的位置后leftright left并且重复上面的过程;
但是我们可以发现在后续的left 向后枚举的过程中只要 left还在前面3个1的位置right 能到达的最远位置是不变的 我们要对上述枚举的细节做优化。 解法二滑动窗口 left 移动到能让 zero2 的位置此时只需要让 right 继续向后挪动 left 0, right 0 ;进窗口 right1无视right 0zero判段zero k 3和4是循环出窗口(left 1无视left 0zero--)更新结果 编写代码 时间复杂度
虽然有两层循环但是根据实际过程时间复杂度 O(N); 空间复杂度
只定义了有限的变量所以是O(1) 将 x 减到0的最小操作数 将 x 减到0的最小操作数
题目描述 转换思路找到数组中长度最长且和为 sum - x 的子数组 如果我们直接按照题目的要求每次操作都删除数组最左边或者最右边的元素使得 x0那么这道题的操作是非常麻烦的因为能删除的方法非常多
如果正面比较难我们就使用“正难则反”的方法这是非常重要的一点 当我们计算数组两边的区间比较难找我们可以转换思路求中间的这一个连续的区间之和 我们只需要在数组中间找一段连续的区域这段区域所有元素之和 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两种情况就刚好重合了 修改代码
