滑动窗口(一)
文章目录
- 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. 长度最小的子数组题目解法一(暴力求解)(超时)解法二(滑动窗口) Leetcode3. 无重复字符的最长子串题目解法一(暴力求解)解法二(滑动窗口) Leetcode1004. 最大连…...
寒假 day1
1、请简述栈区和堆区的区别? 2、有一个整形数组:int arr[](数组的值由外部输入决定),一个整型变量: x(也 由外部输入决定)。要求: 1)删除数组中与x的值相等的元素 2)不得创建新的数组 3)最多只允许使用单层循环 4)无需考虑超出新数组长度后面的元素,所以…...
DATAX改造支持geometry类型数据同步
数据库使用postgresql安装了postgis插件存储了geometry空间数据,想使用datax做数据同步,但datax本身不支持geometry类型数据,如何改造呢? 1.首先下载已改造支持geometry类型的datax引擎,下载地址 https://download.c…...
Vue中keep-alive的作用、原理及应用场景
在进行Vue开发的过程中,我们经常会遇到需要进行组件缓存的场景,这时候Vue提供的keep-alive组件就派上了用场。keep-alive组件是Vue内置的一个抽象组件,它可以将其包裹的组件进行缓存,提高组件的性能,同时也可以节省服务…...
SpringBoot集成Redisson实现限流(二)
1. 简介 Springboot集成Redisson默认的限流器为令牌桶型限流器,底层是通过lua脚本去实现的。 通过lua脚本我们可以去实现一个滑动窗口限流器,利用ZSET格式数据就可以轻松实现。 springboot集成Redisson就不做讲解,可以参考:sprin…...
【2024美赛E题】985博士解题思路分析(持续更新中)!
【2024美赛E题】985博士解题思路分析! 加群可以享受定制等更多服务,或者搜索B站:数模洛凌寺 联络组织企鹅:936670395 以下是E题老师的解题思路(企鹅内还会随时更新文档): 2024美赛E题思路详解…...
北朝隋唐文物展亮相广西,文物预防性保护网关保驾护航
一、霸府名都——太原博物馆收藏北朝隋朝文物展 2月1日,广西民族博物馆与太原博物馆携手,盛大开启“霸府名都——太原博物馆北朝隋文物展”。此次新春展览精选了北朝隋唐时期150多件晋阳文物珍品。依据“巍巍雄镇”“惊世古冢”“锦绣名都”三个单元&am…...
回归预测 | Matlab实现WOA-CNN-LSTM-Attention鲸鱼算法优化卷积长短期记忆网络注意力多变量回归预测(SE注意力机制)
回归预测 | Matlab实现WOA-CNN-LSTM-Attention鲸鱼算法优化卷积长短期记忆网络注意力多变量回归预测(SE注意力机制) 目录 回归预测 | Matlab实现WOA-CNN-LSTM-Attention鲸鱼算法优化卷积长短期记忆网络注意力多变量回归预测(SE注意力机制&…...
ubuntu离线安装k8s
目录 一、前期准备 二、安装前配置 三、安装docker 四、安装cri-dockerd 五、部署k8s master节点 六、整合kubectl与cri-dockerd 七、网络等插件安装 八、常见问题及解决方法 一、前期准备 ①ubuntu系统 本地已安装ubuntu系统,lsb_release -a命令查看版本信…...
学成在线:媒体资源管理系统(MAM)
媒体资源管理系统(MAM) 媒体资源管理系统(Media Asset Management)是建立在多媒体、网络、数据库和数字存储等先进技术基础上的一个对各种媒体及内容进行数字化存储、管理以及应用的总体解决方案,可以满足媒体资源拥有者收集、保存、查找、编辑、发布各种信息的要求,为媒体资源…...
18个8年以上服务器开发经验的面试题(2)
目录 1.问:如何设计一个系统来确保在可能出现网络分区和故障的分布式环境中的数据一致性?...
【SpringBoot】applicationContext.getBeansOfType(class)获取某一接口所有实现类,应用于策略模式
一、问题的提出 在实际工作中,我们经常会遇到一个接口及多个实现类的情况,并且在不同的条件下会使用不同的实现类。 二、应用场景 springboot 项目中通过 ApplicationContext.getBeansOfType(class) 获取某一接口的所有实现类,并通过枚举完…...
AJAX-入门
定义 概念:AJAX是浏览器与服务器进行数据通信的技术 使用 1.先使用axios库,与服务器进行数据通信 1)基于XMLHttpRequest封装、代码简单、月下载量在14亿次 2)Vue、React项目中都会用到axios 2.再学习XMLHttpRequest对象的使用…...
学术写作|第二篇论文写作记录|GPT4论文润色Prompt
本文目录 写作时间安排如何写出初稿?找谁修改?1. 找AI修改2. 找师姐、师兄、老师、同行/外行修改论文修改意见集锦(反复观看)最好用的GPT4指令禁止转载,未经允许的任何引用。 写作时间安排 第二篇工作的idea去年就想出来了,一直被其他事情干扰,错过了N个会议… 在寒假…...
力扣热门100题刷题笔记 - 10. 正则表达式匹配
力扣热门100题 - 10. 正则表达式匹配 题目链接:10. 正则表达式匹配 题目描述: 给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 . 和 * 的正则表达式匹配。 . 匹配任意单个字符 * 匹配零个或多个前面的那一个元素 所谓匹配ÿ…...
4.0 HDFS 配置与使用
之前提到过的 Hadoop 三种模式:单机模式、伪集群模式和集群模式。 单机模式:Hadoop 仅作为库存在,可以在单计算机上执行 MapReduce 任务,仅用于开发者搭建学习和试验环境。 伪集群模式:此模式 Hadoop 将以守护进程的…...
【实训】网络规划与部署实训
一 实训目的及意义 本周实训主要是了解网络规划与部署,熟悉三大厂商华为、思科、锐捷交换机路由器以及相关协议的原理和配置,提高学生的动手能力和分析规划部署能力。 实训主要针对计算机网络系统集成的设计与实现的实际训练,着重锻炼学生熟练…...
相同的树[简单]
优质博文:IT-BLOG-CN 一、题目 给你两棵二叉树的根节点p和q,编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。 示例 1: 输入: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模式 选择你自己的数据库,执行以下sql语句 EXEC sys.sp_cdc_enable_db…...
大数据学习栈记——Neo4j的安装与使用
本文介绍图数据库Neofj的安装与使用,操作系统:Ubuntu24.04,Neofj版本:2025.04.0。 Apt安装 Neofj可以进行官网安装:Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
Frozen-Flask :将 Flask 应用“冻结”为静态文件
Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是:将一个 Flask Web 应用生成成纯静态 HTML 文件,从而可以部署到静态网站托管服务上,如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...
dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...
R语言速释制剂QBD解决方案之三
本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...
在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)
考察一般的三次多项式,以r为参数: p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]; 此多项式的根为: 尽管看起来这个多项式是特殊的,其实一般的三次多项式都是可以通过线性变换化为这个形式…...
RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill
视觉语言模型(Vision-Language Models, VLMs),为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展,机器人仍难以胜任复杂的长时程任务(如家具装配),主要受限于人…...
android13 app的触摸问题定位分析流程
一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...
嵌入式常见 CPU 架构
架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集,单周期执行;低功耗、CIP 独立外设;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel(原始…...
ui框架-文件列表展示
ui框架-文件列表展示 介绍 UI框架的文件列表展示组件,可以展示文件夹,支持列表展示和图标展示模式。组件提供了丰富的功能和可配置选项,适用于文件管理、文件上传等场景。 功能特性 支持列表模式和网格模式的切换展示支持文件和文件夹的层…...
