Leetcode with Golang 滑动窗口 Part1

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

滑动窗口的定义:

滑动窗口这一个技巧主要运用于处理数组问题上,一般用于“子串”问题。精髓是,维护一个里面装着元素的“窗口”,在将新元素装进“窗口”的同时,根据题意,把不符合题意的元素踢出“窗口”。

滑动窗口的模板:

right:=0
left:=0
for right<len(数组或字符串){
  n = 数组[right]
  right+=1
  for (窗口需要收缩的时候,判断){
    l = 数组[left]
    ...
    left+=1
  }
}

接下来看几道题目:

Leetcode 209.长度最小的子数组

https://leetcode.cn/problems/minimum-size-subarray-sum/

题目简介:找到长度最短的一个子数组。并且数组内数字的和>=target

Leetcode with Golang 滑动窗口 Part1,Golang,leetcode,算法

题目分析:窗口不断扩大,当窗口里的元素的总和满足条件后(>=target),窗口缩小,即target减去窗口左端的数。然后再用一个变量记录窗口的大小,最小值随时更新。直接用模板就好了:

func min(i, j int) int {
    if i >= j {
        return j
    } else {
        return i
    }
}
func minSubArrayLen(target int, nums []int) int {
    sum := 0
    right := 0
    left := 0
    res := 10000000
    for right < len(nums) {
        n := nums[right]
        right += 1
        sum += n
        for sum >= target {
            sum -= nums[left]
            res = min(res, right-left)
            left += 1
        }
    }
    if res == 10000000 {
        return 0
    }
    return res
}

 文章来源地址https://www.toymoban.com/news/detail-805930.html

Leetcode 3.无重复的最长字串

给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。

 

https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/

Leetcode with Golang 滑动窗口 Part1,Golang,leetcode,算法

func lengthOfLongestSubstring(s string) int {
    right := 0
    left := 0
    res := 0
    check_dict := make(map[string]int)
    for right < len(s) {
        word := string(s[right])
        if _, exist := check_dict[word]; !exist {
            check_dict[word] = 1
        } else {
            check_dict[word] += 1
        }
        right += 1
        for check_dict[word] > 1 {
            l := string(s[left])
            left += 1
            check_dict[l] -= 1
        }
        if right-left > res {
            res = right - left
        }

    }
    return res

}

LEETCODE 904.水果成篮

https://leetcode.cn/problems/fruit-into-baskets/description/

题目有点拗口,简单解释:“窗口内”只能含有两种数字。问窗口最长能有多长?

可以用一个字典来装元素。当字典中出现3种及以上数字时,开始收缩窗口。有一个要点,当元素的个数为“0”时,记得把键值对删除。

Leetcode with Golang 滑动窗口 Part1,Golang,leetcode,算法

func totalFruit(fruits []int) int {
    right := 0
    left := 0
    res := 0
    dict := make(map[int]int)
    for right < len(fruits) {
       n := fruits[right]
        right+=1
       if _, exist := dict[n]; !exist {
          dict[n] = 1
       } else {
          dict[n] += 1
       }
       for len(dict) > 2 {
          l := fruits[left]
          left += 1
          dict[l] -= 1
          if dict[l] == 0 {
                delete(dict,l)
          }
       }
        if right-left >res{
            res = right-left
        }
    }
    return res
}

 

 

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

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

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

相关文章

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

    学完了双指针算法,滑动窗口那肯定是逃不掉了,我个人感觉他俩就不分家,不把滑动窗口的题目好好刷上一刷我都难受 先来一道经典的滑动窗口试试水 题目链接:209. 长度最小的子数组 其实滑动窗口题目的解法都大同小异,我们基本上写几道题目,就能很好的掌握这个算

    2024年02月07日
    浏览(52)
  • LeetCode239.滑动窗口最大值

    看到这道题我就有印象, 我在剑指offer里面做过这道题,我记得当时用的是优先队列,然后我脑子里一下子就有了想法,拿优先队列作为窗口,每往右移动一步,把左边的数remove掉,把右边的数add进来,然后把队头,也就是窗口中最大的元素放入答案数组,然后就写出了如下

    2024年02月11日
    浏览(44)
  • leetcode-239-滑动窗口最大值

    题意描述: 给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 示例: 输入:nums = [1,3,-1,-3,5,3,6,7], k = 3 输出:[3,3,5,5,6,7] 解释: 滑动

    2024年02月07日
    浏览(49)
  • LeetCode算法小抄--滑动窗口算法

    ⚠申明: 未经许可,禁止以任何形式转载,若要引用,请标注链接地址。 全文共计6244字,阅读大概需要3分钟 🌈更多学习内容, 欢迎👏关注👀文末我的个人微信公众号:不懂开发的程序猿 个人网站:https://jerry-jy.co/ 滑动窗口算法 思路 1、我们在字符串 S 中使用双指针中的

    2023年04月09日
    浏览(38)
  • 【滑动窗口】leetcode1004:最大连续1的个数

    最大连续1的个数  这道题要我们找最大连续1的个数,看到“连续”二字,我们要想到滑动窗口的方法。滑动窗口的研究对象是一个连续的区间,这个区间需要满足某个条件。那么本题要找的是怎样的区间呢?是一个通过翻转0后得到连续1的区间,而最多可以翻转k个字符。 故

    2024年02月11日
    浏览(39)
  • 【LeetCode热题100】【子串】滑动窗口最大值

    题目 给你一个整数数组  nums ,有一个大小为  k   的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的  k  个数字。滑动窗口每次只向右移动一位。 返回  滑动窗口中的最大值  。 示例 1: 示例 2: 提示: 1 = nums.length = 105 -104 = nums[i] = 104 1 =

    2024年01月19日
    浏览(48)
  • 剑指 Offer 59 - I. 滑动窗口的最大值 / LeetCode 239. 滑动窗口最大值(优先队列 / 单调队列)

    链接:剑指 Offer 59 - I. 滑动窗口的最大值;LeetCode 239. 滑动窗口最大值 难度:困难 下一篇:剑指 Offer 59 - II. 队列的最大值(单调队列) 给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗

    2024年02月15日
    浏览(41)
  • 算法刷题记录-双指针/滑动窗口(LeetCode)

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

    2024年02月09日
    浏览(41)
  • leetcode76. 最小覆盖子串(滑动窗口-java)

    难度 - 困难 原题链接 - 最小覆盖字串 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。 注意: 对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果

    2024年02月11日
    浏览(40)
  • 【滑动窗口】【map】LeetCode:76最小覆盖子串

    【二叉树】【单调双向队列】LeetCode239:滑动窗口最大值 C++算法:滑动窗口总结 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。 注意: 对于 t 中重复字符,我们寻找的子字符串中该字

    2024年02月03日
    浏览(37)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包