当前位置: 首页 > 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…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

STM32HAL库USART源代码解析及应用

STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...

iview框架主题色的应用

1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题&#xff0c;无需引入&#xff0c;直接可…...

Ubuntu系统复制(U盘-电脑硬盘)

所需环境 电脑自带硬盘&#xff1a;1块 (1T) U盘1&#xff1a;Ubuntu系统引导盘&#xff08;用于“U盘2”复制到“电脑自带硬盘”&#xff09; U盘2&#xff1a;Ubuntu系统盘&#xff08;1T&#xff0c;用于被复制&#xff09; &#xff01;&#xff01;&#xff01;建议“电脑…...

云原生周刊:k0s 成为 CNCF 沙箱项目

开源项目推荐 HAMi HAMi&#xff08;原名 k8s‑vGPU‑scheduler&#xff09;是一款 CNCF Sandbox 级别的开源 K8s 中间件&#xff0c;通过虚拟化 GPU/NPU 等异构设备并支持内存、计算核心时间片隔离及共享调度&#xff0c;为容器提供统一接口&#xff0c;实现细粒度资源配额…...

32单片机——基本定时器

STM32F103有众多的定时器&#xff0c;其中包括2个基本定时器&#xff08;TIM6和TIM7&#xff09;、4个通用定时器&#xff08;TIM2~TIM5&#xff09;、2个高级控制定时器&#xff08;TIM1和TIM8&#xff09;&#xff0c;这些定时器彼此完全独立&#xff0c;不共享任何资源 1、定…...

Python环境安装与虚拟环境配置详解

本文档旨在为Python开发者提供一站式的环境安装与虚拟环境配置指南&#xff0c;适用于Windows、macOS和Linux系统。无论你是初学者还是有经验的开发者&#xff0c;都能在此找到适合自己的环境搭建方法和常见问题的解决方案。 快速开始 一分钟快速安装与虚拟环境配置 # macOS/…...

OpenHarmony标准系统-HDF框架之I2C驱动开发

文章目录 引言I2C基础知识概念和特性协议&#xff0c;四种信号组合 I2C调试手段硬件软件 HDF框架下的I2C设备驱动案例描述驱动Dispatch驱动读写 总结 引言 I2C基础知识 概念和特性 集成电路总线&#xff0c;由串网12C(1C、12C、Inter-Integrated Circuit BUS)行数据线SDA和串…...

第6章:Neo4j数据导入与导出

在实际应用中&#xff0c;数据的导入与导出是使用Neo4j的重要环节。无论是初始数据加载、系统迁移还是数据备份&#xff0c;都需要高效可靠的数据传输机制。本章将详细介绍Neo4j中的各种数据导入与导出方法&#xff0c;帮助读者掌握不同场景下的最佳实践。 6.1 数据导入策略 …...

【基于阿里云搭建数据仓库(离线)】使用UDTF时出现报错“FlatEventUDTF cannot be resolved”

目录 问题&#xff1a; 可能的原因有&#xff1a; 解决方法&#xff1a; 问题&#xff1a; 已经将包含第三方依赖的jar包上传到dataworks&#xff0c;并且成功注册函数&#xff0c;但是还是报错&#xff1a;“FlatEventUDTF cannot be resolved”&#xff0c;如下&#xff1a…...