当前位置: 首页 > news >正文

滑动窗口(一)

文章目录

  • Leetcode209. 长度最小的子数组
    • 题目
    • 解法一(暴力求解)(超时)
    • 解法二(滑动窗口)
  • Leetcode3. 无重复字符的最长子串
    • 题目
    • 解法一(暴力求解)
    • 解法二(滑动窗口)
  • Leetcode1004. 最大连续1的个数 III
    • 题目
    • 解法(滑动窗口)

Leetcode209. 长度最小的子数组

题目

Leetcode209. 长度最小的子数组

解法一(暴力求解)(超时)

暴力枚举出所有子数组的和 O(n^2);

代码

class Solution 
{
public:int minSubArrayLen(int target, vector<int>& nums) {int n = nums.size();int res = INT_MAX;// 记录答案for(int i = 0; i < n; i++){int sum = 0;for(int j = i; j < n; j++){sum += nums[j];if(sum >= target){res = min(res, j - i + 1);break;}}}return res == INT_MAX ? 0 : res;}
};

解法二(滑动窗口)

开始将右端元素划⼊窗⼝中,统计出此时窗⼝内元素的和:

  • 如果窗⼝内元素之和⼤于等于target :更新结果,并且将左端元素划出去的同时继续判
    断是否满⾜条件并更新结果(因为左端元素可能很小,划出去之后依旧满⾜条件)
  • 如果窗⼝内元素之和不满⾜条件: right++ ,另下⼀个元素进⼊窗⼝。

O(N^2)

代码

class Solution 
{
public:int minSubArrayLen(int target, vector<int>& nums) {int res = INT_MAX;int sum = 0;for(int left = 0, right = 0; right < nums.size(); right++){sum += nums[right];//进窗口while(sum >= target)//判断{res = min(res, right - left + 1);//更新结果sum -= nums[left++];//出窗口}}return res == INT_MAX? 0:res;}};

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

题目

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

解法一(暴力求解)

从每一个字母开始向后枚举无重复字符的字串最大的长度
利用哈希表来统计每一个字符出现的次数

代码

class Solution 
{
public:int lengthOfLongestSubstring(string s) {int res = 0;int n = s.size();for(int i = 0; i < n; i++){//利用数组模拟哈希统计字符出现次数int hash[128] = {0};for(int j = i; j < n; j++){hash[s[j]]++;//统计字符的次数if(hash[s[j]] > 1)//判断{break;}res = max(res, j - i + 1);}}return res;}
};

解法二(滑动窗口)

右端元素 ch 进⼊窗⼝的时候,哈希表统计这个字符的频次:

  • 如果这个字符出现的频次超过 1 ,说明窗⼝内有重复元素,那么就从左侧开始划出窗⼝,
    直到 ch 这个元素的频次变为 1 ,然后再更新结果。
  • 如果没有超过 1 ,说明当前窗⼝没有重复元素,可以直接更新结果。
    代码
class Solution 
{
public:int lengthOfLongestSubstring(string s) {int res = 0;int n = s.size();int hash[128] = {0};//利用数组模拟哈希统计字符出现次数for(int left = 0, right = 0; right < n; right++){hash[s[right]]++;//进窗口while(hash[s[right]] > 1)//判断{hash[s[left]]--;//出窗口left++;}res = max(res, right - left + 1);// 更新结果}return res;}
};

Leetcode1004. 最大连续1的个数 III

题目

Leetcode1004. 最大连续1的个数 III

解法(滑动窗口)

我们发现一会从左边开始减、一会从右边开始减,这样做起来十分麻烦,因为我们不确定从哪边开始,所以我们不要想着如何反转,而是一段连续的1中间有k个0。
因此,我们将题目转化为了求一段最长连续区间,要求其中的0不能超过k

代码

class Solution 
{
public:int longestOnes(vector<int>& nums, int k) {int res = 0;int zero = 0;//统计0的个数for(int left = 0, right = 0; right < nums.size(); right++){if(nums[right] == 0) zero++;//进窗口while(zero > k)//判断{if(nums[left++] == 0) zero--;//出窗口}res = max(res, right - left + 1);//更新结果}return res;}
};

相关文章:

滑动窗口(一)

文章目录 Leetcode209. 长度最小的子数组题目解法一(暴力求解)&#xff08;超时&#xff09;解法二&#xff08;滑动窗口&#xff09; Leetcode3. 无重复字符的最长子串题目解法一&#xff08;暴力求解&#xff09;解法二&#xff08;滑动窗口&#xff09; Leetcode1004. 最大连…...

寒假 day1

1、请简述栈区和堆区的区别? 2、有一个整形数组:int arr[](数组的值由外部输入决定)&#xff0c;一个整型变量: x(也 由外部输入决定)。要求: 1)删除数组中与x的值相等的元素 2)不得创建新的数组 3)最多只允许使用单层循环 4)无需考虑超出新数组长度后面的元素&#xff0c;所以…...

DATAX改造支持geometry类型数据同步

数据库使用postgresql安装了postgis插件存储了geometry空间数据&#xff0c;想使用datax做数据同步&#xff0c;但datax本身不支持geometry类型数据&#xff0c;如何改造呢&#xff1f; 1.首先下载已改造支持geometry类型的datax引擎&#xff0c;下载地址 https://download.c…...

Vue中keep-alive的作用、原理及应用场景

在进行Vue开发的过程中&#xff0c;我们经常会遇到需要进行组件缓存的场景&#xff0c;这时候Vue提供的keep-alive组件就派上了用场。keep-alive组件是Vue内置的一个抽象组件&#xff0c;它可以将其包裹的组件进行缓存&#xff0c;提高组件的性能&#xff0c;同时也可以节省服务…...

SpringBoot集成Redisson实现限流(二)

1. 简介 Springboot集成Redisson默认的限流器为令牌桶型限流器&#xff0c;底层是通过lua脚本去实现的。 通过lua脚本我们可以去实现一个滑动窗口限流器&#xff0c;利用ZSET格式数据就可以轻松实现。 springboot集成Redisson就不做讲解&#xff0c;可以参考&#xff1a;sprin…...

【2024美赛E题】985博士解题思路分析(持续更新中)!

【2024美赛E题】985博士解题思路分析&#xff01; 加群可以享受定制等更多服务&#xff0c;或者搜索B站&#xff1a;数模洛凌寺 联络组织企鹅&#xff1a;936670395 以下是E题老师的解题思路&#xff08;企鹅内还会随时更新文档&#xff09;&#xff1a; 2024美赛E题思路详解…...

北朝隋唐文物展亮相广西,文物预防性保护网关保驾护航

一、霸府名都——太原博物馆收藏北朝隋朝文物展 2月1日&#xff0c;广西民族博物馆与太原博物馆携手&#xff0c;盛大开启“霸府名都——太原博物馆北朝隋文物展”。此次新春展览精选了北朝隋唐时期150多件晋阳文物珍品。依据“巍巍雄镇”“惊世古冢”“锦绣名都”三个单元&am…...

回归预测 | Matlab实现WOA-CNN-LSTM-Attention鲸鱼算法优化卷积长短期记忆网络注意力多变量回归预测(SE注意力机制)

回归预测 | Matlab实现WOA-CNN-LSTM-Attention鲸鱼算法优化卷积长短期记忆网络注意力多变量回归预测&#xff08;SE注意力机制&#xff09; 目录 回归预测 | Matlab实现WOA-CNN-LSTM-Attention鲸鱼算法优化卷积长短期记忆网络注意力多变量回归预测&#xff08;SE注意力机制&…...

ubuntu离线安装k8s

目录 一、前期准备 二、安装前配置 三、安装docker 四、安装cri-dockerd 五、部署k8s master节点 六、整合kubectl与cri-dockerd 七、网络等插件安装 八、常见问题及解决方法 一、前期准备 ①ubuntu系统 本地已安装ubuntu系统&#xff0c;lsb_release -a命令查看版本信…...

学成在线:媒体资源管理系统(MAM)

媒体资源管理系统(MAM) 媒体资源管理系统(Media Asset Management)是建立在多媒体、网络、数据库和数字存储等先进技术基础上的一个对各种媒体及内容进行数字化存储、管理以及应用的总体解决方案,可以满足媒体资源拥有者收集、保存、查找、编辑、发布各种信息的要求,为媒体资源…...

18个8年以上服务器开发经验的面试题(2)

目录 1.问:如何设计一个系统来确保在可能出现网络分区和故障的分布式环境中的数据一致性?...

【SpringBoot】applicationContext.getBeansOfType(class)获取某一接口所有实现类,应用于策略模式

一、问题的提出 在实际工作中&#xff0c;我们经常会遇到一个接口及多个实现类的情况&#xff0c;并且在不同的条件下会使用不同的实现类。 二、应用场景 springboot 项目中通过 ApplicationContext.getBeansOfType(class) 获取某一接口的所有实现类&#xff0c;并通过枚举完…...

AJAX-入门

定义 概念&#xff1a;AJAX是浏览器与服务器进行数据通信的技术 使用 1.先使用axios库&#xff0c;与服务器进行数据通信 1&#xff09;基于XMLHttpRequest封装、代码简单、月下载量在14亿次 2&#xff09;Vue、React项目中都会用到axios 2.再学习XMLHttpRequest对象的使用…...

学术写作|第二篇论文写作记录|GPT4论文润色Prompt

本文目录 写作时间安排如何写出初稿?找谁修改?1. 找AI修改2. 找师姐、师兄、老师、同行/外行修改论文修改意见集锦(反复观看)最好用的GPT4指令禁止转载,未经允许的任何引用。 写作时间安排 第二篇工作的idea去年就想出来了,一直被其他事情干扰,错过了N个会议… 在寒假…...

力扣热门100题刷题笔记 - 10. 正则表达式匹配

力扣热门100题 - 10. 正则表达式匹配 题目链接&#xff1a;10. 正则表达式匹配 题目描述&#xff1a; 给你一个字符串 s 和一个字符规律 p&#xff0c;请你来实现一个支持 . 和 * 的正则表达式匹配。 . 匹配任意单个字符 * 匹配零个或多个前面的那一个元素 所谓匹配&#xff…...

4.0 HDFS 配置与使用

之前提到过的 Hadoop 三种模式&#xff1a;单机模式、伪集群模式和集群模式。 单机模式&#xff1a;Hadoop 仅作为库存在&#xff0c;可以在单计算机上执行 MapReduce 任务&#xff0c;仅用于开发者搭建学习和试验环境。 伪集群模式&#xff1a;此模式 Hadoop 将以守护进程的…...

【实训】网络规划与部署实训

一 实训目的及意义 本周实训主要是了解网络规划与部署&#xff0c;熟悉三大厂商华为、思科、锐捷交换机路由器以及相关协议的原理和配置&#xff0c;提高学生的动手能力和分析规划部署能力。 实训主要针对计算机网络系统集成的设计与实现的实际训练&#xff0c;着重锻炼学生熟练…...

相同的树[简单]

优质博文&#xff1a;IT-BLOG-CN 一、题目 给你两棵二叉树的根节点p和q&#xff0c;编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同&#xff0c;并且节点具有相同的值&#xff0c;则认为它们是相同的。 示例 1&#xff1a; 输入&#xff1a;p [1,2,3], q [1,…...

02-Web应用_架构构建_漏洞_HTTP数据包_代理服务器

Web应用_架构构建_漏洞_HTTP数据包_代理服务器 一、网站搭建前置知识1.1 域名1.2、子域名1.3、DNS二、web应用环境架构类三、web应用安全漏洞分类四、web请求返回过程数据包 五、演示案例5.1、架构-Web应用搭建-域名源码解析5.2、请求包-新闻回帖点赞-重放数据包5.3、请求包-移…...

使用flink-cdc-sqlserver出现错误,需要批量开启sqlserver表cdc模式,监听表变化

docker安装 docker run -e "ACCEPT_EULAY" -e "MSSQL_SA_PASSWORDZcyc123456" -p 1433:1433 --name sqlserver -d mcr.microsoft.com/mssql/server:2017-latest开启库cdc模式 选择你自己的数据库&#xff0c;执行以下sql语句 EXEC sys.sp_cdc_enable_db…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...

论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing

Muffin 论文 现有方法 CRADLE 和 LEMON&#xff0c;依赖模型推理阶段输出进行差分测试&#xff0c;但在训练阶段是不可行的&#xff0c;因为训练阶段直到最后才有固定输出&#xff0c;中间过程是不断变化的。API 库覆盖低&#xff0c;因为各个 API 都是在各种具体场景下使用。…...