算法(滑动窗口四)
1.串联所有单词的子串
给定一个字符串 s
和一个字符串数组 words
。 words
中所有字符串 长度相同。
s
中的 串联子串 是指一个包含 words
中所有字符串以任意顺序排列连接起来的子串。
- 例如,如果
words = ["ab","cd","ef"]
, 那么"abcdef"
,"abefcd"
,"cdabef"
,"cdefab"
,"efabcd"
, 和"efcdab"
都是串联子串。"acdbef"
不是串联子串,因为他不是任何words
排列的连接。
返回所有串联子串在 s
中的开始索引。你可以以 任意顺序 返回答案。
示例 1:
输入:s = "barfoothefoobarman", words = ["foo","bar"]
输出:[0,9]
解释:因为 words.length == 2 同时 words[i].length == 3,连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。
示例 2:
输入:s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出:[]
解释:因为 words.length == 4 并且 words[i].length == 4,所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。
示例 3:
输入:s = "barfoofoobarthefoobarman", words = ["bar","foo","the"] 输出:[6,9,12] 解释:因为 words.length == 3 并且 words[i].length == 3,所以串联子串的长度必须为 9。 子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。 子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。 子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。
算法原理
我们随便来看一个例子 输入:s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
我们把bar 看成一个a,foo看成一个b,the看成一个c
这个题的s就可以看成一串 abbacvad
这样这个题就变成一个找出字符串你的异位字符,变成跟我们做的上个题是一样的
这道题我们要熟练的运用容器以及哈希表和List表
这道题我们right-left的长度不能大于words数组的长度,即单词的长度
由于我们不确定从哪里开始是我们想要找的单词的首字母,我们需要遍历单个单词的每个字母如下图所示
我们要对一个单词遍历这个单词的每个字母,所以我们要套两层for循环
第一层for循环就是 for(int i=0;i<len;i++) 表示words单词里面每个单词的长度
1.定义left=i,right=i 还需要定义一个count用来记录单词的数量定义两个哈希表,一个哈希表hash1用来记录words数组里面单词的个数,一个哈希表hash2用来记录s表内的单词,用len表示words单词的长度
2.我们的起始位置是right=i,终止位置时 right+len 每次向后移动都是移动len的长度
3.我们首先需要进窗口,用in来接受进入窗口的单词,然后我们判断进来窗口的单是否在 hash1中存在 存在就count++
3,当我们一直向后判断,当right-left的值>words里面字符的m(m表示单词的个数)*len了 说明此时我们应该出窗口了 在出窗口前我们需要判断出窗口的单词是否存在于hash1表中,存在我们就count--
然后left+len判断下一个单词
4.当count==m 说明此时正是我们要找的子串,我们输出left的值
代码如下
class Solution {public List<Integer> findSubstring(String s, String[] words) {List<Integer>ret=new ArrayList();Map<String,Integer>hash1=new HashMap<String,Integer>();for(String str:words)hash1.put(str,hash1.getOrDefault(str,0)+1);int len=words[0].length(),m=words.length;for(int i=0;i<len;i++){Map<String,Integer>hash2=new HashMap<String,Integer>();for(int left=i,right=i,count=0;right+len<=s.length();right+=len){String in=s.substring(right,right+len);hash2.put(in,hash2.getOrDefault(in,0)+1);if(hash2.get(in)<=hash1.getOrDefault(in,0))count++;if(right-left+1>len*m){String out=s.substring(left,left+len);if(hash2.get(out)<=hash1.getOrDefault(out,0))count--;hash2.put(out,hash2.get(out)-1);left+=len;}if(count==m){ret.add(left);}}}return ret;}
}
2.最小覆盖子串
给你一个字符串 s
、一个字符串 t
。返回 s
中涵盖 t
所有字符的最小子串。如果 s
中不存在涵盖 t
所有字符的子串,则返回空字符串 ""
。
注意:
- 对于
t
中重复字符,我们寻找的子字符串中该字符数量必须不少于t
中该字符数量。 - 如果
s
中存在这样的子串,我们保证它是唯一的答案。
示例 1:
输入:s = "ADOBECODEBANC", t = "ABC" 输出:"BANC" 解释:最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
示例 2:
输入:s = "a", t = "a" 输出:"a" 解释:整个字符串 s 是最小覆盖子串。
示例 3:
输入: s = "a", t = "aa" 输出: "" 解释: t 中两个字符 'a' 均应包含在 s 的子串中, 因此没有符合条件的子字符串,返回空字符串。
程序解法:
1.暴力解法:通过暴力枚举,枚举出所有结果,然后比对所有结果那个子串最短
2.滑动窗口+哈希表
算法原理
这个题我们依旧用滑动窗口来做,并且用数组来模拟哈希表
如图我们有以下的一个字符串,我们要找的是abc的最小子串,
1.我们给字符串和abc串各创建一个数组
int[]hash1=new int[128];
int[] hash2=new int[128];
hash1用来存放abc,hash2用来存放长的字符串
我们来统计hash1中的个数,这里使用统计个数的方式不可取,因为长的字符串中有可能有多个一样的字符,我们就取第一次出现的字符为新的字符,就是取种类的个数
for(char ch:t){if(hash1[ch]==0)kinds++;hash1[ch]++;}
2.采用滑动窗口的方式
定义left=0,right=0,count=0;
我们首先进入窗口,进窗口之后判断hash2[right]==hash1[right] 相等就++
int minlen=Integer.MAX_VALUE,begin=-1;for(int left=0,right=0,count=0;right<ss.length();right++){char in=s[right];hash2[in]++;if(hash1[in]==hash2[in])count++;
然后当kind和count相等时 我们更新结果,取出当前right-left+1的值,和开始的值
int minlen=Integer.MAX_VALUE,begin=-1;
while(kinds==count){if(right-left+1<minlen){minlen=right-left+1;begin=left;}
3.更新完结果后我们出窗口
char out=s[left];left++;if(hash1[out]==hash2[out]) count--;hash2[out]--;
最后代码如下
class minWindow {public String minWindow1 (String ss, String tt) {char s[]=ss.toCharArray();char t[]=tt.toCharArray();int[]hash1=new int[128];int[] hash2=new int[128];int kinds=0;for(char ch:t){if(hash1[ch]==0)kinds++;hash1[ch]++;}int minlen=Integer.MAX_VALUE,begin=-1;for(int left=0,right=0,count=0;right<ss.length();right++){char in=s[right];hash2[in]++;if(hash1[in]==hash2[in])count++;while(kinds==count){if(right-left+1<minlen){minlen=right-left+1;begin=left;}char out=s[left];left++;if(hash1[out]==hash2[out]) count--;hash2[out]--;}}if(begin==-1)return new String();else return ss.substring(begin,begin+minlen);}public static void main(String[] args) {minWindow minWindow=new minWindow();String s="ADOBECODEBANC";String t="AABC";String result= minWindow.minWindow1(s,t);System.out.println(result);}
}
相关文章:
算法(滑动窗口四)
1.串联所有单词的子串 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。 s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。 例如,如果 words ["ab","cd","ef"]ÿ…...
学习记录:bazel和cmake运行终端指令
Bazel和CMake都是用于构建软件项目的工具,但它们之间有一些重要的区别和特点: Bazel: Bazel是由Google开发的构建和测试工具,用于构建大规模的软件项目。它采用一种称为“基于规则”的构建系统,它利用构建规则和依赖关…...
蓝桥杯刷题--python-37-分解质因数
3491. 完全平方数 - AcWing题库 nint(input()) res1 i2 while i*i<n: if n%i0: t0 while n%i0: n//i t1 if t%2: res*i i1 if n>1: res*n print(res) 4658. 质因数个数 - AcWing题库…...
Delphi编写的图片查看器
UNIT Unit17;INTERFACEUSESWinapi.Windows, Winapi.Messages, System.SysUtils, System.Variants,System.Classes, Vcl.Graphics, Vcl.Controls, Vcl.Forms, Vcl.Dialogs,Vcl.StdCtrls, Vcl.ExtDlgs, Vcl.ExtCtrls, Vcl.Imaging.jpeg; //注意:要加入jpej 否侧浏览图…...
Swing中的FlowLayout/WrapLayout在打横排列时候如何做到置顶对齐
前言 最近在开发swing客户端时候碰到一个棘手的问题: Swing中的FlowLayout/WrapLayout在打横排列时候如何做到置顶对齐如果是vue或者react,一搜百度什么都出来了,swing的话,嗯。。。资料有点少而且大部分是stack overflow上面的…...
C# MES通信从入门到精通(8)——C#调用Webservice服务进行数据交互
前言 在上位机开发领域,使用webservice来访问客户的终端Mes系统是一项必备的技能,本文详细介绍了如何在c#中调用webservice服务,不仅介绍了使用添加服务引用直接调用webservice中的方法外还介绍了使用http的post方法调用webservice方法,过程详细且均为实战经验总结,对于初…...
day04-MQ
1.初识MQ 1.1.同步和异步通讯 微服务间通讯有同步和异步两种方式: 同步通讯:就像打电话,需要实时响应。异步通讯:就像发邮件,不需要马上回复。 两种方式各有优劣,打电话可以立即得到响应,但是你…...
神经网络汇聚层
文章目录 最大汇聚层平均汇聚层自适应平均池化层 最大汇聚层 汇聚窗口从输入张量的左上角开始,从左往右、从上往下的在输入张量内滑动。在汇聚窗口到达的每个位置,它计算该窗口中输入子张量的最大值或平均值。计算最大值或平均值是取决于使用了最大汇聚…...
2024.3.8力扣每日一题——找出美丽数组的最小和
2024.3.8 题目来源我的题解方法一 数学 题目来源 力扣每日一题;题序:2834 我的题解 方法一 数学 经过分析,在target之前,取小于等于target/2的正整数才能使得和最小,并且满足条件3。 时间复杂度:O(n) 空…...
单例模式以及线程安全问题
单例模式的概念 单例模式是指的是整个系统生命周期内,保证一个类只能产生一个实例对象 保证类的唯一性 。 通过一些编码上的技巧,使编译器可以自动发现咱们的代码中是否有多个实例,并且在尝试创建多个实例的时候,直接编译出错。 …...
车载电子电器架构 —— 软件下载
车载电子电器架构 —— 软件下载 我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 屏蔽力是信息过载时代一个人的特殊竞争力,任何消耗你的人和事,多看一眼都是你的不对。非必要不费力证明自己,无…...
阿里云弹性计算通用算力型u1实例性能评测,性价比高
阿里云服务器u1是通用算力型云服务器,CPU采用2.5 GHz主频的Intel(R) Xeon(R) Platinum处理器,ECS通用算力型u1云服务器不适用于游戏和高频交易等需要极致性能的应用场景及对业务性能一致性有强诉求的应用场景(比如业务HA场景主备机需要性能一致)…...
Jupyter IPython帮助文档及其魔法命令
1.IPython 的帮助文档 使用 help() 使用 ? 使用 ?? tab 自动补全 shift tab 查看参数和函数说明 2.运行外部 Python 文件 使用下面命令运行外部 Python 文件(默认是当前目录,也可以使用绝对路径) %run *.py …...
设计模式总结-面向对象设计原则
面向对象设计原则 面向对象设计原则简介单一职责原则单一职责原则定义单一职责原则分析单一职责原则实例 开闭原则开闭原则定义开闭原则分析开闭原则实例 里氏代换原则里氏代换原则定义里氏代换原则分析 依赖倒转原则依赖倒转原则定义依赖倒转原则分析依赖倒转原则实例 接口隔离…...
绿联 安装zfile,创建属于自己的网盘,支持直链分享
绿联 安装zfile,创建属于自己的网盘,支持直链分享 1、镜像 zhaojun1998/zfile:latest ZFile ZFile 是一个适用于个人的在线网盘(列目录)程序,可以将你各个存储类型的存储源,统一到一个网页中查看、预览、维护,再也不用…...
KnowLog:基于知识增强的日志预训练语言模型|顶会ICSE 2024论文
徐波 东华大学副教授 东华大学计算机学院信息技术系副系主任,复旦大学知识工场实验室副主任,智能运维方向负责人。入选“上海市青年科技英才扬帆计划”。研究成果发表在IJCAI、ICDE、ICSE、ISSRE、ICWS、CIKM、COLING等国际会议上,曾获中国数…...
前端:用Sass简化媒体查询
在进行媒体查询的编写的时候,我们可以利用scss与与编译器,通过include混入的方式对代码进行简化,从而大大提高了代码的可维护性,也减少了代码的编写量,废话不多说,直接上代码 // 定义设备数值 $breakpoints…...
如何快速写出漂亮的Button按钮呢?
你是否曾在浏览网页时,被那些色彩鲜艳、功能多样的按钮所吸引?无论是提交表单,还是触发一个动作,按钮都扮演着不可或缺的角色。今天聊聊网页设计中的 <button> 标签。 1. 基础语法 什么是 <button> 标签 <butto…...
美摄科技AI智能图像矫正解决方案
图像已经成为了企业传播信息、展示产品的重要媒介,在日常拍摄过程中,由于摄影技巧的限制和拍摄环境的复杂多变,许多企业面临着图像内容倾斜、构图效果不佳等挑战,这无疑给企业的形象展示和信息传递带来了不小的困扰。 美摄科技深…...
上位机图像处理和嵌入式模块部署(qmacvisual查找圆缺角)
【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing 163.com】 前面我们讲过识别,讲过标定,讲过测量,讲过匹配,但就是没有讨论过基于图像的产品检测。但事实上&…...
Python 之 Fastapi 框架学习
依赖安装 Fastapi 有版本要求,需要的 Python 版本至少是 Python 3.8(不要犟,按照版本要求来,我最先也是在我 Python3.6 上装的,果不其然跑不起来),幸好我 Win7 老古董能支持的 Python 最高版本…...
C++初阶:stack和queue使用及模拟实现
stack的介绍和使用 stack的介绍 堆栈 - C 参考 (cplusplus.com) 翻译 : 1. stack 是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作。 2. stack 是作为容器适配器被实现的,容器…...
LINUX系统CFS调度模型实现思考和仿真
关于LINUX资源调度 计算机系统中,管理资源的方式一般有两种方法,分别是时间分割和空间分割,可以通过分割硬件的相似性,让软件以一致的逻辑执行,CPU运行特点是在时刻点A和时刻B运行机制是一样的,不同的只是…...
兑换码生成算法
兑换码生成算法 兑换码生成算法1.兑换码的需求2.算法分析2.重兑校验算法3.防刷校验算法 3.算法实现 兑换码生成算法 兑换码生成通常涉及在特定场景下为用户提供特定产品或服务的权益或礼品,典型的应用场景包括优惠券、礼品卡、会员权益等。 1.兑换码的需求 要求如…...
Vue框架介绍简介
Vue.js,通常简称为Vue,是一个用于构建用户界面的渐进式框架。它发布于2014年2月,由Evan You设计并开发。Vue被设计为可以自底向上逐层应用,这使得开发者可以根据项目的需求灵活地使用Vue。无论是构建简单的轻量级应用,…...
的C++奇迹之旅:值和引用的本质效率与性能比较
文章目录 请添加图片描述 [TOC](文章目录) 📝引用# 🌠引用概念**引用**不是新定义一个变量,而是给**已存在变量取了一个别名**,编译器不会为引用变量开辟内存空间,它和它引用的变量共用同一块内存空间。>定义&#…...
【C++】vector问题解决(非法的间接寻址,迭代器失效 , memcpy拷贝问题)
送给大家一句话: 世界在旋转,我们跌跌撞撞前进,这就够了 —— 阿贝尔 加缪 vector问题解决 1 前言2 迭代器区间拷贝3 迭代器失效问题4 memcpy拷贝问题 1 前言 我们之前实现了手搓vector,但是当时依然有些问题没有解决ÿ…...
风控系统之普通规则条件,使用LiteFlow实现
个人博客:无奈何杨(wnhyang) 个人语雀:wnhyang 共享语雀:在线知识共享 Github:wnhyang - Overview 提要 参考:智能风控筑基手册:全面了解风控决策引擎 前面有可配置输入参数的接…...
在一套Dockerfile中完成编译和运行环境部署
大纲 解释型语言编译环境解释环境编译型语言编译环境运行环境 方法编译环境安装系统安装编译依赖下载代码特殊处理(可以忽略)编译准备(可以忽略)编译打包依赖(编译结果) 运行环境安装操作系统安装运行时依赖…...
ubuntu系统里克隆github代码到本地,提示fatal: unable to connect to github.com的解决方案
打开命令行终端生成一个新的SSH密钥对。如果你还没有SSH密钥或者想创建一个新的,可以使用以下命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com"当系统提示你“Enter a file in which to save the key”,时,…...
西宁做网站哪家好/网站平台做推广
ST7 单片机 C 语言编程王志杰2007.12ST7 单片机 C 语言编程目 录1 开发环境安装和配置31.1 ST7 Visual Develop 安装 31.2 COSMIC C语言编译器安装31.3 COSMIC C语言编译器配置62 创建一个Workspace和Project 83 仿真与调试134 一个程序例子184.1 概述184.2 程序清单194.3 程序…...
wordpress统计分析/东莞网络优化公司
作者 | 张俊鸣素有“大笨象”之称的银行股轻盈起舞,上证指数五天内连攻3000点到3400点之间的五个百点整数关口,“牛市来了”已经成为众多投资者的共识。伴随着汹涌入市的资金潮,日成交破万亿再度成为“新常态”,部分券商的APP一度…...
网站的网站建设公司/宁波seo企业网络推广
Spring 框架作为 Java 开发中最流行的框架之一,其核心特性之一就是依赖注入(Dependency Injection,DI)。在Spring中,依赖注入是通过 IOC 容器(Inversion of Control,控制反转)来实现…...
南山做网站哪家好/微信群推广
基于eclipse的Java文件:项目(project)<类(class)<方法(method),即方法method必须基于class, class必须基于project。 项目是程序的源代码以及程序用到的资源文件、…...
iis7如何部署网站/杭州百度百科
1、安装安卓开发环境(教程很多,不细写) 2、安装eclipse下载eclipse,解压即可3、安装python下载地址:https://www.python.org/downloads/release/python-2713/下载文件:python-2.7.13.msi配置环境变量&#…...
做网站ruby还是python/seo搜索引擎优化工资
概念 devicePixelRatio ,它是设备上物理像素和设备独立像素( device-independent pixels (dips) )的比例,即 devicePixelRatio 屏幕物理像素/设备独立像素 例如iPhone4S,分辨率为:960640,取屏幕宽度计算,…...