力扣-最小覆盖子串

ops/2024/10/30 14:14:15/

76. 最小覆盖子串 - 力扣(LeetCode)

给定一个字符串s,和目标字符串t,需要找出s中包含t中所有字符且长度最小子串,输出这个子串

滑动窗口,初始时左右指针都指向s的第一个字符,对于每个遍历到的窗口,判断当前窗口是否包含了t中所需要的所有字符,不是的话就移动右指针,是的话就移动左指针。

怎么判断当前窗口是否包含了t中所需要的字符?

可以定义一个distance这样的int变量,当移动右指针后,如果此时右指针指向的字符在当前窗口中的个数严格小于t中所需要的个数,那么distance++。

在移动左指针前,如果此时左指针指向的字符在当前窗口中的个数等于t中所需要的个数,那么distance--。

distance等于t中所含字符数量时,就说明当前窗口是一个符合条件的子串

class Solution {public String minWindow(String s, String t) {int ans=1000000;String ansString="";int [] target=new int[200];int [] window=new int[200];int ansCount=0;for (int i = 0; i <t.length() ; i++) {target[t.charAt(i)]++;ansCount++;}int distance=0;for (int l=0,r=0; r <s.length() ; r++) {char x =s.charAt(r);if(window[x]<target[x]){distance++;}window[x]++;int f=0;while(distance==ansCount){f=1;
//                if(ans>r-l+1){
//                    ans =r-l+1;
//                    ansString=s.substring(l,r+1);
//                }if( window[s.charAt(l)]==target[s.charAt(l)]){distance--;}window[s.charAt(l)]--;l++;}//出循环说明distance不满足anscount了if(f==1&&ans>r-l+2){f=0;ans =r-l+2;ansString=s.substring(l-1,r+1);}}return ansString;}
}


http://www.ppmy.cn/ops/129600.html

相关文章

结合无监督表示学习与伪标签监督的自蒸馏方法,用于稀有疾病影像表型分类的分散感知失衡校正|文献速递-基于生成模型的数据增强与疾病监测应用

Title 题目 Hybrid unsupervised representation learning and pseudo-label supervisedself-distillation for rare disease imaging phenotype classification with dispersion-aware imbalance correction 结合无监督表示学习与伪标签监督的自蒸馏方法&#xff0c;用于稀…

UML外卖系统报告(包含具体需求分析)

1 系统背景 随着互联网技术的快速发展&#xff0c;外卖订餐服务逐渐成为人们生活中的一部分。传统的电话订餐方式面临诸多不便和限制&#xff0c;而基于互联网的外卖订餐系统则提供了更加便捷、快速和高效的订餐服务。这种系统通过将餐厅、顾客和配送人员连接起来&#xff0c;…

SpringBoot 下的Excel文件损坏与内容乱码问题

序言 随着打包部署的方式的改变&#xff0c;原本正常运行的代码可能带来一些新的问题&#xff0c;比如我们现在使用SpringBoot 的方式生成Jar包直接运行&#xff0c;就会对我们再在Resource下的Excel文件产生影响&#xff0c;导入与预期不符的情况发生cuiyaonan2000163.com 比…

Xcode 16.1 (16B40) 发布下载 - Apple 平台 IDE

Xcode 16.1 (16B40) 发布下载 - Apple 平台 IDE IDE for iOS/iPadOS/macOS/watchOS/tvOS/visonOS 发布日期&#xff1a;2024 年 10 月 28 日 Xcode 16.1 包含适用于 iOS 18.1、iPadOS 18.1、Apple tvOS 18.1、watchOS 11.1、macOS Sequoia 15.1 和 visionOS 2.1 的 SDK。Xco…

Zookeeper 理论基础

简介 ZooKeeper 由雅虎研究院开发&#xff0c;后来捐赠给了 Apache。ZooKeeper 是一个开源的分布式应用程序协调服务器&#xff0c;其为分布式系统提供一致性服务。其一致性是通过基于 Paxos 算法的ZAB 协议完成的。其主要功能包括&#xff1a;配置维护、域名服务、分布式同步、…

CSS 样式 box-sizing: border-box; 用于控制元素的盒模型如何计算宽度和高度

文章目录 box-sizing: border-box; 的含义默认盒模型 (content-box)border-box 盒模型 在微信小程序中的应用示例 在微信小程序中&#xff0c;CSS 样式 box-sizing: border-box; 用于控制元素的盒模型如何计算宽度和高度。具体来说&#xff0c; box-sizing: border-box; 会改…

使用VS2019将C#代码生成DLL文件在Unity3D里面使用(二)

系列文章目录 unity知识点 文章目录 系列文章目录&#x1f449;前言&#x1f449;一、导入文件&#x1f449;二、代码编写&#x1f449;壁纸分享&#x1f449;总结 &#x1f449;前言 使用VS2019将C#代码生成DLL文件在Unity3D里面使用&#xff08;一&#xff09; 上一篇写了怎…

2024前端面试训练计划-高频题-Vue基础篇

具体内容结构&#xff08;可作为回答思路&#xff09;为&#xff1a;简略回答&#xff0c;详细回答 1、vue响应式 简略回答 Vue 2 响应式原理 数据劫持&#xff08;Object.defineProperty&#xff09; Vue 2 使用Object.defineProperty()来实现数据劫持。它会遍历数据对象的…