1004. 最大连续1的个数 III
1004. 最大连续1的个数 III
题目描述:
给定一个二进制数组 nums
和一个整数 k
,如果可以翻转最多 k
个 0
,则返回 数组中连续 1
的最大个数 。
解题思路:
首先题目要我们求出的最多翻转k个0后(可以翻转【0,k】个0,不一定要全翻转)的连续1最多的子数组的长度
我们可以用left,right滑动窗口的思想,定一个zero来记录0的个数,right不断向右走,当遇到nums【right】等于0时,zero++,当zero的个数大于k的时候,left先右走,当遇到nums【left】等于0时,zero--直到zero<=k,然后更新length的大小
解题代码:
class Solution {
public:int longestOnes(vector<int>& nums, int k) {int length=0;int n=nums.size();int zero=0;int left=0,right=0;while(right<n){if(nums[right]==0)zero++;while(zero>k){if(nums[left++]==0)zero--;}length=max(length,right-left+1);right++;}return length;}
};
1658. 将 x 减到 0 的最小操作数
1658. 将 x 减到 0 的最小操作数
题目描述:
给你一个整数数组 nums
和一个整数 x
。每一次操作时,你应当移除数组 nums
最左边或最右边的元素,然后从 x
中减去该元素的值。请注意,需要 修改 数组以供接下来的操作使用。
如果可以将 x
恰好 减到 0
,返回 最小操作数 ;否则,返回 -1
。
解题思路:
本题是要不断从左右两边减一个数,使x减为0,我们可以发现左右两边减的数组是两个连续区间,也就是说整个大数组被分成了三个小数组,我们可以转换一下思想:变为求中间数组之和等于target(大数组之和-x)的最长长度,也就是变成了子数组问题
值得注意的是length应该初始化为-1,而不是0,因为当length=0有两种情况
- 当数组为【5,6,7,8,9】,而x=4,中间数组每个数都大于x
- 刚好length=0,每个元素都要出的情况
解题代码:
class Solution {
public:int minOperations(vector<int>& nums, int x) {int sum=0;for(int i=0;i<nums.size();i++)sum+=nums[i];int target=sum-x;if(target<0) return -1;int n=nums.size();int length=-1;for(int left=0,right=0,num=0;right<n;right++){num+=nums[right];while(num>target)num-=nums[left++];if(num==target)length=max(length,right-left+1);}if(length==-1)return length;else return n-length;}
};