当前位置: 首页 > 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…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...

基于PHP的连锁酒店管理系统

有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发&#xff0c;数据库mysql&#xff0c;前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...

《信号与系统》第 6 章 信号与系统的时域和频域特性

目录 6.0 引言 6.1 傅里叶变换的模和相位表示 6.2 线性时不变系统频率响应的模和相位表示 6.2.1 线性与非线性相位 6.2.2 群时延 6.2.3 对数模和相位图 6.3 理想频率选择性滤波器的时域特性 6.4 非理想滤波器的时域和频域特性讨论 6.5 一阶与二阶连续时间系统 6.5.1 …...

数据分析六部曲?

引言 上一章我们说到了数据分析六部曲&#xff0c;何谓六部曲呢&#xff1f; 其实啊&#xff0c;数据分析没那么难&#xff0c;只要掌握了下面这六个步骤&#xff0c;也就是数据分析六部曲&#xff0c;就算你是个啥都不懂的小白&#xff0c;也能慢慢上手做数据分析啦。 第一…...

路由基础-路由表

本篇将会向读者介绍路由的基本概念。 前言 在一个典型的数据通信网络中&#xff0c;往往存在多个不同的IP网段&#xff0c;数据在不同的IP网段之间交互是需要借助三层设备的&#xff0c;这些设备具备路由能力&#xff0c;能够实现数据的跨网段转发。 路由是数据通信网络中最基…...

Qt Quick Controls模块功能及架构

Qt Quick Controls是Qt Quick的一个附加模块&#xff0c;提供了一套用于构建完整用户界面的UI控件。在Qt 6.0中&#xff0c;这个模块经历了重大重构和改进。 一、主要功能和特点 1. 架构重构 完全重写了底层架构&#xff0c;与Qt Quick更紧密集成 移除了对Qt Widgets的依赖&…...

生信服务器 | 做生信为什么推荐使用Linux服务器?

原文链接&#xff1a;生信服务器 | 做生信为什么推荐使用Linux服务器&#xff1f; 一、 做生信为什么推荐使用服务器&#xff1f; 大家好&#xff0c;我是小杜。在做生信分析的同学&#xff0c;或是将接触学习生信分析的同学&#xff0c;<font style"color:rgb(53, 1…...