【算法挨揍日记】day06——1004. 最大连续1的个数 III、1658. 将 x 减到 0 的最小操作数

 

 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
        {
            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;isize();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
        {
            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;
    }
};