leetcode:滑动窗口

这篇具有很好参考价值的文章主要介绍了leetcode:滑动窗口。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

1.定长滑动窗口

1.1 几乎唯一子数组的最大和(使用map来计数)

1.2 长度为k子数组中的最大和

2.不定长滑动窗口

2.1 最多k个重复元素的最长子数组

2.2 绝对差不超过限制的最长连续子数组(multiset)

2.3 将x减到0的最小操作数(正难则反 逆向思维)

2.4 统计最大元素出现至少k次的子数组

2.5 乘积小于k的子数组


1.定长滑动窗口

1.1 几乎唯一子数组的最大和(使用map来计数)

leetcode:滑动窗口,leetcode,算法,数据结构

class Solution {
public:
    long long maxSum(vector<int>& nums, int m, int k) {
        long long ans = 0, sum = 0;
        unordered_map<int, int>
            cnt; //如何把重复的数字算成一个数字,就要用到数组来进行计数了,重复的数字对应的值大于1
        for (int i = 0; i < k - 1; i++) //先求前k-1个数
        {
            sum += nums[i];
            cnt[nums[i]]++;
        }
        for (int i = k - 1; i < nums.size(); i++) //进去一个出来一个,满足k个数
        {
            sum += nums[i];
            cnt[nums[i]]++;
            if (cnt.size() >= m) //判断是否有m个不相同的数
                ans = max(ans, sum);

            int out = nums[i - k + 1];
            sum -= out;
            if (--cnt[out] == 0) //如果只出现1次,可以直接删除
                cnt.erase(out);
        }
        return ans;
    }
};

      这道题让我们求最大的问题,而且是连续非空的子数组,很容易想到滑动窗口,但滑动窗口有定长和不定长两种,题中说长度为k,说明是定长的,要求长度为k的几乎唯一子数组的最大和,我们可以先求前k-1个数,这样之后进来一个出去一个,始终是k个数,题目要求该子数组至少有m个不相同的数,我们怎么记录是否有m个不相同的数呢?我们可以用map来记录有几个不相同的数,同时记录每个数字出现了几次,如果某个子数组有m个不相同的数,就更新答案,之后就要出去一个数,如果出去的这个数只出现了1次,就要直接从map中删除。最后返回答案

1.2 长度为k子数组中的最大和

leetcode:滑动窗口,leetcode,算法,数据结构

class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        long long res = 0, sum = 0;
        for (int i = 0; i < k - 1; i++) {
            sum += nums[i];
            mp[nums[i]]++;
        }
        for (int i = k - 1; i < nums.size(); i++) {
            sum += nums[i];
            mp[nums[i]]++;
            if (mp.size() == k ) res =max(res,sum);//这个已经去重了,只要当mp的大小等于k时,才会更新res的大小,否则说明有重复数字,不更新
            int x = nums[i - k + 1];
            if (--mp[x] == 0) mp.erase(x);//及时清除为0的数字
            sum -= x;
        }
        return res;
    }
};

      这道题也是定长滑动窗口,要求子数组长度为k,且元素各不相同,和上一道题很相似,也要用map,值得注意的是什么时候我们更新答案,只有当map中的元素个数等于k时,说明子数组长度为k,且元素各不相同,这时候更新答案,其他都是不断滑动的过程。

2.不定长滑动窗口

2.1 最多k个重复元素的最长子数组

leetcode:滑动窗口,leetcode,算法,数据结构

class Solution {
public:
    int maxSubarrayLength(vector<int>& nums, int k) {
        unordered_map<int,int>cnt;
        int ans=0,l=0;
        for(int r=0;r<nums.size();r++)
        {
            cnt[nums[r]]++;
            while(cnt[nums[r]]>k)//如果有元素的出现频率大于k,就要不断左移左指针,直到这个元素的出现频率小于等于k,如果这个元素
                cnt[nums[l++]]--;
            ans=max(ans,r-l+1);
        }
        return ans;
    }
};

     这个没有规定长度,要求满足条件的最长子数组,很明显是不定长滑动窗口的问题。最多k个重复元素说明我们要记录元素出现了几次,一旦超过了k次,我们就要开始滑动,直到子数组没有一个元素的出现频率大于k,否则不断更新答案。

2.2 绝对差不超过限制的最长连续子数组(multiset)

leetcode:滑动窗口,leetcode,算法,数据结构

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        multiset<int>st;//关键在于找每个区间的最大值和最小值,如果遍历寻找,就会超时,所以要找到一个合适的数据结结构
        //我们知道set/multiset/map是有序的,set会去重,所以我们使用multiset
        int l=0;
        int res=0;
        for(int r=0;r<nums.size();r++)
        {
            st.insert(nums[r]);
            while(*st.rbegin()-*st.begin()>limit)
            {
                st.erase(st.find(nums[l]));
                l++;
            }
            res=max(res,r-l+1);
        }
        return res;
    }
};

      这道题的关键在于求每个区间的最大值和最小值,首先我们要把元素放到multiset中,它不仅不会去重,而且是有序的,改变顺序并不影响答案,这样我们使用两个迭代器rbegin()、begin()分别求逆序第一个元素和正序第一个元素,两者之差就是绝对差,如果大于限制,我们就不断滑动窗口,直到绝对值小于等于限制,更新答案。

2.3 将x减到0的最小操作数(正难则反 逆向思维)

leetcode:滑动窗口,leetcode,算法,数据结构

