【LeetCode 算法专题突破】滑动窗口(⭐)

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

前言

学完了双指针算法,滑动窗口那肯定是逃不掉了,我个人感觉他俩就不分家,不把滑动窗口的题目好好刷上一刷我都难受

1. 长度最小的子数组

先来一道经典的滑动窗口试试水

题目链接:209. 长度最小的子数组

题目描述

【LeetCode 算法专题突破】滑动窗口(⭐),LeetCode 算法专题突破,# 数组,算法,leetcode,职场和发展
其实滑动窗口题目的解法都大同小异,我们基本上写几道题目,就能很好的掌握这个算法的思想了,来看代码:

代码

func minSubArrayLen(target int, nums []int) int {
    sum, len, n := 0, math.MaxInt32, len(nums)
    left, right := 0, 0
    for right < n {
        sum += nums[right]
        for sum >= target {
            len = min(len, right-left+1)
            sum -= nums[left]
            left++
        }
        right++
    }
    if len == math.MaxInt32 {
        return 0
    }
    return len
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

我写滑动窗口的题目时,一般会按照这样一个步骤来编写代码:

  1. 使用两个指针作为窗口的左右边界
  2. 右边界往右延伸,数组内容进窗口
  3. 左边界缩小范围,判断如何出窗口

这道题目相对容易,只需要关注 sum 和 target 是否匹配就行,之后遇到类似的题目就按照这样的解题思路来求解即可。

2. 无重复字符的最长子串

还是老样子,多做题,多思考,才能多进步

题目链接:3. 无重复字符的最长子串

题目描述

【LeetCode 算法专题突破】滑动窗口(⭐),LeetCode 算法专题突破,# 数组,算法,leetcode,职场和发展
这道题目其实一眼看过去,有很多解法,可以直接通过暴力解出来,也可以用滑动窗口来进行匹配,直接通过 set 去重,我之前用 C++ 做这道题的时候就是这么做的,但是在题解区学习了一下之后,我也用上了一个很巧妙而且复杂度最低的方法,来看代码:

代码

func lengthOfLongestSubstring(s string) int {
    win := [128]bool{}
    left, len := 0, 0
    for right, v := range s {
        for win[v] == true { // 出现了重复的字符,开始循环去重(代码的核心)
            win[s[left]] = false
            left++
        }
        win[v] = true
        len = max(len, right-left+1)
    }
    return len
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

这段代码可以说也是非常的清晰易懂,这个代码最核心最精华,或者说设计最巧妙的地方就是在他使用了一个 bool 类型的数组来完成去重操作,和滑动窗口的遍历完美融合到了一起。

3. 最大连续1的个数 III

让我们再来一道题目,操练一下使用滑动窗口的能力

题目链接:1004. 最大连续1的个数 III

题目描述

【LeetCode 算法专题突破】滑动窗口(⭐),LeetCode 算法专题突破,# 数组,算法,leetcode,职场和发展
这道题目乍一看,会发现有很多种情况需要考虑,最重要的其实就是思考 K 个 0 该怎么翻转才能实现出最多的连续 1,来看代码:

代码

func longestOnes(nums []int, k int) int {
    left, cnt0, len := 0, 0, 0
    for right, v := range nums {
        if v == 0 {
            cnt0++
        }
        for cnt0 > k {
            if nums[left] == 0 {
                cnt0--
            }
            left++
        }
        len = max(len, right-left+1)
    }
    return len 
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

虽然题目分析起来似乎有很多中情况需要考虑,但是我们可以把问题巧妙的转化一下,从翻转 k 个 0 转化成允许 1 数组中存在 k 个 0,这样这道题目就只需要单纯的计算连续为 1 的数组,然后顺便记录一下数组中 0 的个数即可,这也是代码中的 cnt0 变量的由来~

4. 将 x 减到 0 的最小操作数

我们话不多说,继续来刷下一道题

题目链接:1658. 将 x 减到 0 的最小操作数

题目描述

【LeetCode 算法专题突破】滑动窗口(⭐),LeetCode 算法专题突破,# 数组,算法,leetcode,职场和发展
乍一看,如果我们直接从两边找 target = x 的数感觉会很麻烦,代码也不好写,那我们该怎么做呢?来看代码:

代码

func minOperations(nums []int, x int) int {
    left, right, sum, lenth, target := 0, 0, 0, math.MaxInt32, -x
    for _, v := range nums {
        target += v
    }
    if target < 0 { // 如果全加上都达不到要求就直接返回
        return -1
    }
    for right < len(nums) { 
        sum += nums[right]
        right++
        for sum > target {
            sum -= nums[left]
            left++
        }
        if sum == target {
            lenth = min(lenth, len(nums)-(right-left))
        }
    }
    if lenth == math.MaxInt32 {
        return -1
    }
    return lenth
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

我们可以将问题转化一下,把问题转化成:找出最长的中间子数组,这样我们就能求出最少需要使用的步骤了,也就能使用滑动窗口来解题了,这里我们就是把 target 设置为:数组总和 - x,这样当我们的子数组和 sum == target 的时候,就是符合题目要求的情况了
做了几道滑动窗口的题目之后,我们发现其实滑动窗口算法真正难的不是代码的编写,代码写几遍发现都是同样的写法,真正有难度的是这么样把问题转化成可以使用滑动窗口算法的形式,那怎么样才能想到呢?没有捷径,只有多练,所以我们继续下一题~

5. 水果成篮

咱们继续来练习

题目链接:904. 水果成篮

题目描述

【LeetCode 算法专题突破】滑动窗口(⭐),LeetCode 算法专题突破,# 数组,算法,leetcode,职场和发展
遇到像这种题目话很多的,其实不用管,直接抓关键词就行,读完题目其实很容易就能想到这道题目该怎么做了(有了前几道题目的经验),像这道题这样不需要转换问题思路就能直接做的,其实就非常简单了,来看代码:

代码

func totalFruit(fruits []int) int {
    win := map[int]int{}
    lenth, left := 0, 0
    for right, v := range fruits {
        win[v]++
        for len(win) > 2 {
            win[fruits[left]]--
            if win[fruits[left]] == 0 {
                delete(win, fruits[left])
            }
            left++
        }
        lenth = max(lenth, right-left+1)
    }
    return lenth
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

这里我们使用的是 map 来进行对水果数量的映射,这样比较方便,其实直接用一个数组来映射也是一样的。
咱们接着练习下一道题。

6. 找到字符串中所有字母异位词

题目链接:438. 找到字符串中所有字母异位词

题目描述

【LeetCode 算法专题突破】滑动窗口(⭐),LeetCode 算法专题突破,# 数组,算法,leetcode,职场和发展
来看代码:

代码

func findAnagrams(s string, p string) (ans []int) {
    lens, lenp := len(s), len(p)
    if lenp > lens { // 如果 p 比 s 长就不用找了
        return
    }

    var wins, winp [26]int
    for _, v := range p { 
        winp[v-'a']++
    }

    left, right := 0, 0
    for right < lens {
        wins[s[right]-'a']++ // 入窗口
        right++
        if wins == winp {
            ans = append(ans, left)
            wins[s[left]-'a']-- // 出窗口
            left++
        }
        if right-left+1 > lenp {
            wins[s[left]-'a']-- // 出窗口
            left++
        }
    }

    return ans
}

这道题在我的解法中,需要注意的是,在我们缩窗口的时候记得要让 wins 的字母出窗口,所以就有两个需要出窗口的地方,让 wins 的大小和 winp 始终保持一致,这样就能把所有情况都比较一遍

7. 串联所有单词的子串

刷了这么多题目,最后必须得来一道 hard 证明一下自己~

题目链接:30. 串联所有单词的子串

题目描述

【LeetCode 算法专题突破】滑动窗口(⭐),LeetCode 算法专题突破,# 数组,算法,leetcode,职场和发展
来看代码:

代码

func findSubstring(s string, words []string) (ans []int) {
    if len(words) == 0 {
        return ans
    }

    slen, wlen, clen := len(s), len(words), len(words[0])
    if slen < clen*wlen {
        return ans
    }

    cmp := map[string]int{}
    for _, v := range words { // 用于比较的 cmp
        cmp[v]++
    }

    for i:= 0; i < clen; i++ {
        cnt, win := 0, map[string]int{}
        for left, right := i, i; right <= slen-clen; right+=clen {
            word := s[right:right+clen] // 截取单词 word,一个个进行匹配
            if num, _ := cmp[word]; num != 0 { // 存在 word 这个单词
                for win[word] >= num { // 如果这个 word 数量超过预期,就出窗口
                    win[s[left:left+clen]]--
                    cnt--
                    left+=clen
                }
                win[word]++ // 入窗口 + 计数
                cnt++
            } else { // 不存在 word 这个单词
                for left < right { // 比较中断了,全部 word 出窗口
                    win[s[left:left+clen]]--
                    cnt--
                    left+=clen
                }
                left+=clen // 让 left = right 重新开始(因为最后 right 会 += clen)
            }
            if cnt == wlen {
                ans = append(ans, left)
            }
        }
    }

    return ans
}

这道题目的思路和上一道题非常的像,但是代码的编写难度要高不少,我还是使用一样的思路,对每一个单词进行比较,具体的操作流程如下:

  1. 将需要比较的单词存进 cmp
  2. 因为每个单词的长度相同,所以遍历 len(words) 就能得出所有情况
  3. 接着设置 left,right 遍历整个 s
  4. 然后就开始逐个单词进行匹配,再根据计数求是否符合题目要求

总结

滑动窗口专题的一些经典题目就告一段落啦,如果什么时候对滑动窗口算法的思路亦或者是写代码的方法有疑问,就可以回来重新刷一遍,相信日后再遇到能够使用滑动窗口的题目都能游刃有余,轻松解决~文章来源地址https://www.toymoban.com/news/detail-722157.html

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

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

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

相关文章

  • 【Leetcode刷题-Python/C++】长度最小的子数组(滑动窗口)

    209.长度最小的子数组 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。 输入:target = 7, nums = [2,3,1,2,4,3] 输出:2 解释:子数

    2023年04月08日
    浏览(41)
  • LeetCode 2090. K Radius Subarray Averages【前缀和,滑动窗口,数组】中等

    本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,

    2024年02月11日
    浏览(48)
  • LeetCode 1493. 删掉一个元素以后全为 1 的最长子数组 - 二分 + 滑动窗口

    删掉一个元素以后全为 1 的最长子数组 提示 中等 90 相关企业 给你一个二进制数组 nums ,你需要从中删掉一个元素。 请你在删掉元素的结果数组中,返回最长的且只包含 1 的非空子数组的长度。 如果不存在这样的子数组,请返回 0 。 提示 1: 输入:nums = [1,1,0,1] 输出:3 解

    2024年02月17日
    浏览(42)
  • Java【手撕滑动窗口】LeetCode 209. “长度最小子数组“, 图文详解思路分析 + 代码

    各位读者好, 我是小陈, 这是我的个人主页, 希望我的专栏能够帮助到你: 📕 JavaSE基础: 基础语法, 类和对象, 封装继承多态, 接口, 综合小练习图书管理系统等 📗 Java数据结构: 顺序表, 链表, 堆, 二叉树, 二叉搜索树, 哈希表等 📘 JavaEE初阶: 多线程, 网络编程, TCP/IP协议, HTTP协议

    2024年02月11日
    浏览(44)
  • LeetCode 周赛 342(2023/04/23)容斥原理、计数排序、滑动窗口、子数组 GCB

    本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 前天刚举办 2023 年力扣杯个人 SOLO 赛,昨天周赛就出了一场 Easy - Easy - Medium - Medium 的水场,不得不说 LeetCode 是懂礼数的 😁。 接下来,请你跟着小彭的思路,一步步将问题做难,

    2023年04月24日
    浏览(37)
  • 算法刷题记录-双指针/滑动窗口(LeetCode)

    思路 根据题目描述,我们可以知道,如果要将某个单词定义为可扩张(stretchy),需要满足如下两个条件: 所以,我们在实现的时候,可以通过两个指针p1和p2,分别指向s和word,分别统计连续的相同字符数量c1和c2,然后再通过上述的两个条件进行判断,即:如果 则表示该单

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

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

    2024年02月16日
    浏览(47)
  • 【算法优选】 滑动窗口专题——壹

    基本概念 滑动窗口是一种 基于双指针 的一种思想,两个指针指向的元素之间形成一个窗口。 分类:窗口有两类,一种是 固定大小类 的窗口,一类是 大小动态变化 的窗口。 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长

    2024年02月08日
    浏览(41)
  • 算法专题二:滑动窗口

    长度最小的子数组 思路一: 思路二: 无重复字符的最长子串 思路一: 最大连续1的个数 开头位0 并且k为0算是一个特殊的情况这样的情况有一些考虑就走不出去前面的0而忽略到后面数组自带1,走不到这些1数据导致记录连续1的个数出问题! 将x减小到0的最小操作数 水果成篮

    2024年02月02日
    浏览(51)
  • 【算法专题】滑动窗口

    题目链接 - Leetcode -209.长度最小的子数组 Leetcode -209.长度最小的子数组 题目:给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组[numsl, numsl + 1, …, numsr - 1, numsr] ,并返回其长度。 如果不存在符合条件的子数组,返

    2024年02月05日
    浏览(46)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包