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

蓝桥杯备战刷题-滑动窗口

在这里插入图片描述

今天给大家带来的是滑动窗口的类型题,都是十分经典的。
1,无重复字符的最长子串
在这里插入图片描述
看例三,我们顺便来说一下子串和子序列的含义
子串是从字符串里面抽出来的一部分,不可以有间隔,顺序也不能打乱。
子序列也是从字符串里面抽出来一部分,可以有间隔,顺序也不能打乱。
如图
在这里插入图片描述
可以看出来,如果是子序列问题,一般会比子串要更难一点。
不扯了,接下来进行这道题题目的讲解
第一种思路,也就是最简单的思路
那就是暴力求解。因为这道题本来就是只含有数字,字母符号,空格等组成。查看ASCII表,可以发现范围在128以内。当然我们也可以创建一个哈希表用来记录。然后分别从字符串的每个位置向后寻找,保留一个最大值即可。

class Solution {
public:
int lengthOfLongestSubstring(string s) {int ret = 0; // 记录结果int n = s.length();// 1. 枚举从不同位置开始的最⻓重复⼦串// 枚举起始位置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;// 如果没有重复,就更新 retret = max(ret, j - i + 1);}}// 2. 返回结果return ret;
}
};

运行后如图
在这里插入图片描述

还有一种方式就是滑动窗口,滑动窗口的思想就是两个同方向移动的指针,然后判断指针范围内我们所要寻找的,或者要统计的。
使用两个指针,left和right。
在这里插入图片描述
如果right和left中的元素没有重复值,那right就继续右移,设置一个max变量保存最长数,在窗口向后滑动时不断更新最大值。如果有重复的元素,就让left右移,直到窗口中没有重复元素为止,这样只需要遍历一遍就可以知道最长字符串的长度。
代码如下

class Solution {
public:
int lengthOfLongestSubstring(string s) {int hash[129] = { 0 };int left = 0, right = 0;int max = 0;while (right < s.size()){hash[s[right]]++;          while (hash[s[right]] != 1)//如果某个元素的数量大于2{hash[s[left]]--;//就右移left,直到该元素数量恢复为1left++;}if (right - left + 1 > max)//更新最大值{max = right - left + 1;}right++;}cout << max;return max;
}
};

在这里插入图片描述

暴力解法的时间复杂度明显为O(N2),而滑动窗口的时间复杂度为O(N)。
第二道题
最大连续1的个数
在这里插入图片描述
这道题很有意思的地方就是可以翻转,将0翻转为1。
这道题还是可以暴力解法,和第一道题很是类似,就是多了可以翻转这一步。但是我们可以这样想,一直遍历1,如果是0就翻转,上道题我们判断的是是否有重复的字符,这道题呢?我们不用想的那么复杂,还是设置两个变量left和right,同样遇到1就继续++right,如果遇到0,就判断窗口内0的个数,如果个数大于K就向右移动left,直到窗口内0的个数小于k即可,这样就只需要遍历一遍数组即可得出答案。
用动态图来演示一下
在这里插入图片描述

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int left=0,right=0;int ret=0;while(right<nums.size())//确定范围{if(nums[right]==0){k--;if(k<0)//k表示还可以翻转的0的个数{while(k!=0){if(nums[left]==0){k++;//如果left跳过了一个0,就++可翻转数left++;}else{left++;}}}}right++;ret=max(right-left,ret);//记录最大值}return ret;}
};

运行后如图
在这里插入图片描述
第三题
水果成篮
在这里插入图片描述题目很长,但是其实很容易理解,最主要的一点就是不能超过两种数,其实就是最长不重复子串的改版,这道题找的是最长只存在两种元素的最长子串的长度。
至于思路还有做题方法可以说和上边两道题很像。
用一个例子说明一下,这道题的暴力解法还是不停遍历,从数组的每一个位置开始,然后保留最大值。
在这里插入图片描述
代码如下

