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

【Hot100】LeetCode—76. 最小覆盖子串

题目

  • 原题链接:76. 最小覆盖子串

1- 思路

利用两个哈希表解决分为 :① 初始化哈希表②遍历 s,处理当前元素,判断当前字符是否有效③收缩窗口④更新最小覆盖子串


2- 实现

⭐76. 最小覆盖子串——题解思路

在这里插入图片描述

class Solution {public String minWindow(String s, String t) {// 定义两个 HashMapHashMap<Character,Integer> hs = new HashMap<>();HashMap<Character,Integer> ht = new HashMap<>();// 定义 int cnt = 0;String res = "";// 初始化 htfor(int i = 0 ; i < t.length();i++){char c = t.charAt(i);ht.put(c,ht.containsKey(c) ? ht.get(c)+1:1);}// 遍历 sfor(int i = 0, j = 0 ; i < s.length();i++){char c = s.charAt(i);hs.put(c, hs.containsKey(c) ? hs.get(c)+1 : 1);// 判断 i 合法if(ht.containsKey(c) && hs.get(c) <= ht.get(c)) cnt++;// 缩小区间while (j <= i && (!ht.containsKey(s.charAt(j)) || hs.get(s.charAt(j)) > ht.get(s.charAt(j)))) {hs.put(s.charAt(j), hs.get(s.charAt(j ++)) - 1);}// 3 收集结果// 首先是必须等于 cnt && (hs.length()> (i-j+1) || res.length()<1)if(cnt==t.length() && ( res.length() > (i-j+1) || res.length()<1)){res = s.substring(j,i+1);}}return res;}
}

3- ACM 实现

public class minWindow {public static String minWindow(String s,String t){// 1.数据结构HashMap<Character,Integer> ht = new HashMap<>();HashMap<Character,Integer> window = new HashMap<>();int cnt = 0;String res = "";// 2.遍历 t 初始化 htfor(int i = 0 ; i < t.length();i++){char c = t.charAt(i);ht.put(c,ht.containsKey(c)? ht.get(c)+1:1);}// 3.遍历 sfor(int i = 0,j=0 ; i < s.length();i++){char cc = s.charAt(i);window.put(cc,window.containsKey(cc)? window.get(cc)+1:1);// 判 cc 断有效性// 在 ht 中if(ht.containsKey(cc) && window.get(cc) <=ht.get(cc)) cnt++;// 窗口收缩while(j<=i && (!ht.containsKey(s.charAt(j)) || window.get(s.charAt(j)) > ht.get(s.charAt(j)))){window.put(s.charAt(j),window.get(s.charAt(j++))-1);}// 更行 resif(cnt == t.length() && (res.length()>(i-j+1) || res.length()<1)){res = s.substring(j,i+1);}}return res;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("输入字符串1");String s = sc.nextLine();System.out.println("输入字符串2");String t = sc.nextLine();String res = minWindow(s,t);System.out.println("结果是"+ res);}
}

相关文章:

【Hot100】LeetCode—76. 最小覆盖子串

题目 原题链接&#xff1a;76. 最小覆盖子串 1- 思路 利用两个哈希表解决分为 &#xff1a;① 初始化哈希表、②遍历 s&#xff0c;处理当前元素&#xff0c;判断当前字符是否有效、③收缩窗口、④更新最小覆盖子串 2- 实现 ⭐76. 最小覆盖子串——题解思路 class Solution …...

删除排序链表中的重复元素 II(LeetCode)

题目 给定一个已排序的链表的头 head &#xff0c; 删除原始链表中所有重复数字的节点&#xff0c;只留下不同的数字 。返回 已排序的链表 。 解题 class ListNode:def __init__(self, val0, nextNone):self.val valself.next nextclass Solution:def deleteDuplicates(self…...

【Java】解决如何将Http转为Https加密输出

目录 HTTP转HTTPS一、 获取 SSL/TLS 证书二、 安装证书2.1 Apache2.2 Nginx 三、更新网站配置四. 更新网站链接五. 检查并测试六. 自动续期&#xff08;针对 Lets Encrypt&#xff09; HTTP转HTTPS 将网站从 HTTP 转换为 HTTPS 能够加密数据传输&#xff0c;还能提高搜索引擎排…...

二叉树链式结构的实现(递归的暴力美学!!)

前言 Hello,小伙伴们。你们的作者菌又回来了&#xff0c;前些时间我们刚学习完二叉树的顺序结构&#xff0c;今天我们就趁热打铁&#xff0c;继续我们二叉树链式结构的学习。我们上期有提到&#xff0c;二叉树的的底层结构可以选为数组和链表&#xff0c;顺序结构我们选用的数…...

Python | Leetcode Python题解之第312题戳气球

题目&#xff1a; 题解&#xff1a; class Solution:def maxCoins(self, nums: List[int]) -> int:n len(nums)rec [[0] * (n 2) for _ in range(n 2)]val [1] nums [1]for i in range(n - 1, -1, -1):for j in range(i 2, n 2):for k in range(i 1, j):total v…...

远程访问mysql数据库的正确打开方式

为了安全&#xff0c;mysql数据库默认只能本机登录&#xff0c;但是在有些时候&#xff0c;我们会有远程登录mysql数据库的需求&#xff0c;这时候应该怎么办呢&#xff1f; 远程访问mysql数据&#xff0c;需要两个条件&#xff1a; 首先需要mysql服务器将服务绑定到0.0.0.0…...

网络6 -- udp_socket 实现 echo服务器

目录 1.server 服务端 1.1.完整代码展示&#xff1a; 1.2.代码解析&#xff1a; 1.2.1 给服务端创建套接字 1.2.2 绑定套接字 1.2.3 服务端接受数据并返回 2.客户端&#xff1a; 2.1 完整代码展示&#xff1a; 2.2 代码解析 2.2.1 客户端使用手则&#xff1a; 2.2.2 …...

ASUS/华硕幻15 2020 冰刃4 GX502L GU502L系列 原厂win10系统 工厂文件 带F12 ASUS Recovery恢复

华硕工厂文件恢复系统 &#xff0c;安装结束后带隐藏分区&#xff0c;一键恢复&#xff0c;以及机器所有驱动软件。 系统版本&#xff1a;windows10 原厂系统下载网址&#xff1a;http://www.bioxt.cn 需准备一个20G以上u盘进行恢复 请注意&#xff1a;仅支持以上型号专用…...

simulink绘制bode图

&#x1f3c6;本文收录于《CSDN问答解惑-专业版》专栏&#xff0c;主要记录项目实战过程中的Bug之前因后果及提供真实有效的解决方案&#xff0c;希望能够助你一臂之力&#xff0c;帮你早日登顶实现财富自由&#x1f680;&#xff1b;同时&#xff0c;欢迎大家关注&&收…...

知识工程视角下的软件研发

知识工程 在我们的工作中存在两类知识&#xff1a;显式知识&#xff08;explicit knowledge&#xff09;、不可言说的知识&#xff08;tacit knowledge&#xff09;。 所谓显式知识就是能够直接表达且在人群中分享的知识。比如&#xff0c;地球的周长、水的密度、三角形面积公…...

深度学习------权重衰退

目录 使用均方范数作为硬性限制使用均方范数作为柔性限制演示最优解的影响参数更新法则总结高纬线性回归多项式的权重衰退从零开始实现初始化模型参数定义L2范数惩罚定义训练代码实现忽略正则化直接训练使用权重衰减从零开始代码实现 多项式的权重衰退的简洁实现简洁函数代码简…...

【算法】退火算法 Simulated Annealing

退火算法&#xff08;Simulated Annealing, SA&#xff09;是一种基于热力学模拟的优化算法&#xff0c;用于求解全局优化问题。它通过模拟物理退火过程来寻找全局最优解。以下是退火算法的基本原理和步骤&#xff1a; 一、基本原理 退火算法的灵感来源于金属在高温下缓慢冷却…...

深入理解 Git `git add -p` 命令中的交互选项

个人名片 🎓作者简介:java领域优质创作者 🌐个人主页:码农阿豪 📞工作室:新空间代码工作室(提供各种软件服务) 💌个人邮箱:[2435024119@qq.com] 📱个人微信:15279484656 🌐个人导航网站:www.forff.top 💡座右铭:总有人要赢。为什么不能是我呢? 专栏导…...

HTML JavaScript 闪光涟漪

<!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>闪光涟漪</title><style>.ripple-conta…...

FastAPI之Depends

文章目录 基本概念基本用法复杂场景中的 Depends数据库会话管理处理请求用户嵌套依赖全局依赖 作用域与生命周期可选依赖类依赖总结 基本概念 在 FastAPI 中&#xff0c;依赖可以是&#xff1a; 一个函数&#xff0c;它的返回值会被传递给视图函数作为参数。可以被其他依赖函…...

AttributeError: module ‘jwt‘ has no attribute ‘decode‘解决方案

大家好,我是爱编程的喵喵。双985硕士毕业,现担任全栈工程师一职,热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。现为CSDN博客专家、人工智能领域优质创作者。喜欢通过博客创作的方式对所学的…...

C++——C++11

前言&#xff1a;本篇文章将分享一些C11版本所产生的一些新的技术以及对老版本的优化。 目录 一.C11简介 二.统一的列表初始化 1.{}初始化 2.std::initializer_list 三.右值引用和移动语义 1.左值引用和右值引用 2.两者的比较 &#xff08;1&#xff09;左值引用 &#…...

day12 多线程

目录 1.概念相关 1.1什么是线程 1.2什么是多线程 2.创建线程 2.1方式一&#xff1a;继承Thread类 2.1.1实现步骤 2.1.2优缺点 2.1.3注意事项 2.2方式二&#xff1a;实现Runnable接口 2.2.1实现步骤 2.2.2优缺点 2.2.3匿名内部类写法 2.3方式三&#xff1a;实现cal…...

DeferredResult 是如何实现异步处理请求的

最近遇到了一个问题&#xff0c;我们的一个接口需要去轮询另一个第三方接口&#xff0c;导致这个接口占用了太多工作线程&#xff0c;这些工作线程长时间 running&#xff0c;我们需要解决这个问题。 于是&#xff0c;我们的方案是&#xff1a;用 DeferredResult 实现接口异步。…...

VUE3——001(03)、开发环境配置(node.js/mvn/java/ngix/tomact/vue3)

嫌麻烦的请下载安装包&#xff0c;有点强迫&#xff08;懒的&#xff09;可以看看。 解释&#xff1a;安装目录&#xff0c;即软件安装所在目录&#xff0c;如 node.js 我装在 D:\AppFolder\nodejs 系统变量修改 path增加 安装目录 在系统变量 p…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...