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

缺乏、安全感 2024-03-03 01:44 8阅读 0赞

![b76e40079c18492096bde397d9e1aa63.png][]

## 1004. 最大连续1的个数 III ##

[1004. 最大连续1的个数 III][1004. _1_ III]

### 题目描述： ###

给定一个二进制数组 `nums` 和一个整数 `k`，如果可以翻转最多 `k` 个 `0` ，则返回 *数组中连续 `1` 的最大个数* 。![f3cc91cc5a7d4c6897f75fe5df2205c9.png][]

### 解题思路： ###

> 首先题目要我们求出的最多翻转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 的最小操作数][1658. _ x _ 0]

### 题目描述： ###

给你一个整数数组 `nums` 和一个整数 `x` 。每一次操作时，你应当移除数组 `nums` 最左边或最右边的元素，然后从 `x` 中减去该元素的值。请注意，需要 **修改** 数组以供接下来的操作使用。

如果可以将 `x` **恰好** 减到 `0` ，返回 **最小操作数** ；否则，返回 `-1` 。

![a3b8ff0c9d044aec9fac0708a28401b1.png][]

### 解题思路： ###

> 本题是要不断从左右两边减一个数，使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;
        }
    };

![285f973078cf4c9ea23da652bcae7094.gif][]

[b76e40079c18492096bde397d9e1aa63.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/d15c021350944fa8a233a44da7919a33.png
[1004. _1_ III]: https://leetcode.cn/problems/max-consecutive-ones-iii/
[f3cc91cc5a7d4c6897f75fe5df2205c9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/bfcae5f81fe7433db9bd0d823754c8c1.png
[1658. _ x _ 0]: https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/
[a3b8ff0c9d044aec9fac0708a28401b1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/d70d1688685f4709859c5cfc40678bd7.png
[285f973078cf4c9ea23da652bcae7094.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/4ba51ea0f1ad433ebe808da91fd78428.png