【滑动窗口】Leetcode 串联所有单词的子串
题目解析
30. 串联所有单词的子串

本题的意思就是在目标串s中寻找能够找到的words字符串的全排列,返回起始位置
算法讲解

我们可以将这道题转化为寻找目标串的words字母的异位词,按照上一次讲解的【滑动窗口】Leetcode 找到字符串中所有字母异位词我们还是使用同样的做法,哈希表 + 滑动窗口
但是这道题有以下注意事项:滑动窗口的移动次数
每一次left和right一开始都指向同一个位置,当滑动窗口移动到字符串s结束的时候,需要将left+1,开始继续滑动下一次的循环
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {unordered_map<string, int> Hash_words;vector<int>ret;int left = 0;int right = 0;//将words放进Hashfor (auto str : words){Hash_words[str]++;}int count = 0;int cnt = 0;//窗口一次移动完成之后再从一开始的下一个位置反复while (cnt < words[0].size()){//这是一次完整的移动unordered_map<string, int> hash2; // 维护窗⼝内单词的频次for (int left = cnt, right = cnt, count = 0; right + words[0].size() <= s.size(); right += words[0].size()){// 进窗⼝ + 维护 countstring temp = s.substr(right, words[0].size());hash2[temp]++;//这里hash2[temp] == Hash_words[temp]时,还需要再count++,因为有可能遇到s中连续相同的串,我要确保当前位置的串和后面的串能利用上if (Hash_words.count(temp) && hash2[temp] <= Hash_words[temp]){count++;}// 判断if (right - left + 1 > (words.size() * words[0].size())){// 出窗⼝ + 维护 countstring out = s.substr(left, words[0].size());if (Hash_words.count(out) && hash2[out] <= Hash_words[out]) count--;hash2[out]--;left += words[0].size();}// 更新结果if (count == words.size()){ret.push_back(left);}}cnt++;}return ret;
}
};
相关文章:
【滑动窗口】Leetcode 串联所有单词的子串
题目解析 30. 串联所有单词的子串 本题的意思就是在目标串s中寻找能够找到的words字符串的全排列,返回起始位置 算法讲解 我们可以将这道题转化为寻找目标串的words字母的异位词,按照上一次讲解的【滑动窗口】Leetcode 找到字符串中所有字母异位词我们…...
golang channel实践代码及注意事项
在使用Go语言(Golang)的通道(Channel)时,有几个重要的注意点可以帮助开发者更安全、高效地使用它们进行并发编程。以下是一些关键的注意事项: 选择正确的通道类型:Go语言提供了两种类型的通道&…...
面试题:RabbitMQ 消息队列中间件
1. 确保消息不丢失 生产者确认机制 确保生产者的消息能到达队列,如果报错可以先记录到日志中,再去修复数据持久化功能 确保消息未消费前在队列中不会丢失,其中的交换机、队列、和消息都要做持久化消费者确认机制 由spring确认消息处理成功后…...
wpf中引用自定义字体
在WPF(Windows Presentation Foundation)中,FontFamily属性用于指定控件或文本元素使用的字体。它是一个非常基础且重要的属性,影响着用户界面的视觉呈现和可读性。以下是关于WPF中FontFamily属性的一些关键信息和使用方法&#x…...
高效准确!指甲剪盖片视觉检测技术解密
指甲剪的盖片是指指甲剪的一端,通常用来盖住另一端的刀刃部分。指甲剪盖片是指甲剪的重要部分,除了保护刀刃外,还起到美观和便捷的作用。正确使用和保养指甲剪盖片可以延长指甲剪的使用寿命。 本案是对指甲剪盖片最大尺寸长75mm*宽10mm*高3mm…...
分布式IO模块PLC扩展模拟量模块
BL200是一款结构紧凑、体积小的分布式IO耦合器,支持ModbusTCP协议,采用嵌入式硬件,主频380Mhz,基于LinuxOS,采用独特的MAC层数据交换技术的双网口技术实现级联,中间设备宕机不影响后面设备的数据传输,可支持高达32个AI、DI、DO、热电阻、热电偶、RS485等种类的IO板,广泛应用于工…...
Qt事件系统
第三章Qt事件系统 文章目录 第三章Qt事件系统1.事件系统事件是如何传递的事件类型事件处理发送事件 2.事件传播机制事件接受和忽略事件分发事件过滤 3.事件和信号的区别 1.事件系统 在Qt中,事件是派生抽象QEvent类的对象,它表示应用程序内发生的事情&am…...
C++STL--排序算法
sort 使用快速排序,平均性能好O(nlogn),但最差情况可能很差O(n^2)。不稳定。 sort(v.begin(),v.end());//对v容器进行排序,默认升序 sort(v.begin(),v.end(),greater<int>());//降序排序对于支持随机访问的迭代器的容器, 都可以利用sort算法直接对其进行排序…...
CEF的了解
(14 封私信 / 80 条消息) CEF和Electron的区别是什么? - 知乎 (zhihu.com) Electron面向的开发者:会用JavaScript,HTML,CSS,不会C CEF面向的开发者:会用JavaScript,HTML,CSS,会C (14 封私信 / 80 条消息) liulun - …...
基于OrangePi Zero2的智能家居项目(开发阶段)
智能家居项目的软件实现 紧接上文 基于OrangePi Zero2的智能家居项目(准备阶段)-CSDN博客 目录 一、项目整体设计 1.1项目整体设计 1.2具体划分 二、开发工作的前期准备 1、进行分类,并用Makefile文件进行管理 参考:自己创…...
数据结构记录
之前记录的数据结构笔记,不过图片显示不了了 数据结构与算法(C版) 1、绪论 1.1、数据结构的研究内容 一般应用步骤:分析问题,提取操作对象,分析操作对象之间的关系,建立数学模型。 1.2、基本概念和术语 数据&…...
从零到一:基于 K3s 快速搭建本地化 kubeflow AI 机器学习平台
背景 Kubeflow 是一种开源的 Kubernetes 原生框架,可用于开发、管理和运行机器学习工作负载,支持诸如 PyTorch、TensorFlow 等众多优秀的机器学习框架,本文介绍如何在 Mac 上搭建本地化的 kubeflow 机器学习平台。 注意:本文以 …...
kettle使用MD5加密增量获取接口数据
kettle使用MD5加密增量获取接口数据 场景介绍: 使用JavaScript组件进行MD5加密得到Http header,调用API接口增量获取接口数据,使用json input组件解析数据入库 案例适用范围: MD5加密可参考、增量过程可参考、调用API接口获取…...
PS入门|黑白色的图标怎么抠成透明背景
前言 抠图可以算是PS的入门必备操作,开始学习PS的小伙伴可以根据本帖子推荐一步步学习哦!但切勿心急~ 今天给小伙伴们带来:黑白色的图标抠图教程 抠图有很多种方法,但根据类型的不同,使用适当的方法很重…...
android 14 apexd分析(2)apexd 启动
1. class main进程一起启动, apexservice是他提供的binderservice,这也第二阶段的最主要的作用 /system/apex/apexd/apexd.rc?r3c8e8603c640fc41e0406ddcf981381803447cfb#1 1 service apexd /system/bin/apexd 2 interface aidl apexservice …...
微信小程序怎么制作?制作一个微信小程序需要多少钱?
随着移动互联网的快速发展,微信小程序已成为连接用户与服务的重要桥梁。它以其便捷性和易用性,为各类企业和个人提供了一个全新的展示和交易平台。那么,如何制作一个微信小程序?又需要投入多少资金呢?本文将为您提供全…...
WPS二次开发专题:如何获取应用签名SHA256值
作者持续关注WPS二次开发专题系列,持续为大家带来更多有价值的WPS开发技术细节,如果能够帮助到您,请帮忙来个一键三连,更多问题请联系我(QQ:250325397) 在申请WPS SDK授权版时候需要开发者提供应用包名和签…...
Flink SQL系列之:基于Flink SQL查询Topic中序列化的Debezium数据格式字段
Flink SQL系列之:基于Flink SQL查询Topic中序列化的Debezium数据格式字段 一、表结构二、查询Topic中表的数据三、反序列化字段一、表结构 CREATE TABLE IF NOT EXISTS record_rt (id decimal(20,0) COMMENT "主键",follow_entity_type <...
【WPF应用30】WPF中的ListBox控件详解
WPF(Windows Presentation Foundation)是.NET框架的一个组成部分,用于构建桌面应用程序的用户界面。ListBox是WPF中一个非常常用的控件,用于显示一系列的项,用户可以选择单个或多个项。 1.ListBox的基本概念 ListBox…...
Chatgpt掘金之旅—有爱AI商业实战篇(二)
演示站点: https://ai.uaai.cn 对话模块 官方论坛: www.jingyuai.com 京娱AI 一、前言: 成为一名商业作者是一个蕴含着无限可能的职业选择。在当下数字化的时代,作家们有着众多的平台可以展示和推广自己的作品。无论您是对写书、文…...
C++vector,智能指针,拷贝构造函数
我将分别介绍 C 中的智能指针、std::vector 动态数组以及拷贝构造函数的概念、用法和适用场景。一、C 智能指针智能指针是用于自动化管理动态分配内存的模板类,位于 <memory> 头文件中。它们通过 RAII(Resource Acquisition Is Initialization&…...
告别龟速下载:用阿里云镜像源5分钟搞定CentOS 8 Stream + 宝塔面板环境
极速部署CentOS 8 Stream与宝塔面板:阿里云镜像实战指南 每次在服务器上配置环境时,最让人抓狂的就是漫长的等待时间。特别是当需要从国外官方源下载安装包时,那个进度条简直像蜗牛爬行。我曾经花了整整一个下午只为安装基础环境,…...
开源键盘固件终极配置指南:轻松自定义你的机械键盘
开源键盘固件终极配置指南:轻松自定义你的机械键盘 【免费下载链接】vial-qmk QMK fork with Vial-specific features. 项目地址: https://gitcode.com/gh_mirrors/vi/vial-qmk 想要完全掌控你的机械键盘,打造独一无二的输入体验吗?Vi…...
TuShare实战(二)高效构建多股数据面板
1. 为什么需要多股数据面板 做量化投资的朋友都知道,数据准备是最基础也最耗时的环节。想象一下,你正在研究一个投资策略,需要同时分析5只股票的历史走势。如果每次都要单独获取、整理每只股票的数据,那效率实在太低了。这就是为什…...
这份榜单够用!高效论文写作全流程AI论文软件推荐(2026 最新)
2026年AI论文软件持续升级,论文写作全流程可拆解为文献调研→选题/开题→大纲/初稿→文献综述→降重/去AI味→润色/格式→查重/投稿七大环节,以下工具按环节精准匹配,兼顾中文适配、降重能力、去AI痕迹、学术合规四大核心需求,覆盖…...
重新定义你的窗口管理体验 - StreamWindow 4.0
StreamWindow 4.0版本带来了重大更新,也做了很多优化和完善。 距离发布APP已经过去小半年了,这款macOS上的3D窗口管理工具随着4.0版本通过审核,带来大量的功能更新和完善,尤其引入了一种新的动画特效:扑克牌洗牌特效。…...
Vue3最新版二维码生成避坑指南:从基础配置到企业级定制(附GitHub源码)
Vue3企业级二维码生成实战:从核心原理到性能优化 二维码作为连接物理世界与数字世界的桥梁,在现代Web应用中扮演着重要角色。本文将带您深入Vue3的二维码生成技术栈,不仅涵盖基础实现,更聚焦企业级应用中的高阶技巧与性能优化方案…...
从零到一:Vision Pro工业视觉软件安装与配置实战指南
1. Vision Pro工业视觉软件入门指南 第一次接触Vision Pro的朋友可能会被这个强大的工业视觉软件震撼到。作为康耐视的拳头产品,它在汽车制造、电子检测、包装印刷等行业应用广泛。我刚开始用的时候也是一头雾水,但跟着正确的步骤走,其实安装…...
SEO_资深运营的SEO外链建设核心技巧
<h2>SEO外链建设:资深运营的核心技巧解析</h2> <p>在当今数字营销的竞争激烈环境中,搜索引擎优化(SEO)外链建设是提升网站排名的关键因素之一。资深运营者在这一领域已经积累了丰富的经验,他们不仅仅…...
FireRed-OCR保姆级教程:一键部署,精准提取表格公式转Markdown
FireRed-OCR保姆级教程:一键部署,精准提取表格公式转Markdown 1. 引言:为什么选择FireRed-OCR? 在日常工作和学习中,我们经常遇到需要从PDF、图片等文档中提取表格、公式等内容的情况。传统OCR工具往往难以准确识别复…...

每一次left和right一开始都指向同一个位置,当滑动窗口移动到字符串s结束的时候,需要将left+1,开始继续滑动下一次的循环