【刷题2—滑动窗口】最大连续1的个数lll、将x减到0的最小操作数

一、最大连续1的个数lll

题目：

思路：
问题转换为：找到一个最长子数组，这个数组里面0的个数不能超过k个

定义一个变量count，来记录0的个数，进窗口、判断、出窗口、更新结果

代码：

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int n = nums.size(), count = 0;
        int left = 0, right = 0, len = 0;
        while (right < n)
        {
            if (nums[right] == 0) count++;
            right++;
            while (count > k)
            {
                if (nums[left] == 0) count--;
                left++;
            }
            len = max(len, right - left);
        }
        return len;
    }
};

二、将x减到0的最小操作数

题目：

思路：
题目要求是移除最右边或者最左边，直接这样操作非常麻烦，可以反过来做。

最右边和最左边的和为x，用一个变量sum统计数组所有的元素之和，sum-x就是剩下区域的元素，这个区域是连续的，可以用滑动窗口。

要考虑target是负数的情况，如果是负数，直接返回-1，因为数组的每个元素都是整数。

要让操作数的次数最小，就要让等于target的子数组尽可能大，然后用滑动窗口的思路做，返回值为：如果子数组中没有和等于target就返回-1，否则返回数组长度减去len（n-len），得到最小操作数。

代码：

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int n = nums.size();
        int sum = 0;
        // 总和
        for (auto e : nums) sum += e;
        int target = sum - x;
        // 负数情况
        if (target < 0) return -1;
        int left = 0, right = 0, len = -1, k = 0;
        while (right < n)
        {
            k += nums[right];
            while (k > target)
            {
                k -= nums[left];
                left++;
            }
            if (k == target)
            {
                len = max(len, right - left + 1);
            }
            ++right;
        }
        return len == -1 ? -1 : n - len;
    }
};

原文地址：https://blog.csdn.net/2301_77459845/article/details/142468135

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！