Leetcode JAVA刷刷站(76)最小覆盖子串

2024-08-23 06:04

本文主要是介绍Leetcode JAVA刷刷站(76)最小覆盖子串,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 一、题目概述

二、思路方向 

       为了解决这个问题,我们可以使用滑动窗口的方法。滑动窗口是数组/字符串问题中常用的一个技巧,特别是用于寻找子数组或子字符串的问题。

       这里的关键是,我们需要知道字符串t中每个字符的出现次数,并在遍历字符串s时维护一个窗口,这个窗口内的字符种类和数量需要能够“覆盖”字符串t中的所有字符。

以下是用Java实现的详细步骤:

  1. 初始化:使用HashMap来记录字符串t中每个字符的出现次数(need),并同时统计t中不同字符的总数(required)。

  2. 双指针滑动窗口:使用两个指针leftright来维护一个滑动窗口,其中right指针用于扩展窗口,left指针用于缩小窗口。

  3. 窗口内字符的计数:使用一个HashMap(例如window)来记录当前窗口内每个字符的出现次数。

  4. 移动right指针:扩展窗口,每次移动right指针时,增加window[s[right]]的计数。

  5. 检查窗口:如果窗口内的字符种类和数量能够覆盖t中的字符,则尝试缩小窗口(移动left指针),直到窗口不再满足覆盖条件或达到最小。

  6. 更新结果:在每次满足覆盖条件时,比较并更新最小子串的起始位置和长度。

  7. 返回结果:如果找到了满足条件的子串,则返回该子串;否则,返回空字符串。

三、代码实现  

import java.util.HashMap;  
import java.util.Map;  public class Solution {  public String minWindow(String s, String t) {  Map<Character, Integer> need = new HashMap<>();  Map<Character, Integer> window = new HashMap<>();  // 统计t中每个字符的出现次数  for (char c : t.toCharArray()) {  need.put(c, need.getOrDefault(c, 0) + 1);  }  int left = 0, right = 0;  int required = need.size(); // t中不同字符的总数  int[] result = {-1, 0, 0}; // {起始索引, 子串长度, 0(占位符)}  while (right < s.length()) {  // c 是将移入窗口的字符  char c = s.charAt(right);  // 扩大窗口  if (need.containsKey(c)) {  window.put(c, window.getOrDefault(c, 0) + 1);  if (window.get(c).equals(need.get(c))) {  required--;  }  }  right++;  // 尝试缩小窗口  while (required == 0) {  // 在这里更新最小覆盖子串  if (result[1] == 0 || right - left < result[1]) {  result[0] = left;  result[1] = right - left;  }  // d 是将移出窗口的字符  char d = s.charAt(left);  // 缩小窗口  if (need.containsKey(d)) {  if (window.get(d).equals(need.get(d))) {  required++;  }  window.put(d, window.get(d) - 1);  }  left++;  }  }  // 根据result数组构建最小覆盖子串  return result[1] == 0 ? "" : s.substring(result[0], result[0] + result[1]);  }  public static void main(String[] args) {  Solution solution = new Solution();  String s = "ADOBECODEBANC";  String t = "ABC";  System.out.println(solution.minWindow(s, t)); // "BANC"  }  
}

执行结果: 

四、小结

       这段代码首先通过两个HashMap来记录需要匹配的字符和当前窗口中的字符,然后通过双指针来维护一个滑动窗口,不断尝试缩小窗口直到不满足条件,并在过程中记录最小覆盖子串。

 结语  

好的事情总是发生在最后

当你觉得不能接受的时候

它却来到了身边

!!!

这篇关于Leetcode JAVA刷刷站(76)最小覆盖子串的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1098550

相关文章

Java编译生成多个.class文件的原理和作用

《Java编译生成多个.class文件的原理和作用》作为一名经验丰富的开发者,在Java项目中执行编译后,可能会发现一个.java源文件有时会产生多个.class文件,从技术实现层面详细剖析这一现象... 目录一、内部类机制与.class文件生成成员内部类(常规内部类)局部内部类(方法内部类)匿名内部类二、

SpringBoot实现数据库读写分离的3种方法小结

《SpringBoot实现数据库读写分离的3种方法小结》为了提高系统的读写性能和可用性,读写分离是一种经典的数据库架构模式,在SpringBoot应用中,有多种方式可以实现数据库读写分离,本文将介绍三... 目录一、数据库读写分离概述二、方案一:基于AbstractRoutingDataSource实现动态

Springboot @Autowired和@Resource的区别解析

《Springboot@Autowired和@Resource的区别解析》@Resource是JDK提供的注解,只是Spring在实现上提供了这个注解的功能支持,本文给大家介绍Springboot@... 目录【一】定义【1】@Autowired【2】@Resource【二】区别【1】包含的属性不同【2】@

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co

Elasticsearch 在 Java 中的使用教程

《Elasticsearch在Java中的使用教程》Elasticsearch是一个分布式搜索和分析引擎,基于ApacheLucene构建,能够实现实时数据的存储、搜索、和分析,它广泛应用于全文... 目录1. Elasticsearch 简介2. 环境准备2.1 安装 Elasticsearch2.2 J

Java中的String.valueOf()和toString()方法区别小结

《Java中的String.valueOf()和toString()方法区别小结》字符串操作是开发者日常编程任务中不可或缺的一部分,转换为字符串是一种常见需求,其中最常见的就是String.value... 目录String.valueOf()方法方法定义方法实现使用示例使用场景toString()方法方法

Java中List的contains()方法的使用小结

《Java中List的contains()方法的使用小结》List的contains()方法用于检查列表中是否包含指定的元素,借助equals()方法进行判断,下面就来介绍Java中List的c... 目录详细展开1. 方法签名2. 工作原理3. 使用示例4. 注意事项总结结论:List 的 contain

Java实现文件图片的预览和下载功能

《Java实现文件图片的预览和下载功能》这篇文章主要为大家详细介绍了如何使用Java实现文件图片的预览和下载功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... Java实现文件(图片)的预览和下载 @ApiOperation("访问文件") @GetMapping("

Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

《SpringBoot+MyBatisPlus高效开发实战从入门到进阶优化(推荐)》本文将详细介绍SpringBoot+MyBatisPlus的完整开发流程,并深入剖析分页查询、批量操作、动... 目录Spring Boot + MyBATis Plus 高效开发实战:从入门到进阶优化1. MyBatis