企业做网站营销的四大途径,免费网站国内空间,北京海淀的保险公司,公众号1000粉丝月收入1004.最大连续1的个数 |||
1004. 最大连续1的个数 III - 力扣#xff08;LeetCode#xff09; 题目解析#xff1a; 这道题如果能转化为滑动窗口的话就会很简单#xff0c;因为我们如果尝试去把0翻转为1再计数的话等到第2轮又得重新翻转回来#xff0c;费时费力~ 那么我…1004.最大连续1的个数 |||
1004. 最大连续1的个数 III - 力扣LeetCode 题目解析 这道题如果能转化为滑动窗口的话就会很简单因为我们如果尝试去把0翻转为1再计数的话等到第2轮又得重新翻转回来费时费力~ 那么我们不妨默认就把0当作1选中一段区间只要里面0的个数不超过k那就可以了。这样就把问题转化为求0的个数不超过k的最长子数组妥妥用滑动窗口。 老规矩我们先来用暴力找找灵感 需要列举的有点多不过也有很多可优化的空间~ 算法解析 其实当我们转换为滑动窗口后相信看过我前边博客的友友们肯定都知道了所以我们废话不多说。 在right不断遍历的过程中遇到0就记录其个数等到不满足条件sumk时说明在它之前已经找到最长子数组了。开始新一轮的寻找这时候我们的right不用再回来遍历因为之前都已经遍历并记录在sum中了所以留在原位移动left即可。 滑动窗口流程 滑动窗口的两个指针移动规律也很简单 right 遇1—— rightright 遇0—— sum,rightleft 遇1—— leftleft 遇0—— sum--,left 代码
class Solution {
public:int longestOnes(vectorint nums, int k) {int n nums.size();int sum 0;int ret INT_MIN;for (int left 0, right 0; right n; right){//扩充窗口if (nums[right] 0){sum;}//判断若sumk到下一循环继续扩充//若sumk缩小窗口while (sum k){if (nums[left] 0){sum--;}left;}//更新长度ret max(ret, right - left 1);}return ret;}
};
1658.将x减到0的最小操作数 1658. 将 x 减到 0 的最小操作数 - 力扣LeetCode 题目解析 这道题从正面来做会很难因为你要不断考虑是从左边选数还是从右边选数。那么我们不如从另外一个角度来思考这个问题~ 首先我们要把通过移除左右两边数使得x0转换为挑选出左右两区间使得里面的数之和为x. 但两段区间也还是麻烦我们不妨去挑出处于两区间中间的连续区间。 我们只需要让这个连续区间里面的和为sum-x就可以了再求出连续区间的长度len最后n-len反推出真正的最小操作数。 算法解析 问题转换求出总数之和为sum-x的最长连续子数组 只要ta我们就让right继续往后遍历直到出现ta的情况。 而在第二轮开始遍历的时候right其实不用去复位因为在ta的那个节点前面的总和本来就是taleft前进一位只会让t更小。所以right是没必要复位的留在原地就好了。 滑动窗口流程 最后有一点小细节 如果题目给的x比我们所有数组之和还大得特殊处理~ 代码
class Solution {
public:int minOperations(vectorint nums, int x) {int len -1;int n nums.size();int sum 0;for (int i : nums){sum i;}//遍历连续数组之和int target 0;//连续段的期望数值int a sum - x;//细节处理if (a 0) return -1;for (int left 0, right 0; right n; right){//扩充窗口target nums[right];//判断只要targeta就缩小窗口反之就进行下一轮的扩充while (target a){//缩小窗口target - nums[left];}//只有达到期望数值才可以记录长度if (target a){len max(len, right - left 1);}}//没有达到期望数值说明找不到if (len -1){return -1;}else{return n - len;}}
};
