经典滑动窗口试题(二)

在这里插入图片描述


📘北尘_:个人主页

🌎个人专栏:《Linux操作系统》《经典算法试题 》《C++》 《数据结构与算法》

☀️走在路上,不忘来时的初心

文章目录

  • 一、水果成篮
    • 1、题目讲解
    • 2、讲解算法思路
    • 3、代码实现
  • 二、找到字符串中所有字母异位词
    • 1、题目讲解
    • 2、讲解算法思路
    • 3、代码实现
  • 三、串联所有单词的子串
    • 1、题目讲解
    • 2、讲解算法思路
    • 3、代码实现
  • 四、最小覆盖子串
    • 1、题目讲解
    • 2、讲解算法思路
    • 3、代码实现


一、水果成篮

1、题目讲解

在这里插入图片描述
在这里插入图片描述

2、讲解算法思路

在这里插入图片描述

3、代码实现

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

二、找到字符串中所有字母异位词

1、题目讲解

在这里插入图片描述

2、讲解算法思路

在这里插入图片描述

3、代码实现

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;int hash1[256]={0},len=p.size();for(char ch:p) hash1[ch]++;int hash2[256]={0};for(int left=0,right=0,count=0;right<s.size();right++){char in=s[right];hash2[in]++;if(hash2[in]<=hash1[in]) count++;if(right-left+1>len){char out=s[left];if(hash2[out]<=hash1[out]) count--;hash2[out]--;left++;}if(count==len){ret.push_back(left);}}return ret;      }
};

三、串联所有单词的子串

1、题目讲解

在这里插入图片描述
在这里插入图片描述

2、讲解算法思路

在这里插入图片描述

3、代码实现

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ret;unordered_map<string,int> hash1;for(auto ch:words){hash1[ch]++;}int len=words[0].size(),m=words.size();for(int i=0;i<len;i++){unordered_map<string,int> hash2;for(int left=i,right=i,count=0;right+len<=s.size();right+=len){string in=s.substr(right,len);hash2[in]++;if(hash1.count(in) && hash2[in]<=hash1[in]) count++;if(right-left+1>len*m){string out=s.substr(left,len);if(hash1.count(out) && hash2[out]<=hash1[out]) count--;hash2[out]--;left+=len;}if(count==m) ret.push_back(left);}}return ret;}
};

四、最小覆盖子串

1、题目讲解

在这里插入图片描述

2、讲解算法思路

在这里插入图片描述

3、代码实现

代码一

class Solution {
public:string minWindow(string s, string t) {int hash1[256]={0};int kinds=0;for(auto ch:t){if(hash1[ch]==0) kinds++;hash1[ch]++;}int hash2[256]={0};int minlen=INT_MAX,begin=-1;for(int left=0,right=0,count=0;right<s.size();right++){char in=s[right];hash2[in]++;if(hash2[in]==hash1[in])  count++;while(count==kinds){if(right-left+1<minlen){minlen=right-left+1;begin=left;}char out=s[left++];if(hash2[out]--==hash1[out])  count--;    } }if(begin==-1) return "";else return s.substr(begin,minlen);}
};

代码二 不使用kinds来计算种类

class Solution {
public:string minWindow(string s, string t) {int hash1[256]={0},n=t.size();for(char ch:t){hash1[ch]++;}int begin=-1,len=INT_MAX;int hash2[256]={0};for(int left=0,right=0,count=0;right<s.size();right++){char in=s[right];hash2[in]++;if(hash2[in]<=hash1[in]) count++;while(count==n){if(right-left+1<len){begin=left;len=right-left+1;}char out=s[left];if(hash2[out]<=hash1[out]) count--;hash2[out]--;left++;}}if(begin==-1) return "";else return  s.substr(begin,len);}};

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

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

相关文章

合并区间[中等]

一、题目 以数组intervals表示若干个区间的集合&#xff0c;其中单个区间为intervals[i] [starti, endi]。请你合并所有重叠的区间&#xff0c;并返回一个不重叠的区间数组&#xff0c;该数组需恰好覆盖输入中的所有区间。 示例 1&#xff1a; 输入&#xff1a;intervals […

