【算法挨揍日记】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. 串联所有单词的子串 题目描述: 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。 s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。 例如,如果 words ["…...
SpringCloud Gateway--网关服务基本介绍和基本原理
😀前言 本篇博文是关于SpringCloud Gateway的基本介绍,希望你能够喜欢 🏠个人主页:晨犀主页 🧑个人简介:大家好,我是晨犀,希望我的文章可以帮助到大家,您的满意是我的动力…...
使用Vue-cli构建spa项目及结构解析
一,Vue-cli是什么? 是一个官方发布的Vue脚手架工具,用于快速搭建Vue项目结构,提供了现代前端开发所需要的一些基础功能,例如:Webpack打包、ESLint语法检查、单元测试、自动化部署等等。同时,Vu…...
自定义Unity组件——AudioManager(音频管理器)
需求描述 在游戏开发中,音频资源是不可或缺的,通常情况下音频资源随机分布,各个音频的操作和管理都是各自负责,同时对于音频的很多操作逻辑都是大同小异的,这就造成了许多冗余代码的堆叠,除此之外在获取各类…...
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、常用集群调度器的优缺点(LVS ,Nginx,Haproxy)2.1 Nginx2.2 LVS2.3 Haproxy 3、LVS、Nginx、HAproxy的区别 二、Haproxy1、简介2、Haproxy应用分析3、HAProxy的主要特性4、Haproxy调度算法(…...
什么是面包屑导航?
面包屑导航(Breadcrumb Navigation)这个概念来自童话故事“汉赛尔和格莱特”,当汉赛尔和格莱特穿过森林时,不小心迷路了,但是他们发现沿途走过的地方都撒下了面包屑,让这些面包屑来帮助他们找到回家的路。 在网站应用中࿰…...
VS2019创建GIt仓库时剔除文件或目录
假设本地有解决方案“SomeSolution” 1、首先”团队资源管理器“-“创建Git存储库”,选择“仅限本地”、“创建” VS会在解决方案目录下自动生成.gitattributes、.gitignore 2、编辑gitignore,直接拖到VS里或者用记事本打开。添加要剔除的文件或文件夹…...
计算机等级考试—信息安全三级真题六
目录 一、单选题 二、填空题 三、综合题 一、单选题...
vue循环滚动字幕
在Vue.js中创建一个循环滚动字幕的效果通常需要使用一些CSS和JavaScript来实现。以下是一个简单的示例,展示如何使用Vue.js创建一个循环滚动字幕的效果: 首先,在HTML中创建一个Vue实例,并添加一个包含滚动字幕的容器元素ÿ…...
扩展pytest接口自动化框架-MS数据解析功能
【软件测试行业现状】2023年了你还敢学软件测试?未来已寄..测试人该何去何从?【自动化测试、测试开发、性能测试】 开篇 MeterSphere的数据源通过html页面上传后,需要将请求方式进行拆分。 get接口的参数,常以params的方式进行传…...
docker容器安装MongoDB数据库
一:MongoDB数据库 1.1 简介 MongoDB是一个开源、高性能、无模式的文档型数据库,当初的设计就是用于简化开发和方便扩展,是NoSQL数据库产品中的一种。是最 像关系型数据库(MySQL)的非关系型数据库。 它支持的数据结构…...
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接口
从本书的开始,我们就已经创建和使用过神秘的预定义error类型,而且没有解释它究竟是什么。实际上它就是interface类型,这个类型有一个返回错误信息的单一方法: type error interface { Error() string } 创建一个error最简单的方…...
RabbitMQ 集群 - 普通集群、镜像集群、仲裁队列
目录 一、RabbitMQ 集群 1.1、前言 1.2、普通集群 1.3、镜像集群 1.4、仲裁队列 一、RabbitMQ 集群 1.1、前言 前面我们已经解决了消息可靠性问题,以及延迟消息问题 和 消息堆积问题. 这最后一章,我们就来解决以下 mq 的可用性 和 并发能力. 1.2、…...
高项新版教程(第四版)解读+学习指导
第四版主要内容 技术部分 信息化教程、软件工程、网络技术是原来的,学习原来的录播。 新基建、工业互联网、车联网、农业现代化、数字化转型、元宇宙等是新增,以直播讲。 管理部分 变化不是太大 。 整合管理、人力变为资源管理、风险管理新增内容。 …...
【Debian】Debian10.0.0安装选项问答
debian的LXQT是什么? LXQT是一套轻量级的桌面环境,主要基于Qt框架开发。 LXQT在debian中的具体特点包括: - 使用Openbox作为窗口管理器,提供平铺式窗口布局。 - 文件管理器为PCManFM-Qt。 - 设置中心集成 debconf 配置界面。 - 支持GTK和Qt应用程序。 - 资源消耗较低…...
【基于React-Native做位置信息获取,并展示出来】
基于React-Native做位置信息获取 在这个里面最重要的是两个部分,一个是位置定位的权限获取,一个是实时位置的监听,在安卓项目中,在 android/app/src/main/AndroidManifest.xml该文件下,在< manifest > 标签内写…...
ansible安装、点对点Ad-Hoc、模块、剧本Playbook
DevOps: 官网:https://docs.ansible.com 自动化运维工具对比 C/S 架构:客户端/服务端 Puppet:基于 Ruby 开发,采用 C/S 架构,扩展性强,基于 SSL,远程命令执行相对较弱 SaltStack:基于 Python 开发,采用 C/S 架构,YAML使得配置脚本更简单.需要配置客户端及服务器…...
Ceph入门到精通-ceph pool 删除导致 misplaced 的原因
misplaced 的原因 Ceph中的misplaced对象是指将对象(或对象的副本)存储在错误的位置上,这可能会导致性能下降或数据不一致的问题。在删除Ceph池时,可能会导致misplaced的原因有以下几个: 删除过程中的操作失误&#x…...
stm32G473的flash模式是单bank还是双bank?
今天突然有人stm32G473的flash模式是单bank还是双bank?由于时间太久,我真忘记了。搜搜发现,还真有人和我一样。见下面的链接:https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...
Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
MVC 数据库
MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...



也就是有len种情况