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

手撕算法-最小覆盖子串

描述

image.png

分析

滑动窗口。

参考力扣官方的题解思路

本问题要求我们返回字符串 s 中包含字符串 t 的全部字符的最小窗口。我们称包含 t 的全部字母的窗口为「可行」窗口。

我们可以用滑动窗口的思想解决这个问题。在滑动窗口类型的问题中都会有两个指针,一个用于「延伸」现有窗口的 r 指针,和一个用于「收缩」窗口的 l 指针。在任意时刻,只有一个指针运动,而另一个保持静止。我们在 s 上滑动窗口,通过移动 r 指针不断扩张窗口。当窗口包含 t 全部所需的字符后,如果能收缩,我们就收缩窗口直到得到最小窗口。

如何判断当前的窗口包含所有 t 所需的字符呢?我们可以用一个哈希表表示 t 中所有的字符以及它们的个数,用一个哈希表动态维护窗口中所有的字符以及它们的个数,如果这个动态表中包含 t 的哈希表中的所有字符,并且对应的个数都不小于 t 的哈希表中各个字符的个数,那么当前的窗口是「可行」的。

直接看代码。

代码

版本1:(超时)

    public static String minWindow(String s, String t) {// 记录t中的所有字符和数量HashMap<Character, Integer> map = new HashMap<>();for (int i = 0; i < t.length(); i++) {map.put(t.charAt(i), map.getOrDefault(t.charAt(i), 0) + 1);}int minLen = Integer.MAX_VALUE;int left = 0, right = 0;// 滑动窗口,左边固定,右边滑动for (int i = 0; i < s.length(); i++) {if (s.length()-i < t.length()) break;HashMap<Character, Integer> tmp = new HashMap<>(map);for (int j = i; j < s.length(); j++) {if (tmp.containsKey(s.charAt(j))) {tmp.put(s.charAt(j), tmp.get(s.charAt(j)) - 1);if (tmp.get(s.charAt(j)) == 0) {tmp.remove(s.charAt(j));}}if (tmp.size() == 0) {if (j - i + 1 < minLen) {minLen = j - i + 1;left = i;right = j;}break;}}}return minLen == Integer.MAX_VALUE ? "" : s.substring(left, right + 1);}

版本2:(官方版本,能看懂,但自己写不出来😭)

class Solution {Map<Character, Integer> ori = new HashMap<Character, Integer>();Map<Character, Integer> cnt = new HashMap<Character, Integer>();public String minWindow(String s, String t) {int tLen = t.length();// 记录t出现字符集合for (int i = 0; i < tLen; i++) {char c = t.charAt(i);ori.put(c, ori.getOrDefault(c, 0) + 1);}// 定义左右指针int l = 0, r = -1;int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;int sLen = s.length();while (r < sLen) {++r;if (r < sLen && ori.containsKey(s.charAt(r))) {// 字符包含在t中的话,记录到另一个集合cnt中cnt.put(s.charAt(r), cnt.getOrDefault(s.charAt(r), 0) + 1);}while (check() && l <= r) {// 说明此子序列,包含了所有t中的字符if (r - l + 1 < len) {len = r - l + 1;ansL = l;ansR = l + len;}if (ori.containsKey(s.charAt(l))) {cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l), 0) - 1);}++l;}}return ansL == -1 ? "" : s.substring(ansL, ansR);}public boolean check() {// 检查 ori 是否包含了 所有的cnt种的字符,并且数量要小于cnt中的字符Iterator iter = ori.entrySet().iterator();while (iter.hasNext()) {Map.Entry entry = (Map.Entry) iter.next();Character key = (Character) entry.getKey();Integer val = (Integer) entry.getValue();if (cnt.getOrDefault(key, 0) < val) {return false;}}return true;}
}

image.png

面试公司

相关文章:

手撕算法-最小覆盖子串

描述 分析 滑动窗口。 参考力扣官方的题解思路 本问题要求我们返回字符串 s 中包含字符串 t 的全部字符的最小窗口。我们称包含 t 的全部字母的窗口为「可行」窗口。 我们可以用滑动窗口的思想解决这个问题。在滑动窗口类型的问题中都会有两个指针&#xff0c;一个用于「延伸…...

TrOCR—基于Transformer的OCR入门

导 读 本文主要介绍TrOCR&#xff1a;基于Transformer的OCR入门。 背景介绍 多年来&#xff0c;光学字符识别 (OCR) 出现了多项创新。它对零售、医疗保健、银行和许多其他行业的影响是巨大的。尽管有着悠久的历史和多种最先进的模型&#xff0c;研究人员仍在不断创新。与深…...

WIN使用LPD协议来共享打印机含统信UOS

打开“控制面板”&#xff0c;“程序和功能”&#xff0c;“启动或关闭Windows功能”&#xff0c;下拉找到“打印和文件服务”&#xff0c;勾选“LPD打印服务”和“LPR端口监视器”。确定之后重启电脑&#xff0c;共享主机和其它需要添加共享打印机的都开启功能和重启。 一、启…...

huawei 华为 交换机 配置 LACP 模式的链路聚合示例 (交换机之间直连)

组网需求 如 图 3-22 所示&#xff0c; SwitchA 和 SwitchB 通过以太链路分别都连接 VLAN10 和 VLAN20 的网络&#xff0c;且SwitchA 和 SwitchB 之间有较大的数据流量。用户希望 SwitchA 和 SwitchB 之间能够提供较大的链路带宽来使相同VLAN 间互相通信。在两台 Switch 设备上…...

c++ 有名对象和匿名对象

c 有名对象和匿名对象 有名对象就是有名字的对象&#xff0c;匿名对象就是没有名字的对象。 #define _CRT_SECURE_NO_WARNINGS 1 using namespace std; #include<iostream> class score { public:score(){math 100;chinese 100;english 100;}score(int _math, int _…...

day 36 贪心算法 part05● 435. 无重叠区间 ● 763.划分字母区间 ● 56. 合并区间

一遍过。首先把区间按左端点排序&#xff0c;然后右端点有两种情况。 假设是a区间&#xff0c;b区间。。。这样排列的顺序&#xff0c;那么 假设a[1]>b[0],如果a[1]>b[1]&#xff0c;就应该以b[1]为准&#xff0c;否则以a[1]为准。 class Solution { public:static bo…...

【数据结构与算法】快速排序(详解:快排的Hoare原版,挖坑法和双指针法|避免快排最坏时间复杂度的两种解决方案|小区间优化|非递归的快排)

引言 快速排序作为交换排序的一种&#xff0c;在排序界的影响力毋庸置疑&#xff0c;我们C语言中用的qsort&#xff0c;C中用的sort&#xff0c;底层的排序方式都是快速排序。相比于同为交换排序的冒泡&#xff0c;其效率和性能就要差的多了&#xff0c;本篇博客就是要重点介绍…...

三位数组合-第12届蓝桥杯选拔赛Python真题精选

[导读]&#xff1a;超平老师的Scratch蓝桥杯真题解读系列在推出之后&#xff0c;受到了广大老师和家长的好评&#xff0c;非常感谢各位的认可和厚爱。作为回馈&#xff0c;超平老师计划推出《Python蓝桥杯真题解析100讲》&#xff0c;这是解读系列的第42讲。 三位数组合&#…...

Mongodb入门到入土,安装到实战,外包半年学习的成果

这是我参与「第四届青训营 」笔记创作活动的的第27天&#xff0c;今天主要记录前端进阶必须掌握内容Mongodb数据库,从搭建环境到运行数据库,然后使用MongodB; 一、文章内容 数据库基础知识关系型数据库和非关系型数据库为什么学习Mongodb数据库环境搭建及运行MongodbMongodb命…...

【C++初阶】之类和对象(下)

【C初阶】之类和对象&#xff08;下&#xff09; ✍ 再谈构造函数&#x1f3c4; 初始化列表的引入&#x1f498; 初始化列表的语法&#x1f498; 初始化列表初始化元素的顺序 &#x1f3c4; explicit关键字 ✍ Static成员&#x1f3c4; C语言中的静态变量&#x1f3c4; C中的静…...

Spring Boot 3 极速搭建OAuth2认证框架

本篇环境 Java 17Spring Boot 3.2.3Spring Authorization Server 1.2.3开发工具 SpringToolSuite4Spring Boot 3.2.3 需要JDK 17及之上的版本。 项目初始化 项目可以使用Spring的初始化器生成, 也可以创建一个Maven类型的项目。 项目创建后的目录结构如下: 项目配置 使用 …...

大数据开发(离线实时音乐数仓)

大数据开发&#xff08;离线实时音乐数仓&#xff09; 一、数据库与ER建模1、数据库三范式2、ER实体关系模型 二、数据仓库与维度建模1、数据仓库&#xff08;Data Warehouse、DW、DWH&#xff09;1、关系型数据库很难将这些数据转换成企业真正需要的决策信息&#xff0c;原因如…...

Python读取csv文件入Oracle数据库

在Python中&#xff0c;使用pandas库的read_sql_query函数可以直接从SQL查询中读取数据到DataFrame。而pd.set_option函数用于设置pandas的显示选项。具体来说&#xff0c;display.unicode.ambiguous_as_wide选项用于控制当字符宽度不明确时&#xff0c;pandas是否将这些字符显…...

Linux_进程概念_冯诺依曼_进程概念_查看进程_获取进程pid_创建进程_进程状态_进程优先级_环境变量_获取环境变量三种方式_3

文章目录 一、硬件-冯诺依曼体系结构二、软件-操作系统-进程概念0.操作系统做什么的1.什么叫做进程2.查看进程3.系统接口 获取进程pid- getpid4.系统接口 获取父进程pid - getppid5.系统接口 创建子进程 - fork1、手册2、返回值3、fork做了什么4、基本用法 6.进程的状态1、进程…...

Set A Light 3D Studio中文--- 打造专业级3D照明效果

Set A Light 3D Studio是一款专业的灯光模拟软件&#xff0c;专为摄影师和电影制片人打造。它允许用户在计算机上模拟并预览各种布光效果&#xff0c;助力拍摄出真实、精准且具有艺术感的作品。软件提供了丰富的灯光和场景模型&#xff0c;用户可以灵活调整光源参数&#xff0c…...

【深度学习】基于机器学习的无机钙钛矿材料形成能预测,预测形成能,神经网络,回归问题

文章目录 任务分析数据处理处理离散数值处理缺失值处理不同范围的数据其他注意事项 我们的数据处理模型训练网页web代码、指导 任务分析 简单来说&#xff0c;就是一行就是一个样本&#xff0c;要用绿色的9个数值&#xff0c;预测出红色的那1个数值。 数据处理 在进行深度数…...

20240321-2-Adaboost 算法介绍

Adaboost 算法介绍 1. 集成学习 集成学习&#xff08;ensemble learning&#xff09;通过构建并结合多个学习器&#xff08;learner&#xff09;来完成学习任务&#xff0c;通常可获得比单一学习器更良好的泛化性能&#xff08;特别是在集成弱学习器&#xff08;weak learner…...

python第三方库的安装,卸载和更新,以及在cmd下pip install安装的包在pycharm不可用问题的解决

目录 第三方库pip安装&#xff0c;卸载更新 1.安装&#xff1a; 2.卸载 3.更新 一、第三方库pip安装&#xff0c;卸载更新 1.安装 pip install 模块名 加镜像下载&#xff1a;pip install -i 镜像网址模块名 常用的是加清华镜像&#xff0c;如 pip install -i https://pyp…...

Python第三次作业

周六 1. 求一个十进制的数值的二进制的0、1的个数 def er(x):a bin(x)b str(a).count("1")c str(a).count("0") - 1print(f"{a},count 1:{b},count 0:{c}")x int(input("enter a number:")) er(x) 2. 实现一个用户管理系统&…...

ai写作软件选哪个?这5款风靡全球的工具不容错过!

从去年到现在&#xff0c;ai 人工智能的发展一直是许多人关注的重点&#xff0c;每隔一段时间新诞生的 ai 工具软件&#xff0c;总会成为人们茶余饭后谈论的焦点。不过在种类繁多的 ai 工具软件中&#xff0c;ai 写作软件是最常被使用的 ai 工具类别&#xff0c;它的使用门槛较…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...

GO协程(Goroutine)问题总结

在使用Go语言来编写代码时&#xff0c;遇到的一些问题总结一下 [参考文档]&#xff1a;https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现&#xff1a; 今天在看到这个教程的时候&#xff0c;在自己的电…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...