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

文章目录

  • 前言
  • 1. 长度最小的子数组
    • 题目描述
    • 代码
  • 2. 无重复字符的最长子串
    • 题目描述
    • 代码
  • 3. 最大连续1的个数 III
    • 题目描述
    • 代码
  • 4. 将 x 减到 0 的最小操作数
    • 题目描述
    • 代码
  • 5. 水果成篮
    • 题目描述
    • 代码
  • 6. 找到字符串中所有字母异位词
    • 题目描述
    • 代码
  • 7. 串联所有单词的子串
    • 题目描述
    • 代码
  • 总结

前言

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

1. 长度最小的子数组

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

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

题目描述


其实滑动窗口题目的解法都大同小异,我们基本上写几道题目,就能很好的掌握这个算法的思想了,来看代码:

代码

func minSubArrayLen(target int, nums []int) int {sum, len, n := 0, math.MaxInt32, len(nums)left, right := 0, 0for 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. 无重复字符的最长子串

题目描述


这道题目其实一眼看过去,有很多解法,可以直接通过暴力解出来,也可以用滑动窗口来进行匹配,直接通过 set 去重,我之前用 C++ 做这道题的时候就是这么做的,但是在题解区学习了一下之后,我也用上了一个很巧妙而且复杂度最低的方法,来看代码:

代码

func lengthOfLongestSubstring(s string) int {win := [128]bool{}left, len := 0, 0for right, v := range s {for win[v] == true { // 出现了重复的字符,开始循环去重(代码的核心)win[s[left]] = falseleft++}win[v] = truelen = 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

题目描述


这道题目乍一看,会发现有很多种情况需要考虑,最重要的其实就是思考 K 个 0 该怎么翻转才能实现出最多的连续 1,来看代码:

代码

func longestOnes(nums []int, k int) int {left, cnt0, len := 0, 0, 0for 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 的最小操作数

题目描述

在这里插入图片描述
乍一看,如果我们直接从两边找 target = x 的数感觉会很麻烦,代码也不好写,那我们该怎么做呢?来看代码:

代码

func minOperations(nums []int, x int) int {left, right, sum, lenth, target := 0, 0, 0, math.MaxInt32, -xfor _, 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. 水果成篮

题目描述


遇到像这种题目话很多的,其实不用管,直接抓关键词就行,读完题目其实很容易就能想到这道题目该怎么做了(有了前几道题目的经验),像这道题这样不需要转换问题思路就能直接做的,其实就非常简单了,来看代码:

代码

func totalFruit(fruits []int) int {win := map[int]int{}lenth, left := 0, 0for 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. 找到字符串中所有字母异位词

题目描述


来看代码:

代码

func findAnagrams(s string, p string) (ans []int) {lens, lenp := len(s), len(p)if lenp > lens { // 如果 p 比 s 长就不用找了return}var wins, winp [26]intfor _, v := range p { winp[v-'a']++}left, right := 0, 0for 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. 串联所有单词的子串

题目描述


来看代码:

代码

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 { // 用于比较的 cmpcmp[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. 然后就开始逐个单词进行匹配,再根据计数求是否符合题目要求

总结

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/166885.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

asp.net特色商品购物网站系统VS开发sqlserver数据库web结构c#编程Microsoft Visual Studio

一、源码特点 asp.net特色商品购物网站系统 是一套完善的web设计管理系统&#xff0c;系统采用mvc模式&#xff08;BLLDALENTITY&#xff09;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。开发环境为 vs2010&#xff0c;数据库为sqlserver2008&a…

动手实现H5仿原生app前进后退切换效果

动手实现H5仿原生app前进后退切换效果 前言 最近在优化H5页面&#xff0c;我注意到当开发完成的移动端H5页面嵌入到微信小程序或者原生app中时&#xff0c;当触发页面路由切换会与原生app看上去有点格格不入&#xff0c;因为H5页面<router-view>切换路由时是直接替换了…

网站、小程序常见布局样式记录

文章目录 &#x1f380;前言&#xff1a;&#x1f415;网页样式展示小程序&#xff1a;《携程网》&#x1f380;持续更新... &#x1f380;前言&#xff1a; 本篇博客会收藏一些作者见到的网页、小程序页面&#xff0c;目的是用来寻找制作项目网页页面的灵感&#xff0c;有需要…

【最短路径算法】一文掌握Dijkstra算法,详解与应用示例+代码

目录 1 Dijkstra算法 2 Dijkstra算法的步骤 3 Dijkstra算法python实现 4 Dijkstra算法应用示例详解 1 Dijkstra算法 Dijkstra算法&#xff08;迪杰斯特拉算法&#xff09;是一种用于在加权图中查找从一个起始节点到所有其他节点的最短路径的算法。该算法最初由荷兰计算机科…

技巧 | 如何解决 OBS 系统声音无法捕获问题 | Mac

技巧 | 如何解决 OBS 系统声音无法捕获问题 | Mac 问题描述 由于 macOS 系统限制&#xff0c;桌面音频被禁止&#xff0c;导致在使用 OBS 无法录制桌面音频&#xff0c;只能使用自带麦克风录制。 解决方法 Loopback 介绍 借助 Loopback 的强大功能&#xff0c;可以轻松地…

Arduino驱动BMA220三轴加速度传感器(惯性测量传感器篇)

目录 1、传感器特性 2、硬件原理图 3、驱动程序 BMA220的三轴加速度计是一款具有I2C接口的超小型三轴低g加速度传感器断路器,面向低功耗消费市场应用。它可以测量3个垂直轴的加速度,从而在手机、手持设备、计算机外围设备、人机界面、虚拟现实功能和游戏控制器中感知倾斜、…

CUDA学习笔记(八)Branch Divergence and Unrolling Loop

Avoiding Branch Divergence 有时&#xff0c;控制流依赖于thread索引。同一个warp中&#xff0c;一个条件分支可能导致很差的性能。通过重新组织数据获取模式可以减少或避免warp divergence&#xff08;该问题的解释请查看warp解析篇&#xff09;。 The Parallel Reduction …

Hook原理--逆向开发

今天我们将继续讲解逆向开发工程另一个重要内容--Hook原理讲解。Hook&#xff0c;可以中文译为“挂钩”或者“钩子”&#xff0c;逆向开发中改变程序运行的一种技术。按照如下过程进行讲解 Hook概述Hook技术方式fishhook原理及实例符号表查看函数名称总结 一、Hook概述 在逆…

平板有必要买触控笔吗?推荐的ipad手写笔

iPad之所以能吸引这么多人&#xff0c;主要是因为它的功能出色。用来画画、做笔记&#xff0c;也是一种不错的体验。但如果只是用来看电视和打游戏的话&#xff0c;那就真的有点大材小用了。如果你不需要昂贵的苹果电容笔&#xff0c;也不需要用来专业的绘图&#xff0c;那你可…

在软件测试行业这种情况下,凭什么他能拿25k?我却约面试都难?

在当今竞争激烈的软件测试行业中&#xff0c;近期的招聘市场确实面临一些挑战。大量的求职者争相涌入岗位&#xff0c;许多热衷于功能测试的人士甚至难以找到理想的工作机会。更不幸的是&#xff0c;连自动化测试和性能测试这些专业领域也受到了测试开发人员的竞争压力。然而&a…

【瑞吉外卖部分功能补充】

瑞吉外卖部分功能补充 菜品的启售和停售 在浏览器控制台点击对应功能后可以看到前端发送的请求是&#xff1a;http://localhost:9999/dish/status/1?ids1413342036832100354&#xff0c;请求方式为POST。 接收到前端参数后&#xff0c;进行controller层代码补全&#xff0c…

Spark简介

文章目录 一、简介二、安装1、简介2、本地部署(Local模式)2.1 安装2.2 官方WordCount实例 3、Standlong模式3.1 简介2.2 安装集群2.3 官方测试案例 4、Yarn模式3.1 安装3.2 配置历史服务器3.3 配置查看历史日志 5、Mesos模式6、几种模式对比7、常用端口 三、Yarn模式详解1、简介…

Leetcode—1726.同积元组【中等】

2023每日刷题&#xff08;六&#xff09; Leetcode—1726.同积元组 哈希表解题思路 实现代码 class Solution { public:int tupleSameProduct(vector<int>& nums) {unordered_map<int, int>count;int n nums.size();int i, j;for(i 0; i < n - 1; i) {f…

拓扑几何学

目录 一&#xff0c;欧拉定理 1&#xff0c;平面图论图 2&#xff0c;单连通多面体 3&#xff0c;一般多面体 一&#xff0c;欧拉定理 1&#xff0c;平面图论图 在一个联通无向图中&#xff0c;点数-边数面数 1 如&#xff1a; 7-126 1 如果把最外面的五边形外面也算…

机器学习终极指南:统计和统计建模03/3 — 第 -3 部分

系列上文&#xff1a;机器学习终极指南&#xff1a;特征工程&#xff08;02/2&#xff09; — 第 -2 部分 一、说明 在终极机器学习指南的第三部分中&#xff0c;我们将了解统计建模的基础知识以及如何在 Python 中实现它们&#xff0c;Python 是一种广泛用于数据分析和科学计…

大数据分析实践 | pandas数据质量分析

文章目录 &#x1f4da;数据质量评估的五个维度&#x1f4da;口袋妖怪数据质量分析&#x1f407;导入库和数据&#x1f407;检查数据&#x1f407;缺失值分析&#x1f407;重复值检测&#x1f407;异常值检测 &#x1f4da;数据质量评估的五个维度 Coherent: without semantic …

【刷题篇】反转链表

文章目录 一、206.反转链表二、92.反转链表 ||三、25. K 个一组翻转链表 一、206.反转链表 class Solution { public://使用头插//三个指针也可以ListNode* reverseList(ListNode* head) {if(headnullptr)return nullptr;ListNode* curhead;ListNode* newheadnew ListNode(0);L…

VR智能家居虚拟连接仿真培训系统重塑传统家居行业

家居行业基于对场景的打造及设计&#xff0c;拥有广阔前景&#xff0c;是众多行业里面成为最有可能进行元宇宙落地的应用场景之一。 家居行业十分注重场景的打造及设计&#xff0c;而元宇宙恰恰能通过将人工智能、虚拟现实、大数据、物联网等技术融合提升&#xff0c;带来身临其…

国产开发板上打造开源ThingsBoard工业网关--基于米尔芯驰MYD-JD9X开发板

本篇测评由面包板论坛的优秀测评者“JerryZhen”提供。 本文将介绍基于米尔电子MYD-JD9X开发板打造成开源的Thingsboard网关。 Thingsboard网关是一个开源的软件网关&#xff0c;采用python作为开发语言&#xff0c;可以部署在任何支持 python 运行环境的主机上&#xff0c;灵…

Linux 救援模式

Linux突然坏了 第三次坏了 第一次是找不到盘&#xff0c;修复好了 第二次是找不到卷&#xff0c;但是能启动&#xff0c;启动界面选择救援模式&#xff0c;可以正常使用 第三次&#xff0c;尝试修复卷&#xff0c;启动后&#xff0c;找不到文件系统了&#xff0c;只能从光盘…