当前位置: 首页 > 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…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...

uniapp 小程序 学习(一)

利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 &#xff1a;开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置&#xff0c;将微信开发者工具放入到Hbuilder中&#xff0c; 打开后出现 如下 bug 解…...

Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?

Pod IP 的本质与特性 Pod IP 的定位 纯端点地址&#xff1a;Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址&#xff08;如 10.244.1.2&#xff09;无特殊名称&#xff1a;在 Kubernetes 中&#xff0c;它通常被称为 “Pod IP” 或 “容器 IP”生命周期&#xff1a;与 Pod …...