最新公告
  • 欢迎您光临起源地模板网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入钻石VIP
  • 【数据结构与算法学习】滑动窗口相关算法题

    正文概述 掘金(麻将大神徐大胖JOY)   2021-04-25   58

    一、滑动窗口相关概念

    1.1 概念

    滑动窗口算法可以用以解决数组/字符串的子元素问题,它可以将嵌套的循环问题,转换为单循环问题,降低时间复杂度。

    1.1 应用场景的特点

    • 需要输出或比较的结果在原数据结构中是连续排列
    • 每次窗口滑动时,只需观察窗口两端元素的变化,无论窗口多长,每次只操作两个头尾元素,当用到的窗口比较长时,可以显著减少操作次数
    • 窗口内元素的整体性比较强,窗口滑动可以只通过操作头尾两个位置的变化实现,但对比结果时往往要用到窗口中所有元素

    二、算法题

    1.1 无重复字符的最长子串[中等]

    ## 描述: 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
    
    输入: s = "abcabcbb"
    输出: 3 
    解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
    
    输入: s = "bbbbb"
    输出: 1
    解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
    
    输入: s = "pwwkew"
    输出: 3
    解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
         请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
    
    输入: s = ""
    输出: 0
    
    //  解题思路:滑动窗口
    const lengthOfLongestSubstring = (str) => {
        let tempStr = '';
        let left = 0;
        let right = 0;
        const len = str.length;
        let maxNum = 0;
    
        while(right < len) {
            right++;
            tempStr = str.substring(left, right);
            const tempLength = tempStr.length;
            // 去重是否长度一致:一致表示无重复字符串
            const isUnique = Array.from(new Set(tempStr)).length === tempLength;
            isUnique && (maxNum = Math.max(maxNum, tempLength));
            (!isUnique) && left++;
        }
        return maxNum;
    };
    

    1.2 长度最小的子数组 [中等]

    ## 描述
    给定一个含有 n 个正整数的数组和一个正整数 target 。
    
    找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
    
    输入:target = 7, nums = [2,3,1,2,4,3]
    输出:2
    解释:子数组 [4,3] 是该条件下的长度最小的子数组。
    
    输入:target = 4, nums = [1,4,4]
    输出:1
    
    输入:target = 11, nums = [1,1,1,1,1,1,1,1]
    输出:0
    
    //  解题思路:滑动窗口
    const minSubArrayLen = (target, nums) => {
        // 初始化滑动窗口左右指针
        let left = 0; 
        let right = 0;
        // 初始化最小长度
        let minSubLen = Infinity;
    
        while(right <= nums.length && left <= right) {
            const subArr = nums.slice(left, right);
            const sum = subArr.reduce((x, y) => x + y, 0); // 这里比较费时间,可以优化
            if (sum >= target) {
                left++;
                minSubLen = Math.min(minSubLen, subArr.length);
            } else {
                right++;
            }
        }
        return minSubLen ===  Infinity ? 0 : minSubLen;
    };
     
    // 优化后解法
    const minSubArrayLen = (s, nums) => {
      let minLen = Infinity;
      let i = 0;
      let j = 0;
      let sum = 0;
      while (j < nums.length) {   // 主旋律是扩张,找可行解
        sum += nums[j];
        while (sum >= s) {        // 间歇性收缩,优化可行解
          minLen = Math.min(minLen, j - i + 1);
          sum -= nums[i];
          i++;
        }
        j++;
      }
      return minLen === Infinity ? 0 : minLen; // 从未找到可行解,返回0
    };
    

    1.3 字符串的排列 [中等]

    ## 描述
    给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。
    换句话说,第一个字符串的排列之一是第二个字符串的 子串 。
    
    输入: s1 = "ab" s2 = "eidbaooo"
    输出: True
    解释: s2 包含 s1 的排列之一 ("ba")
    
    输入: s1= "ab" s2 = "eidboaoo"
    输出: False
    
    const isEqual = (s1, s2) => Array.from(s1).sort().join('') === Array.from(s2).sort().join('');
    
    const checkInclusion = (s1, s2) => {
        const s1Length = s1.length;
        let left = 0;
        let right = s1Length;
        while(right <= s2.length) {
            const tempStr = s2.substring(left, right);
            if (isEqual(tempStr, s1)) {return true;}
            left++;
            right = left + s1Length;
        }
        return false;
    };
    
    ## 主要使用 hash 去判断窗口和 s1 是否一致,用 sort 太浪费性能了, 上面的方法超时了,用map的方式对比
    

    1.4 最小覆盖子串 【困难】

    1.5 滑动窗口最大值 【困难】

    ## 描述
    给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。
    
    输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
    输出:[3,3,5,5,6,7]
    解释:
    滑动窗口的位置                最大值
    ---------------               -----
    [1  3  -1] -3  5  3  6  7       3
     1 [3  -1  -3] 5  3  6  7       3
     1  3 [-1  -3  5] 3  6  7       5
     1  3  -1 [-3  5  3] 6  7       5
     1  3  -1  -3 [5  3  6] 7       6
     1  3  -1  -3  5 [3  6  7]      7
    
    输入:nums = [1], k = 1
    输出:[1]
    
    输入:nums = [1,-1], k = 1
    输出:[1,-1]
    
    function maxSlidingWindow (nums, k) {
        // 初始化窗口左右指针
        let left = 0;
        let right = k;
        const length = nums.length;
        const result = [];
        while(right <= length) {
            const subArr = nums.slice(left, right);
            result.push(Math.max.apply(null, subArr));
            left++;
            right = left + k;
        };
        return [...result];
    };
    
    // 上面的解法超时了
    
    

    1.6 串联所有单词的子串【困难】

    1.7 最小区间

    1.8 最小窗口子序列 【会员】

    1.9 至多包含两个不同字符的最长子串【会员】


    起源地 » 【数据结构与算法学习】滑动窗口相关算法题

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    模板不会安装或需要功能定制以及二次开发?
    请QQ联系我们

    发表评论

    还没有评论,快来抢沙发吧!

    如需帝国cms功能定制以及二次开发请联系我们

    联系作者

    请选择支付方式

    ×
    迅虎支付宝
    迅虎微信
    支付宝当面付
    余额支付
    ×
    微信扫码支付 0 元