class Solution {
public:int totalFruit(vector<int>& fruits) {int hash[100001] = { 0 };int left = 0, right = 0;int kind = 0;int ret = 0;while (right < fruits.size()){if (hash[fruits[right]] == 0){kind++;}hash[fruits[right]]++;while(kind>2){hash[fruits[left]]--;if(hash[fruits[left]]==0){kind--;}left++;}ret = max(right-left+1, ret);right++;}return ret;
}
};

这里我们知道数据的范围,所以直接用一个数组代替哈希表。前三题的思路都十分相似。
第四题
找到字符串中所有的字母异位词

在这里插入图片描述
看一看例子,就知道异位词的含义了。
在这里插入图片描述
这道题的思路也很明显,和前边的题目又有一点不一样,我们首先要记录p字符串中的字母,然后从s字符串中利用滑动窗口查找,如果滑动窗口中的字符符合p字符串中所有字符个数。如果不符合,那就移动right和left。当然,p字符串的长度是一定的,所以滑动窗口的长度也是一定的。
我们可以用两个数组模拟哈希表,一个统计p字符串中的每个字母的个数,另一个是统计每一个字符出现的个数。
在滑动的时候,如果符合就++count,然后设置一个vector数组,将符合的位置(就是left的位置)放进数组中。然后将该数组返回。

class Solution
{
public:
vector<int> findAnagrams(string s, string p)
{vector<int> ret;int hash1[26] = { 0 }; // 统计字符串 p 中每个字符出现的个数for(auto ch : p) hash1[ch - 'a']++;int hash2[26] = { 0 }; // 统计窗⼝⾥⾯的每⼀个字符出现的个数int m = p.size();for(int left = 0, right = 0, count = 0; right < s.size(); right++){char in = s[right];// 进窗⼝ + 维护 countif(++hash2[in - 'a'] <= hash1[in - 'a']) count++;if(right - left + 1 > m) // 判断{char out = s[left++];// 出窗⼝ + 维护 countif(hash2[out - 'a']-- <= hash1[out - 'a']) count--;}// 更新结果if(count == m) ret.push_back(left);}return ret;
}
};

运行后如图
在这里插入图片描述

相关文章:

蓝桥杯备战刷题-滑动窗口

今天给大家带来的是滑动窗口的类型题&#xff0c;都是十分经典的。 1&#xff0c;无重复字符的最长子串 看例三&#xff0c;我们顺便来说一下子串和子序列的含义 子串是从字符串里面抽出来的一部分&#xff0c;不可以有间隔&#xff0c;顺序也不能打乱。 子序列也是从字符串里…...

LLM(十一)| Claude 3:Anthropic发布最新超越GPT-4大模型

2024年3月4日&#xff0c;Anthropic发布最新多模态大模型&#xff1a;Claude 3系列&#xff0c;共有Haiku、Sonnet和Opus三个版本。 Opus在研究生水平专家推理、基础数学、本科水平专家知识、代码等10个维度&#xff0c;超过OpenAI的GPT-4。 Haiku模型更注重效率&#xff0c;能…...

20-Java备忘录模式 ( Memento Pattern )

Java备忘录模式 摘要实现范例 备忘录模式&#xff08;Memento Pattern&#xff09;保存一个对象的某个状态&#xff0c;以便在适当的时候恢复对象 备忘录模式属于行为型模式 摘要 1. 意图 在不破坏封装性的前提下&#xff0c;捕获一个对象的内部状态&#xff0c;并在该对…...

整合生成型AI战略:从宏观思维到小步实践

“整合生成型AI战略&#xff1a;从宏观思维到小步实践” 在这篇文章中&#xff0c;我们探讨了将生成型AI和大型语言模型融入企业核心业务的战略开发方法。我们的方法基于敏捷开发原则&#xff0c;技术专家和数据科学家需要采纳商业思维&#xff0c;而执行官则需理解生成型AI和…...

个人博客系列-后端项目-用户验证(5)

