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

【算法挨揍日记】day08——30. 串联所有单词的子串、76. 最小覆盖子串

30. 串联所有单词的子串 

30. 串联所有单词的子串

题目描述:

给定一个字符串 s 和一个字符串数组 words words 中所有字符串 长度相同

 s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。

  • 例如,如果 words = ["ab","cd","ef"], 那么 "abcdef", "abefcd""cdabef", "cdefab""efabcd", 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串,因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

解题思路:

首先题目表示word的单词每个长度都一样,我们设为len

我们通过暴力解法来分析一下,当我们每次移动下标都下标可以+len

当然我们可能会从第一个字符开始判断也可以从第二个字符开始判断,因此第一个示例就有以下几种情况:

 也就是有len种情况

我们可以利用滑动窗口+哈希表来解决这个问题

我们还需要使用一个代表有效个数的变量count

1.进窗口——hash2【in】++,当hash2<=hash1, count++(in为要进窗口的下标的字符串)

2. 判断——当m*len>right-left+1(m为s.size())

3.更新结果——ret.push一下

4.出窗口——当hash2<=hash1,count--,hash2【out】--,left+=len(out为要出窗口的下标的字符串)

这里我写了hash1.count(in)和hash1.count(out)是为了提升速度

解题代码:

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

 76. 最小覆盖子串

76. 最小覆盖子串

题目描述: 

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。

注意:

  • 对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串,我们保证它是唯一的答案。

 解题思路:

本题还是滑动窗口+哈希

利用count和kind来解决这个问题(count为有效字符的个数,kind为种类个数)

1.进窗口——hash2[in]++,当in这个字符的个数达到要求,count++

2.判断——count==kind

3.更新结果——当length > right - left + 1,记录一下length和begin

4.出窗口

解题代码:

