算法——滑动窗口(day8)

30.串联所有单词的子串 

30. 串联所有单词的子串 - 力扣(LeetCode) 

必看!!!本题是我们上次写的438.异位词的进阶版,可参考本篇文章:算法——滑动窗口(day7)-CSDN博客来帮助理解。

题目解析:

这里我就默认大家都已经看过我们上一篇题解的思路了~ 

本道题我们可以通过题意:words数组内所有字符串长度相同的特性对问题进行转化~

例如,我们可以把words数组内的其中一个字符串想象成字符a,另一个字符串想象成字符b。然后也对字符串s中进行成队字符串转化(这里是长度为3的字符串转化为1字符)。双方转化完之后我们就可以发现这跟之前的求异位词那道题已经没有什么区别了~

算法解析:

这里我们再来补充一下细节问题:比如right遍历移动的时候应该是跨words数组中的字符串长度进行移动,因为我们把一段子串想象成一个字符,所以哈希表录入的时候都是已子串录入的,那么我们就不能单纯让right一个字符一个字符遍历,而是一段子串一段子串遍历。left也同样如果。不过在遍历完毕后还需要注意,还有绿色线,黄色线这种划分情况,至于黑色线只不过比蓝色线少了一个字符串,所以没必要划分了~

滑动流程图:

其实只要能把问题转化为我们上一题的思路剩下的就简单了,基本思路是一样的,后面再考虑一下两个哈希表的字符串录入,双指针的移动距离,考虑到所有情况的发生就好了。

代码:

 

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {//记录字符串数组words的数据unordered_map<string, int>hash2;for (auto& ch : words){hash2[ch]++;}//字符串数组中每个字符串的长度int m = words[0].size();//字符串数组中数组的个数int n = words.size();//记录结果vector<int> ret;int k = 0;//多层循环做到不遗漏while (k < m){//在每一层新的循环中都有特定记录字符串s的哈希表unordered_map<string, int>hash1;for (int left = k, right = k, count = 0; right + m <= s.size(); right += m){//获取特定长度的字符串录入hash1中string a = s.substr(right, m);//正常情况下,窗口长度短时扩充窗口//先录入所选子串数据hash1[a]++;//判定录入的数据是否为可以抵消hash2中对应的有效字符串if (hash1[a] <= hash2[a]){count++;}//扩充完发现仍过短就跳到下一循环继续扩充//当窗口长度过长时候,开始缩小窗口if (right - left + 1 > m * n){//获取特定长度的字符串string b = s.substr(left, m);//删减对应字符串个数hash1[b]--;//如果删完后发现缺少了抵消hash2中对应子串可能性if (hash1[b] < hash2[b]){//有效字符串减一count--;}left += m;}//当有效字符串个数完全可以抵消时if (count == n){//录入结果ret.push_back(left);}}//开始下一轮的循环k++;}return ret;}
};

 

76.最小覆盖子串

76. 最小覆盖子串 - 力扣(LeetCode)

题目解析:

这道题依然可以利用两个哈希表进行辅助,不过与其他题不同的是本题只要划分好的s内至少有t对应的字符就行了, 多了也没事。

对暴力进行分析,如果已经找到满足条件的子串那么left在进入下一轮的遍历时right需要复位吗?————不需要假设【left,right】为目标子串的范围,left继续前进只有2种可能

  • 要么缩小窗口后仍满足条件,这时候只需要让right呆在原地,然后记录满足条件的新子串范围【left,right】即可。
  • 要么不符合所需条件,就让right继续前进直到找到所需字符。

所以不管怎么样right都是不用复位的,而这也引出了我们的滑动窗口~

算法解析:

滑动窗口流程图:

之所以找字符种类而不是个数是因为本题只要满足t中所含字符即可,个数超出也无大碍。那我们就以hash2中的个数为基准,假设hash2中a有2个,那么只有hash1中a的个数也达2个跟hash2相等那才能算是一个有效种类。在未达到数量标准之前都不算为有效种类~

基本思路为:

  • 进窗口:进之前先录入数据到hash1中,然后判断两表中该字符个数是否相等(若相等,count++)
  • 判断,这里是以判断count与m是否相等,若相等则说明找到子串,更新结果,然后不断出窗口直到count不等于m为止(在这个过程可以找出更多子串)
  • 出窗口:出之前先判断两表中该字符个数是否相等(若相等,则说明删减后无法匹配,则count--),然后删减数据

代码:

