目录
1658. 将 x 减到 0 的最小操作数
解析
题解
904. 水果成篮
解析
题解
1658. 将 x 减到 0 的最小操作数
1658. 将 x 减到 0 的最小操作数 - 力扣(LeetCode)
解析
题解
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
// 012_专题二_滑动窗口_将 x 减到 0 的最小操作数_C++
// 正难则反
// 转化:找出最长的子数组的长度,所有元素的和正好等于 sum - x
// 结果只需要用 n - len就可以了
int n = nums.size(), len = -1, sum = 0;
for (int e : nums)
sum += e;
int target = sum - x;
if (target < 0)
return -1;
for (int left = 0, right = 0, tmp = 0; right < n; ++right) {
tmp += nums[right]; // 进窗口
while (tmp > target) // 判断
{
tmp -= nums[left];
left++;
}
if (tmp == target)
len = max(len, right - left + 1);
}
return len == -1 ? -1 : n - len;
}
};
904. 水果成篮
904. 水果成篮 - 力扣(LeetCode)
解析
题解
class Solution {
public:
int totalFruit(vector<int>& fruits) {
// 013_专题二_滑动窗口_水果成篮_C++
// 转化为:找出一个最长的子数组的长度,子数组中不超过两种类型的水果
// 滑动窗口
// 老三样
// 1. 进窗口
// 2. 出窗口
// 2.1 判断
// 3. 更新结果
// unordered_map<int, int> hash; // 统计出现了多少种水果,用stl可以更方便的解决
int hash[100001] = {0};
int n = fruits.size(), sum = 0, ret = 0;
for (int left = 0, right = 0, kinds = 0; right < n; right++)
{
if (hash[fruits[right]] == 0) kinds++;
hash[fruits[right]]++; // 进窗口
while (kinds > 2) // 判断
{
hash[fruits[left]]--; // 出窗口
if (hash[fruits[left]] == 0) // 当为0的时候,就删除该元素
kinds--;
left++;
}
ret = max(ret, right - left + 1);
}
return ret;
}
};