目录
- 一、最大连续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;}
};