介绍 创建系统管理app&#xff0c;用于管理系统的用户&#xff0c;角色&#xff0c;权限&#xff0c;登录等功能&#xff0c;项目中将使用django-rest_framework进行用户认证和权限解析。这里将完成用户认证 用户验证 rest_framework.authentication模块中的认证类&#xff…...

css3中nth-child属性作用及用法剖析

hello宝子们...我们是艾斯视觉擅长ui设计和前端开发10年经验!希望我的分享能帮助到您!如需帮助可以评论关注私信我们一起探讨!致敬感谢感恩! 标题&#xff1a;CSS3中nth-child属性作用及用法剖析 摘要&#xff1a;CSS3中的nth-child选择器允许我们根据元素位置来定位特定的元素…...

okHttp MediaType MIME格式详解

一、介绍 我们在做数据上传时&#xff0c;经常会用到Okhttp的开源库&#xff0c;okhttp开源库也遵循html提交的MIME数据格式。 所以我们经常会看到applicaiton/json这样的格式在传。 但是如果涉及到其他文件等就需要详细的数据格式&#xff0c;否则服务端无法解析 二、okHt…...

跨境电商三大趋势

跨境电商有着不断发展的三大趋势&#xff1a; 个性化定制&#xff1a;随着消费者需求的不断变化和个性化定制的潮流&#xff0c;跨境电商平台开始提供更多的定制化服务。消费者可以根据自己的需求选择产品的款式、材料和设计&#xff0c;从而获得更加个性化的产品体验。 无界销…...

【DevOps基础篇之k8s】如何通过Kubernetes CKA认证考试

【DevOps基础篇之k8s】如何通过Kubernetes CKA认证考试 目录 【DevOps基础篇之k8s】如何通过Kubernetes CKA认证考试核心概念资源监控生命周期管理Cluster维护安全认证问题排查其他推荐超级课程: Docker快速入门到精通Kubernetes入门到大师通关课这些是我在准备CK...

Mysql数据库-基本表操作

1.表操作 创建表&#xff1a;CREATE TABLE table_name ( field1 datatype, field2 datatype, field3 datatype ) character set 字符集 collate 校验规则 engine 存储引擎; field 表示列名 datatype 表示列的类型 character set 字符集&#xff0c;如果没有指定字符集&#xff…...

OceanBase社区版单节点安装搭建(Docker)

OceanBase社区版单节点安装搭建&#xff08;Docker&#xff09; 文章目录 OceanBase社区版单节点安装搭建&#xff08;Docker&#xff09;一、环境检查及Docker配置1.1 安装docker1.2 配置docker镜像源 二、OB镜像下载三、obd部署单节点数据库四、创建业务租户、数据库、表4.1 …...

Unity 关节:铰链、弹簧、固定、物理材质:摩檫力、 特效:拖尾、

组件-物理-关节&#xff1a;铰链&#xff08;类似门轴&#xff09; 自动动作、多少力可以将其断开、 弹簧可以连接另一个刚体&#xff08;拖动即可&#xff09; 固定一般是等待一个断裂力&#xff0c;造成四分五裂的效果。 物理材质 设置摩檫力&#xff0c;则可以创造冰面的…...

RIPEMD算法:多功能哈希算法的瑰宝

title: RIPEMD算法&#xff1a;多功能哈希算法的瑰宝 date: 2024/3/10 17:31:17 updated: 2024/3/10 17:31:17 tags: RIPEMD起源算法优势安全风险对比SHA优于MD5应用领域工作原理 一、RIPEMD算法的起源与历程 RIPEMD&#xff08;RACE Integrity Primitives Evaluation Messag…...

如何学习ChatGPT?从入门到精通(附资料下载)

2023 ChatGPT从入门到精通视频教程&#xff08;共30课&#xff09;.zip 学习ChatGPT需要涉及多个层面&#xff0c;包括理解其基本原理、掌握相关技术、以及进行实际的项目应用。以下是一些具体的学习步骤和建议&#xff1a; 理解ChatGPT的基本原理&#xff1a; 深入了解ChatGP…...