初探HarmonyOS路由跳转

最近的鸿蒙新闻也是很大声势&#xff0c;鸿蒙的纯血版一出&#xff0c;各大互联网大厂都坐不住了&#xff0c;纷纷加入其中。这意味鸿蒙将来会取代大部分Android用户&#xff0c;这也是程序员的一篇大好前程。如今的Android开发行业已经夕阳西下了。 网上有关HarmonyOS的资料几…

SVD recommendation systems

SVD recommendation systems 为什么在推荐系统中使用SVD 一个好的推荐系统一定有小的RMSE R M S E 1 m ∑ i 1 m ( Y i − f ( x i ) 2 RMSE \sqrt{\frac{1}{m} \sum_{i1}^m(Y_i-f(x_i)^2} RMSEm1​i1∑m​(Yi​−f(xi​)2 ​ 希望模型能够在已知的ratings上有好的结果的…

springboot整合redis+自定义注解+反射+aop实现分布式锁

1.定义注解 import java.lang.annotation.*; import java.util.concurrent.TimeUnit;/** Author: best_liu* Description:* Date: 16:13 2023/9/4* Param * return **/ Retention(RetentionPolicy.RUNTIME) Target({ElementType.METHOD}) Documented public interface RedisLo…

Ubuntu系统Springboot项目Nginx安装(编译安装方式)

1.下载 nginx官网下载 Index of /download/ 2.解压 这里我下载的1.25.3版本&#xff0c;系统是ubuntu 解压 tar -zxvf nginx-1.25.3.tar.gz 3.编译安装 安装前需要执行安装一些系统依赖 3.1安装PCRE库 ubuntu&#xff1a;执行以下命令 sudo apt-get install libpcre…

MOSFET安全工作区域SOA

Safe Operating Area&#xff08;SOA&#xff09;即安全工作区&#xff1a;描述了当MOSFET工作在饱和区时可以处理的最大功率。超出安全工作区&#xff0c;则可能导致元件损坏。 SOA分为五个单独的界限&#xff0c;分别是RDS(on)限制 On Resistance&#xff08;RDS(on)&#…

Kafka系列 - Kafka一篇入门

Kafka是一个分布式流式处理平台。很多分布式处理系统&#xff0c;例如Spark&#xff0c;Flink等都支持与Kafka集成。 Kafka使用场景 消息系统&#xff1a;Kafka实现了消息顺序性保证和回溯消费。存储系统&#xff1a;Kafka把消息持久化到磁盘&#xff0c;相比于其他基于内存的…

⑨【Stream】Redis流是什么?怎么用?: Stream [使用手册]

个人简介&#xff1a;Java领域新星创作者&#xff1b;阿里云技术博主、星级博主、专家博主&#xff1b;正在Java学习的路上摸爬滚打&#xff0c;记录学习的过程~ 个人主页&#xff1a;.29.的博客 学习社区&#xff1a;进去逛一逛~ ⑨Redis Stream基本操作命令汇总 一、Redis流 …

苹果mac屏幕投屏镜像工具AirServer2024

airserver 是什么软件&#xff1f;AirServer 是一款 Airplay Mac屏幕镜像应用&#xff0c;AirServer可以通过 mac 实时接收iPhone、iPad以及Android设备的实时屏幕画面。AirServer 可以将一个简单的大屏幕或投影仪变成一个通用的屏幕镜像接收器。在您的大屏幕上启用 AirServer …

八股文面试day6

什么是代理&#xff1f;为什么要用动态代理&#xff1f; 代理模式大概意思是&#xff1a;为其他对象提供一个代理项或者是占位符&#xff0c;以控制对这个对象的访问 代理模式核心思想&#xff1a;创建一个代理对象&#xff0c;在客户端和目标对象之间的一个中介&#xff0c;…

MySQL与Redis如何保证数据的一致性

文章目录 MySQL与Redis如何保证数据的一致性&#xff1f;不好的方案1. 先写 MySQL&#xff0c;再写 Redis2. 先写 Redis&#xff0c;再写 MySQL3. 先删除 Redis&#xff0c;再写 MySQL 好的方案4. 先删除 Redis&#xff0c;再写 MySQL&#xff0c;再删除 Redis5. 先写 MySQL&am…

实现极坐标图表QPolarChart的角度轴范围是[0,360]时,0度在水平右侧

目录 参考角度轴范围是[0,360]时&#xff0c;0度在水平右侧.h.cpp 参考 Qt数据可视化(QPolarChart雷达图) 默认QPolarChart的范围是[0,360]时&#xff0c;0度在垂直上方 如官方例子QValueAxis角度轴范围是[-100,100] 角度轴范围是[0,360]时&#xff0c;0度在水平右侧 原理&am…

如何在GO中写出准确的基准测试

一般来说&#xff0c;我们不应该对性能进行猜测。在编写优化时&#xff0c;会有许多因素可能起作用&#xff0c;即使我们对结果有很强的看法&#xff0c;测试它们很少是一个坏主意。然而&#xff0c;编写基准测试并不简单。很容易编写不准确的基准测试&#xff0c;并且基于这些…

C语言进阶之笔试题详解(1)

引言&#xff1a; 对指针知识进行简单的回顾&#xff0c;然后再完成笔试题。 ✨ 猪巴戒&#xff1a;个人主页✨ 所属专栏&#xff1a;《C语言进阶》 &#x1f388;跟着猪巴戒&#xff0c;一起学习C语言&#x1f388; 目录 引言&#xff1a; 知识简单回顾 指针是什么 指针变…

vue项目中使用jsonp跨域请求百度联想接口

一. 内容简介 vue项目中使用jsonp跨域请求百度联想接口 二. 软件环境 2.1 Visual Studio Code 1.75.0 2.2 chrome浏览器 2.3 node v18.14.0 三.主要流程 3.1 代码 核心代码 // 这个是请求函数doLeno() {// 挂载回调函数&#xff0c;不挂载&#xff0c;会报不存在window…

React入门使用 (官方文档向 Part1)

文章目录 React组件:万物皆组件 JSX: 将标签引入 JavaScriptJSX 规则1. 只能返回一个根元素2. 标签必须闭合3. 使用驼峰式命名法给 ~~所有~~ 大部分属性命名&#xff01;高级提示&#xff1a;使用 JSX 转化器 在 JSX 中通过大括号使用 JavaScript使用引号传递字符串使用大括号&…

性能优化中使用Profiler进行内存泄露的排查及解决方式

文章目录 一、前言二、内存泄露的排查方式三、参考链接 一、前言 对于常规意义上的线程使用要及时关闭&#xff0c;数据库用完要及时关闭&#xff0c;数据用完要及时清空等等这里不再赘述&#xff0c;但是在开发中总会有不熟悉的api&#xff0c;开发进度过快&#xff0c;开发人…

【工具】Zotero|使用Zotero向Word中插入引用文献(2023年)

版本&#xff1a;Word 2021&#xff0c;Zotero 6.0.30 前言&#xff1a;两年前我找网上插入文献的方式&#xff0c;网上的博客提示让我去官网下个插件然后才能装&#xff0c;非常麻烦&#xff0c;导致我对Zotero都产生了阴影。最近误打误撞发现Zotero自带了Word插件&#xff0c…

随时随地,打开浏览器即可体验的在线PS编辑器

即时设计 即时设计是国产的专业级 UI 设计工具&#xff0c;不限平台不限系统&#xff0c;在浏览器打开即用&#xff0c;能够具备 Photoshop 的设计功能&#xff0c;钢笔、矢量编辑、矩形工具、布尔运算等设计工具一应俱全&#xff0c;是能够在线使用的 Photoshop 免费永久工具…

DjiTello + YoloV5的无人机的抽烟检测

一、效果展示 注&#xff1a;此项目纯作者自己原创&#xff0c;创作不易&#xff0c;不经同意不给予搬运权限&#xff0c;转发前请联系我&#xff0c;源码较大需要者评论获取&#xff0c;谢谢配合&#xff01; 1、未启动飞行模型无人机的目标检测。 DjiTello YOLOV5抽烟检测 …