当前位置：首页 > news >正文

算法刷题Day9 5.18:leetcode定长滑动窗口3道题，结束定长滑动窗口,用时1h

news 来源：原创 2025/7/30 10:52:14

12. 1852.每个子数组的数字种类数

1852. 每个子数组的数字种类数 - 力扣（LeetCode）

思想

找到nums 所有长度为 k 的子数组中不同元素的数量。
返回一个数组 ans，其中 ans[i] 是对于每个索引 0 <= i <= n - k，nums[i..(i + k - 1)] 中不同元素的数量。

代码

c++:

class Solution {
public:vector<int> distinctNumbers(vector<int>& nums, int k) {int n=nums.size();vector<int> res(n-k+1);map<int,int> mp;for(int i=0;i<k;++i){mp[nums[i]]++;}int right=k;for(int i=0;i<=n-k;++i){res[i]=mp.size();if(right<n) mp[nums[right]]++; // right是开区间，访问nums[right]可能会越界mp[nums[right-k]]--;if(mp[nums[right-k]]==0){mp.erase(nums[right-k]);}right++;}return res;}
};

注意:right是开区间，访问nums[right]可能会越界

13. 1151.最少交换次数来组合所有的1(中等，重点学习思想)

思想

1.你需要通过交换位置，将数组中 任何位置 上的 1 组合到一起，并返回所有可能中所需 最少的交换次数。
2.题意转换->数组1的总数为k，长度为k的定长滑动窗口移动，统计量为当前窗口1的数量sum1,交换次数就是k-sum1

代码

c++:

class Solution {
public:int minSwaps(vector<int>& data) {int n = data.size();int k = 0;for (int i = 0; i < n; ++i) {if (data[i] == 1)k++;}int res = INT_MAX, sum1 = 0;for (int i = 0; i < n; ++i) {if (data[i] == 1)sum1++;if (i < k - 1)continue;res = min(res, k - sum1);if (data[i - k + 1] == 1)sum1--;}return res;}
};

14. 2107.分享K个糖果后独特口味的数量(中等)

2107. 分享 K 个糖果后独特口味的数量 - 力扣（LeetCode）

思想

1.给她 k 个连续的糖果，但你想保留尽可能多的糖果口味。在与妹妹分享后，返回最多可保留的独特口味的糖果。

代码

c++:

class Solution {
public:int shareCandies(vector<int>& candies, int k) {int n = candies.size();map<int, int> mp;for (int i = 0; i < n; ++i) {mp[candies[i]]++;}if (k == 0)return (int)mp.size(); //.size()返回类型为size_t,有些地方的自己强制转换为intint res = 0;for (int i = 0; i < n; i++) {mp[candies[i]]--;if (mp[candies[i]] == 0)mp.erase(candies[i]);if (i < k - 1)continue;res = max(res, (int)mp.size());mp[candies[i - k + 1]]++;}return res;}
};

注意:
1…size()返回类型为size_t,有些地方的自己强制转换为int