Linux安装MeterSphere并结合内网穿透实现公网远程访问本地服务

文章目录 前言1. 安装MeterSphere2. 本地访问MeterSphere3. 安装 cpolar内网穿透软件4. 配置MeterSphere公网访问地址5. 公网远程访问MeterSphere6. 固定MeterSphere公网地址 前言 MeterSphere 是一站式开源持续测试平台, 涵盖测试跟踪、接口测试、UI 测试和性能测试等功能&am…...

【 React 】state和props有什么区别?

1. state 一个组件的显示形态可以由数据状态和外部参数所决定&#xff0c;而数据状态就是state&#xff0c;一般在constructor中初始化 当需要修改里面的值的状态需要通过调用setState来改变&#xff0c;从而达到更新组件内部数据的作用&#xff0c;并且重新调用组件render方法…...

So you think you understand IP fragmentation?

文章目录 前言一、Why care?二、Prevention三、Well-understood?四、Introducing fragquiz五、A novel (?) algorithm六、Reader challenge七、traceroute八、ICMP参考资料 前言 本文来自&#xff1a;https://lwn.net/Articles/960913/ February 7, 2024This article was …...

为什么main方法在Java中代表主线程?

main 方法在 Java 等编程语言中确实代表着程序的入口点&#xff0c;也就是程序开始执行的地方。当我们启动一个 Java 应用程序时&#xff0c;JVM&#xff08;Java 虚拟机&#xff09;会首先查找 main 方法&#xff0c;并从那里开始执行程序。 关于为什么 main 方法代表主线程&a…...

腾讯 后端 一面(115min)

> 3.3投递 3.5测评 3.7约面 > 03.07 技术架构团队 一. 面试官介绍部门 二. 自我介绍 三. 拷打项目 1. 为什么、怎么用微服务架构改写 2. token无感刷新 3. ipfs用来干什么 为什么又用了minio 4. 怎么用redis做缓存的&#xff0c;缓…...

Python错题集-8:AttributeError(找不到对应的对象的属性)

1问题描述 AttributeError: AxesSubplot object has no attribute arc 2代码详情 import matplotlib.pyplot as plt# 创建一个新的图形和坐标轴 fig, ax plt.subplots()# 定义弧线的参数 center (0.5, 0.5) # 圆心坐标 (x, y) width 1.0 # 半径 height 0.5 # 半径 ang…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

给网站添加live2d看板娘

给网站添加live2d看板娘 参考文献&#xff1a; stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下&#xff0c;文章也主…...

CppCon 2015 学习:REFLECTION TECHNIQUES IN C++

关于 Reflection&#xff08;反射&#xff09; 这个概念&#xff0c;总结一下&#xff1a; Reflection&#xff08;反射&#xff09;是什么&#xff1f; 反射是对类型的自我检查能力&#xff08;Introspection&#xff09; 可以查看类的成员变量、成员函数等信息。反射允许枚…...

C++ 类基础:封装、继承、多态与多线程模板实现

前言 C 是一门强大的面向对象编程语言&#xff0c;而类&#xff08;Class&#xff09;作为其核心特性之一&#xff0c;是理解和使用 C 的关键。本文将深入探讨 C 类的基本特性&#xff0c;包括封装、继承和多态&#xff0c;同时讨论类中的权限控制&#xff0c;并展示如何使用类…...

C#中用于控制自定义特性(Attribute)

我们来详细解释一下 [AttributeUsage(AttributeTargets.Class, AllowMultiple false, Inherited false)] 这个 C# 属性。 在 C# 中&#xff0c;Attribute&#xff08;特性&#xff09;是一种用于向程序元素&#xff08;如类、方法、属性等&#xff09;添加元数据的机制。Attr…...

npm install 相关命令

npm install 相关命令 基本安装命令 # 安装 package.json 中列出的所有依赖 npm install npm i # 简写形式# 安装特定包 npm install <package-name># 安装特定版本 npm install <package-name><version>依赖类型选项 # 安装为生产依赖&#xff08;默认&…...