class Solution {
public:
    int minOperations(vector<int> &nums, int x) {   //正难则反 逆向思维
        int target = accumulate(nums.begin(), nums.end(), 0) - x;
        if (target < 0) return -1;
        int ans = -1, l = 0, sum = 0, n = nums.size();
        for (int r = 0; r < n; r++) {
            sum += nums[r];
            while (sum > target) sum -= nums[l++]; 
            if (sum == target) ans = max(ans, r - l + 1);
        }
        return ans < 0 ? -1 : n - ans;
    }
};

      这道题借用灵神的思路,正难则反,逆向思维,我们如果维护两个窗口的和,使得和等于x肯定是很麻烦的,那不如我们只维护一个窗口,这个窗口的和要等于整数数组nums的和sum-x,这样只用维护一个区间,不得不说,这个思维太帅了。accumulate函数是用来求某个区间元素的和,0为初始值

2.4 统计最大元素出现至少k次的子数组

leetcode:滑动窗口,leetcode,算法,数据结构

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int k) {
         long long ans=0;
         int mx=*max_element(nums.begin(),nums.end());
         int cnt=0,left=0;        
         for(auto x:nums)
         {
             if(x==mx)cnt++;
             while(cnt==k)
             {
                 if(nums[left]==mx)
                 {
                     cnt--;
                 }
                 left++;
             }
             ans+=left;
         }
         return ans;
    }
};

      这道题我们首先用max_element函数找出数组最大值,然后就对最大值出现的次数进行计数,如果子数组中最大值出现的次数等于k,那么我们就要滑动,寻找下一个满足条件的子数组,如果左端点对应的值等于最大值,cnt--,左端点向右移动,直到cnt!=k,此时更新答案+left,为什么要加left,因为left是cnt==k进入循环向右移动,left++,直到cnt!=k,退出循环得到了,之前的子数组全部满足要求,所以直接加left。

2.5 乘积小于k的子数组

leetcode:滑动窗口,leetcode,算法,数据结构

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if(k<=1)return 0;
        int ans=0,mul=1,l=0;
        for(int r=0;r<nums.size();r++)
        {
            mul*=nums[r];
            while(mul>=k)
            {
                 mul/=nums[l];
                 l++;
            }
            ans+=r-l+1;
        }
        return ans;
    }
};

     这道题和上一道题很类似,如果[l,r]区间内子数组的乘积小于k,那么[l+1,r],[l+2,r]...[r,r]全部小于k,个数为r-l+1,更新答案每次加上r-l+1即可。文章来源地址https://www.toymoban.com/news/detail-781427.html

到了这里,关于leetcode:滑动窗口的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法|滑动窗口No.1】leetcode209. 长度最小的子数组

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月08日
    浏览(42)
  • python - leetcode - 424. 替换后的最长重复字符【经典题解 - 贪心滑动窗口算法】

    描述: 给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符,并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。 在执行上述操作后,返回包含相同字母的最长子字符串的长度。 示例 1: 示例 2: 提示: 1 = s.length = 105 s 仅由大写英文字母组成 0 =

    2024年02月16日
    浏览(47)
  • 【算法与数据结构】112、LeetCode路径总和

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :本题通过计算根节点到叶子节点路径上节点的值之和,然后再对比目标值。利用文章【算法和数据结构】257、LeetCode二叉树的所有路径中的递归算法。 这里要注意,默认路径之和是

    2024年02月11日
    浏览(53)
  • 【算法与数据结构】62、LeetCode不同路径

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :机器人只能向下或者向右移动,那么到达(i,j)位置的路径和(i-1,j)以及(i,j-1)有关。那么我们就得到的动态规划的表达式 d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + d p [ i ] [ j − 1 ] dp[i][

    2024年01月18日
    浏览(67)
  • 【算法与数据结构】343、LeetCode整数拆分

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :博主做这道题的时候一直在思考,如何找到 k k k 个正整数, k k k 究竟为多少合适。从数学的逻辑上来说,将 n n n 均分为 k k k 个数之后, k k k 个数的乘积为最大(类似于相同周长

    2024年01月17日
    浏览(52)
  • 【算法与数据结构】474、LeetCode一和零

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :本题要找strs数组的最大子集,这个子集最多含有 m m m 个0和 n n n 个1。本题也可以抽象成一个01背包的问题。其中,strs内的元素就是物品,而 m m m 和 n n n 就是背包的维度。 d p [

    2024年01月22日
    浏览(41)
  • 【算法与数据结构】494、LeetCode目标和

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :本题和这道题【算法与数据结构】1049、LeetCode 最后一块石头的重量 II类似,同样可以转换成01背包问题。下面开始论述。假设添加正号的整数子集和为 p o s i t i v e positive p os i t

    2024年01月20日
    浏览(44)
  • 数据结构算法leetcode刷题练习(1)

    给定一个三角形 triangle ,找出自顶向下的最小路径和。 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标

    2023年04月24日
    浏览(54)
  • 【python与数据结构】(leetcode算法预备知识)

    笔记为自我总结整理的学习笔记,若有错误欢迎指出哟~ 1.数字类型: 整数(int):表示整数值,例如 1、-5、100。 浮点数(float):表示带有小数部分的数字,例如 3.14、-0.5、2.0。 复数(complex):表示实部和虚部的复数,例如 2+3j。 2.布尔类型(bool): 表示真(True)或假(

    2024年02月08日
    浏览(39)
  • 【算法与数据结构】377、LeetCode组合总和 Ⅳ

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :本题明面上说是组合,实际上指的是排列。动态规划排列组合背包问题需要考虑遍历顺序。 d p [ i ] dp[i] d p [ i ] 指的是nums数组中总和为target的元素排列的个数。 d p [ i ] dp[i] d p [

    2024年01月23日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包