class Solution {
public:string minWindow(string s, string t) {unordered_map<char, int> hash1;int kind = 0;//有效字符的种数for (auto& i : t) if (hash1[i]++ == 0)kind++;int count = 0;//有效字符个数(包括数量)的种类unordered_map<char, int>hash2;int length = INT_MAX;int begin=-1;for (int left = 0, right = 0; right < s.size(); right++){char in = s[right];hash2[in]++;if (hash2[in] == hash1[in])count++;while(count == kind){if (length > right - left + 1){length = right - left + 1;begin=left;}char out = s[left];if (hash2[out]--==hash1[out])count--;out = s[++left];}}if(begin==-1)return "";string str=s.substr(begin,length);return str;}
};

相关文章:

【算法挨揍日记】day08——30. 串联所有单词的子串、76. 最小覆盖子串

30. 串联所有单词的子串 30. 串联所有单词的子串 题目描述&#xff1a; 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。 s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。 例如&#xff0c;如果 words ["…...

SpringCloud Gateway--网关服务基本介绍和基本原理

&#x1f600;前言 本篇博文是关于SpringCloud Gateway的基本介绍&#xff0c;希望你能够喜欢 &#x1f3e0;个人主页&#xff1a;晨犀主页 &#x1f9d1;个人简介&#xff1a;大家好&#xff0c;我是晨犀&#xff0c;希望我的文章可以帮助到大家&#xff0c;您的满意是我的动力…...

使用Vue-cli构建spa项目及结构解析

一&#xff0c;Vue-cli是什么&#xff1f; 是一个官方发布的Vue脚手架工具&#xff0c;用于快速搭建Vue项目结构&#xff0c;提供了现代前端开发所需要的一些基础功能&#xff0c;例如&#xff1a;Webpack打包、ESLint语法检查、单元测试、自动化部署等等。同时&#xff0c;Vu…...

自定义Unity组件——AudioManager(音频管理器)

需求描述 在游戏开发中&#xff0c;音频资源是不可或缺的&#xff0c;通常情况下音频资源随机分布&#xff0c;各个音频的操作和管理都是各自负责&#xff0c;同时对于音频的很多操作逻辑都是大同小异的&#xff0c;这就造成了许多冗余代码的堆叠&#xff0c;除此之外在获取各类…...

leetcode 558 设计内存文件系统

题目 Design an in-memory file system to simulate the following functions: ls: Given a path in string format. If it is a file path, return a list that only contains this files name. If it is a directory path, return the list of file and directory namesin th…...

Haproxy负载均衡群集

HAproxy搭建Web群集一、Web集群调度器1、常见的Web集群调度器2、常用集群调度器的优缺点&#xff08;LVS ,Nginx,Haproxy)2.1 Nginx2.2 LVS2.3 Haproxy 3、LVS、Nginx、HAproxy的区别 二、Haproxy1、简介2、Haproxy应用分析3、HAProxy的主要特性4、Haproxy调度算法&#xff08;…...

什么是面包屑导航?

面包屑导航(Breadcrumb Navigation)这个概念来自童话故事“汉赛尔和格莱特”&#xff0c;当汉赛尔和格莱特穿过森林时&#xff0c;不小心迷路了&#xff0c;但是他们发现沿途走过的地方都撒下了面包屑&#xff0c;让这些面包屑来帮助他们找到回家的路。 在网站应用中&#xff0…...

VS2019创建GIt仓库时剔除文件或目录

假设本地有解决方案“SomeSolution” 1、首先”团队资源管理器“-“创建Git存储库”&#xff0c;选择“仅限本地”、“创建” VS会在解决方案目录下自动生成.gitattributes、.gitignore 2、编辑gitignore&#xff0c;直接拖到VS里或者用记事本打开。添加要剔除的文件或文件夹…...

计算机等级考试—信息安全三级真题六

目录 一、单选题 二、填空题 三、综合题 一、单选题...

vue循环滚动字幕

在Vue.js中创建一个循环滚动字幕的效果通常需要使用一些CSS和JavaScript来实现。以下是一个简单的示例&#xff0c;展示如何使用Vue.js创建一个循环滚动字幕的效果&#xff1a; 首先&#xff0c;在HTML中创建一个Vue实例&#xff0c;并添加一个包含滚动字幕的容器元素&#xff…...

扩展pytest接口自动化框架-MS数据解析功能

【软件测试行业现状】2023年了你还敢学软件测试&#xff1f;未来已寄..测试人该何去何从&#xff1f;【自动化测试、测试开发、性能测试】 开篇 MeterSphere的数据源通过html页面上传后&#xff0c;需要将请求方式进行拆分。 get接口的参数&#xff0c;常以params的方式进行传…...

docker容器安装MongoDB数据库

一&#xff1a;MongoDB数据库 1.1 简介 MongoDB是一个开源、高性能、无模式的文档型数据库&#xff0c;当初的设计就是用于简化开发和方便扩展&#xff0c;是NoSQL数据库产品中的一种。是最 像关系型数据库&#xff08;MySQL&#xff09;的非关系型数据库。 它支持的数据结构…...

Python机器学习实战-特征重要性分析方法(3):迭代删除法:Leave-one-out(附源码和实现效果)

实现功能 迭代地每次删除一个特征并评估准确性 实现代码 from sklearn.datasets import load_breast_cancer from sklearn.model_selection import train_test_split from sklearn.ensemble import RandomForestClassifier from sklearn.metrics import accuracy_score impo…...

Go的error接口

从本书的开始&#xff0c;我们就已经创建和使用过神秘的预定义error类型&#xff0c;而且没有解释它究竟是什么。实际上它就是interface类型&#xff0c;这个类型有一个返回错误信息的单一方法&#xff1a; type error interface { Error() string } 创建一个error最简单的方…...

RabbitMQ 集群 - 普通集群、镜像集群、仲裁队列

目录 一、RabbitMQ 集群 1.1、前言 1.2、普通集群 1.3、镜像集群 1.4、仲裁队列 一、RabbitMQ 集群 1.1、前言 前面我们已经解决了消息可靠性问题&#xff0c;以及延迟消息问题 和 消息堆积问题. 这最后一章&#xff0c;我们就来解决以下 mq 的可用性 和 并发能力. 1.2、…...

高项新版教程(第四版)解读+学习指导

第四版主要内容 技术部分 信息化教程、软件工程、网络技术是原来的&#xff0c;学习原来的录播。 新基建、工业互联网、车联网、农业现代化、数字化转型、元宇宙等是新增&#xff0c;以直播讲。 管理部分 变化不是太大 。 整合管理、人力变为资源管理、风险管理新增内容。 …...

【Debian】Debian10.0.0安装选项问答

debian的LXQT是什么&#xff1f; LXQT是一套轻量级的桌面环境,主要基于Qt框架开发。 LXQT在debian中的具体特点包括: - 使用Openbox作为窗口管理器,提供平铺式窗口布局。 - 文件管理器为PCManFM-Qt。 - 设置中心集成 debconf 配置界面。 - 支持GTK和Qt应用程序。 - 资源消耗较低…...

【基于React-Native做位置信息获取,并展示出来】

基于React-Native做位置信息获取 在这个里面最重要的是两个部分&#xff0c;一个是位置定位的权限获取&#xff0c;一个是实时位置的监听&#xff0c;在安卓项目中&#xff0c;在 android/app/src/main/AndroidManifest.xml该文件下&#xff0c;在< manifest > 标签内写…...

ansible安装、点对点Ad-Hoc、模块、剧本Playbook

DevOps: 官网&#xff1a;https://docs.ansible.com 自动化运维工具对比 C/S 架构:客户端/服务端 Puppet:基于 Ruby 开发,采用 C/S 架构,扩展性强,基于 SSL,远程命令执行相对较弱 SaltStack:基于 Python 开发,采用 C/S 架构,YAML使得配置脚本更简单.需要配置客户端及服务器…...

Ceph入门到精通-ceph pool 删除导致 misplaced 的原因

misplaced 的原因 Ceph中的misplaced对象是指将对象&#xff08;或对象的副本&#xff09;存储在错误的位置上&#xff0c;这可能会导致性能下降或数据不一致的问题。在删除Ceph池时&#xff0c;可能会导致misplaced的原因有以下几个&#xff1a; 删除过程中的操作失误&#x…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式

今天是关于AI如何在教学中增强学生的学习体验&#xff0c;我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育&#xff0c;这并非炒作&#xff0c;而是已经发生的巨大变革。教育机构和教育者不能忽视它&#xff0c;试图简单地禁止学生使…...