class Solution {
public:string minWindow(string s, string t) {//记录字符串s的数据unordered_map<int, int>hash1;//记录字符串t的数据unordered_map<int, int>hash2;for (auto ch : t){hash2[ch - 'a']++;}int count = 0;int len = INT_MAX;int begin = -1;//计算t中字符的种类int m = hash2.size();for (int left = 0, right = 0; right < s.size(); right++){//扩充窗口//录入数据hash1[s[right] - 'a']++;//录入完如果两表字符数量相等,则说明count可+1if (hash1[s[right] - 'a'] == hash2[s[right] - 'a']){count++;}//在扩充窗口的过程中如果已经找到可匹配的子串while (count == m){//记录所找子串长度以及起始位置if (right - left + 1 < len){len = right - left + 1;begin = left;}//判断在缩小窗口之前两表中字符个数是否相等if (hash1[s[left] - 'a'] == hash2[s[left] - 'a']){//若相等则说明该字符出窗口后无法与hash2对应字符匹配count--;}//移除该字符hash1[s[left] - 'a']--;//缩小窗口left++;}}//未找到目的子串if (begin == -1){return "";}else{return s.substr(begin, len);}}
};

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

MySQL数据库安装使用

我们都知道数据库又分为关系型数据库和非关系型数据库&#xff1b; 关系型数据库指采用了关系模型来组织数据的数据库&#xff0c;指的就是二维表格模型。可以先初步理解为Excel表格。非关系型数据库又被称为NoSQL&#xff0c;对NoSQL 最普遍的定义是“非关联型的”&#xff0…

Android平台RTSP|RTMP直播播放器技术接入说明

技术背景 大牛直播SDK自2015年发布RTSP、RTMP直播播放模块&#xff0c;迭代从未停止&#xff0c;SmartPlayer功能强大、性能强劲、高稳定、超低延迟、超低资源占用。无需赘述&#xff0c;全自研内核&#xff0c;行业内一致认可的跨平台RTSP、RTMP直播播放器。本文以Android平台…

免费【2024】springboot 编程语言在线学习平台的设计与实现

博主介绍&#xff1a;✌CSDN新星计划导师、Java领域优质创作者、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流✌ 技术范围&#xff1a;SpringBoot、Vue、SSM、HTML、Jsp、PHP、Nodejs、Python、爬虫、数据可视化…

数据库处理表

首先先创建库&#xff0c;然后创建需要的这三个表 用dese表名查看 然后题目要求对表进行修改 用alter table这个语法来对表进行修改 modify为修改字段 需要修改的字段的属性类型改变为的属性 最后用descStudent查看 第二题需要创建索引 创建索引createindex索引名称 cre…

C#开发的全屏图片切换效果应用 - 开源研究系列文章 - 个人小作品

这天无聊&#xff0c;想到上次开发的图片显示软件《 PhotoNet看图软件 》&#xff0c;然后想到开发一个全屏图片切换效果的应用&#xff0c;类似于屏幕保护程序&#xff0c;于是就写了此博文。这个应用比较简单&#xff0c;主要是全屏切换换图片效果的问题。 1、 项目目录&…

JS基础知识学习笔记全

JS基础知识学习笔记全 一、引入方式 1、内部脚本 &#xff08;一般定义在body下面会改善执行速度&#xff09; <body></body><!-- 内部脚本 --><script>/* 打开页面警告框显示的内容 */alert(helloJS);</script>2、外部脚本 外部专门新建一…

在Ubuntu上安装移远EC200M驱动

最近公司在做降本相关工作&#xff0c;考虑移远 EC20 4G模组成本较高&#xff0c;希望通过更低成本替换硬件&#xff0c;最后找到EC200M芯片&#xff0c;虽然EC200M速率(最大下行10M/s 最大上行5M/s)上低于EC20&#xff08;最大下行150M/s 最大上行50M/s&#xff09;,基本上可以…

(leetcode学习)19. 删除链表的倒数第 N 个结点

给你一个链表&#xff0c;删除链表的倒数第 n 个结点&#xff0c;并且返回链表的头结点。 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,4,5], n 2 输出&#xff1a;[1,2,3,5]示例 2&#xff1a; 输入&#xff1a;head [1], n 1 输出&#xff1a;[]示例 3&#xff1a; …

ARM功耗管理之autosleep和睡眠锁实验

安全之安全(security)博客目录导读 ARM功耗管理精讲与实战汇总参见&#xff1a;Arm功耗管理精讲与实战 思考&#xff1a;睡眠唤醒实验&#xff1f;压力测试&#xff1f;Suspend-to-Idle/RAM/Disk演示&#xff1f; 1、实验环境准备 2、软件代码准备 3、唤醒源 4、Suspend-…

CSS学习笔记[Web开发]

CSS学习 本文为学习笔记&#xff0c;参考菜鸟和w3c 文章目录 CSS 简介CSS 插入外部 CSS内部 CSS行内 CSS多个样式表层叠顺序 CSS 语法例子解释 CSS 选择器CSS 元素选择器CSS id 选择器实例CSS 类选择器实例CSS 通用选择器实例CSS 分组选择器CSS 后代选择器CSS 子元素选择器CSS …

如何让网站实现https访问

要让网站实现HTTPS访问&#xff0c;主要需要完成以下几个步骤。这些步骤确保了网站与用户之间的数据传输安全&#xff0c;并提升了用户对网站的信任度。 1. 确定证书类型 首先&#xff0c;根据网站的需求和预算&#xff0c;选择合适的SSL证书类型。常见的SSL证书类型包括&…

GPT(LLM)不是AGI的全部

人工智能领域正在如火如荼地发展&#xff0c;随着诸如ChatGPT、Claude、Gemini、Sora和Grok等平台的不断涌现&#xff0c;AI技术和模型持续演进&#xff0c;引发人们对通用人工智能&#xff08;AGI&#xff09;的浓厚兴趣。 在这一备受关注的话题中&#xff0c;人们常常将GPT和…

Android WebViewClient 的 `shouldOverrideUrlLoading` 方法

简介 在Android开发中&#xff0c;WebView是一个强大的工具&#xff0c;可以在你的应用中显示网页内容。了解 WebViewClient 中的 shouldOverrideUrlLoading 方法是至关重要的&#xff0c;因为这个方法允许你控制 URL 在 WebView 中的处理方式。 在本文中&#xff0c;我们将详…

gitlab以及分支管理

一、分支概念 每次提交&#xff0c;Git都把它们串成一条时间线&#xff0c;这条时间线就是一个分支。截止 到目前&#xff0c;只有一条时间线&#xff0c;在Git里&#xff0c;这个分支叫主分支&#xff0c;即master分支。 HEAD 严格来说不是指向提交&#xff0c;而是指向maste…

【微信小程序实战教程】之微信小程序原生开发详解

微信小程序原生开发详解 微信小程序的更新迭代非常频繁&#xff0c;几乎每个月都会有新版本发布&#xff0c;这就会让初学者感觉到学习的压力和难度。其实&#xff0c;我们小程序的每次版本迭代都是在现有小程序架构基础之上进行更新的&#xff0c;如果想要学好小程序开发技术&…

redis的使用场景和持久化方式

redis的使用场景 热点数据的缓存。热点&#xff1a;频繁读取的数据。限时任务的操作&#xff1a;短信验证码。完成session共享的问题完成分布式锁。 redis的持久化方式 什么是持久化&#xff1a;把内存中的数据存储到磁盘的过程&#xff0c;同时也可以把磁盘中的数据加载到内存…

iPhone 在 App Store 中推出的 PC 模拟器 UTM SE

PC 模拟器是什么&#xff1f;PC 模拟器是一种软件工具&#xff0c;它模拟不同硬件或操作系统环境&#xff0c;使得用户可以在一台 PC 上运行其他平台的应用程序或操作系统。通过 PC 模拟器&#xff0c;用户可以在 Windows 电脑上体验 Android 应用、在 Mac 电脑上运行 Windows …

如何优化 Selenium 和 BeautifulSoup 的集成以提高数据抓取的效率?

摘要 在互联网时代&#xff0c;数据的价值日益凸显。对于电商网站如京东&#xff0c;其商品信息、用户评价等数据对于市场分析、产品定位等具有重要意义。然而&#xff0c;由于这些网站通常使用 JavaScript 动态生成内容&#xff0c;传统的爬虫技术难以直接获取到完整数据。本…

新智慧:企元数智呈现全新新零售合规分销系统免费送

新智慧&#xff01;企元数智近期发布了令人振奋的消息&#xff1a;他们推出了全新的新零售合规分销系统&#xff0c;并且免费向企业赠送&#xff01;这一举措旨在帮助更多企业轻松实现数字化转型&#xff0c;提高管理效率&#xff0c;实现持续增长。 企元数智的新零售合规分销系…

HTML学习笔记[Web开发]

HTML学习 本文为学习笔记&#xff0c;参考w3c&#xff0c;菜鸟&#xff0c;Mozilla&#xff0c;尚硅谷等文章编写。 文章目录 HTML 简介HTML文档的后缀名HTML版本 HTML 编辑器HTML 标签 (HTML Tag)HTML 提示&#xff1a;使用小写标签HTML 标签简写及全称 HTML 元素HTML元素组成…