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

算法练习题25——leetcode3279统计重新排列后包含另一个字符串的子字符串的数目(滑动窗口 双指针 哈希)

题目描述

解题思路

本题用到了滑动窗口 双指针 哈希

刚开始我是没读懂题的因为我笨

我想把我的思路说一下 左端不轻易缩小 只有找到跟word2匹配了 比如说abbcdd  遍历到c的时候才能匹配这个word2 对吧 那么之后加上以一个d或者俩d 都符合了 然后我们算完了 才能缩小左端 扩大右端

让left先不动 等字符频次和目标频次完全匹配后 right右边剩余的所有字符都可以加到结果字符串中作为符合的子字符串 然后再移动left

代码示例

class Solution {public long validSubstringCount(String word1, String word2) {int n = word1.length();int m = word2.length();// 统计 word2 的字符频次Map<Character, Integer> countWord2 = new HashMap<>();for (char c : word2.toCharArray()) {countWord2.put(c, countWord2.getOrDefault(c, 0) + 1);}// 滑动窗口的字符频次计数器Map<Character, Integer> countWindow = new HashMap<>();int left = 0;  // 窗口左边界long result = 0;int matched = 0;  // 记录匹配的字符数量// 开始滑动窗口的遍历for (int right = 0; right < n; right++) {// 扩展右端,加入当前字符char rightChar = word1.charAt(right);countWindow.put(rightChar, countWindow.getOrDefault(rightChar, 0) + 1);// 如果该字符在 word2 中存在,且它的频次也匹配了if (countWord2.containsKey(rightChar)) {if (countWindow.get(rightChar).equals(countWord2.get(rightChar))) {matched++;}}// 当窗口中的字符频次与 word2 完全匹配时while (matched == countWord2.size()) {// 计算从当前窗口到字符串末尾的所有合法子串result += (n - right);  // 从 right 到字符串末尾的所有子串都是合法的// 缩小左端,移除左边的字符char leftChar = word1.charAt(left);if (countWindow.get(leftChar) > 0) {countWindow.put(leftChar, countWindow.get(leftChar) - 1);}if (countWord2.containsKey(leftChar)) {if (countWindow.get(leftChar) < countWord2.get(leftChar)) {matched--;  // 如果频次不再匹配,匹配字符数减少}}left++;  // 左端收缩}}return result;}
}

相关文章:

算法练习题25——leetcode3279统计重新排列后包含另一个字符串的子字符串的数目(滑动窗口 双指针 哈希)

题目描述 解题思路 本题用到了滑动窗口 双指针 哈希 刚开始我是没读懂题的因为我笨 我想把我的思路说一下 左端不轻易缩小 只有找到跟word2匹配了 比如说abbcdd 遍历到c的时候才能匹配这个word2 对吧 那么之后加上以一个d或者俩d 都符合了 然后我们算完了 才能缩小左端 扩大…...

JavaEE: 深入探索TCP网络编程的奇妙世界(二)

文章目录 TCP核心机制TCP核心机制二: 超时重传为啥会丢包?TCP如何对抗丢包?超时重传的时间设定超时时间该如何确定? TCP核心机制 前一篇文章 JavaEE: 深入探索TCP网络编程的奇妙世界(一) 书接上文~ TCP核心机制二: 超时重传 在网络传输中,并不会一帆风顺,而是可能出现&qu…...

GPT1-GPT3论文理解

GPT&#xff11;&#xff0d;GPT&#xff13;论文理解 视频参考&#xff1a;https://www.bilibili.com/video/BV1AF411b7xQ/?spm_id_from333.788&vd_sourcecdb0bc0dda1dccea0b8dc91485ef3e74 1 历史 2017.6 Transformer 2018.6 GPT 2018.10 BERT 2019.2 GPT-2 2020…...

C/C++内存管理 ——

目录 五、C/C内存管理 1、C/C内存分布 2、C语言中动态内存管理方式&#xff1a;malloc/calloc/realloc/free 3、C内存管理方式 1.new/delete操作内置类型 2.new和delete操作自定义类型 4、operator new与operator delete函数 5、new和delete的实现原理 1.内置类…...

深度学习02-pytorch-04-张量的运算函数

在 PyTorch 中&#xff0c;张量&#xff08;tensor&#xff09;运算是核心操作之一&#xff0c;PyTorch 提供了丰富的函数来进行张量运算&#xff0c;包括数学运算、线性代数、索引操作等。以下是常见的张量运算函数及其用途&#xff1a; 1. 基本数学运算 加法运算&#xff1a…...

OpenHarmony(鸿蒙南向开发)——小型系统内核(LiteOS-A)【文件系统】上

往期知识点记录&#xff1a; 鸿蒙&#xff08;HarmonyOS&#xff09;应用层开发&#xff08;北向&#xff09;知识点汇总 鸿蒙&#xff08;OpenHarmony&#xff09;南向开发保姆级知识点汇总~ 子系统开发内核 轻量系统内核&#xff08;LiteOS-M&#xff09; 轻量系统内核&#…...

NISP 一级 | 8.4 《网络安全法》

关注这个证书的其他相关笔记&#xff1a;NISP 一级 —— 考证笔记合集-CSDN博客 2017 年 6 月 1 日&#xff0c;《中华人民共和国网终安全法》&#xff08;以下简称《网终安全法》&#xff09;正式实施。这是我国第一部全面规范网络空间安全管理方面问题的基础性法律&#xff0…...

实现人体模型可点击

简化需求&#xff1a;实现项目内嵌人体模型&#xff0c;实现点击不同部位弹出部位名称 一&#xff1a;优先3d&#xff0c; 方案&#xff1a;基于three.js&#xff0c;.gltf格式模型&#xff0c;vue3 缺点&#xff1a;合适且免费的3d模型找不到&#xff0c;因为项目对部位有要…...

C++ | Leetcode C++题解之第429题N叉树的层序遍历

题目&#xff1a; 题解&#xff1a; class Solution { public:vector<vector<int>> levelOrder(Node* root) {if (!root) {return {};}vector<vector<int>> ans;queue<Node*> q;q.push(root);while (!q.empty()) {int cnt q.size();vector<…...

Pandas简介

Pandas 是一个流行的开源数据分析库&#xff0c;它是基于 NumPy 构建的&#xff0c;为 Python 编程语言提供了高性能、易用的数据结构和数据分析工具。Pandas 主要用于数据清洗、数据转换、数据分析等任务&#xff0c;使得数据处理工作变得更加高效和便捷。 Pandas 的两个主要…...

Python | Leetcode Python题解之第430题扁平化多级双向链表

题目&#xff1a; 题解&#xff1a; class Solution:def flatten(self, head: "Node") -> "Node":def dfs(node: "Node") -> "Node":cur node# 记录链表的最后一个节点last Nonewhile cur:nxt cur.next# 如果有子节点&#…...

机器人机构、制造

简单整理一下&#xff0c;在学习了一些运动学和动力学之类的东西&#xff0c;简单的整合了一些常用的机械结构和图片。 1.电机&#xff1a; 市面上的电机有&#xff1a;直流电机&#xff0c;交流电机&#xff0c;舵机&#xff0c;步进电机&#xff0c;电缸&#xff0c;无刷电…...

《拿下奇怪的前端报错》:nvm不可用报错`GLIBC_2.27‘‘GLIBCXX_3.4.20‘not Found?+ 使用docker构建多个前端项目实践

有些前端的小伙伴可能会好奇&#xff0c;nvm是什么&#xff1f;这里接简单介绍下&#xff0c;它是一个Nodejs版本管理工具。为什么需要它呢&#xff1f;当然是需要多个Nodejs版本的时候&#xff0c;那什么时候需要多个Nodejs版本&#xff1f;那肯定是在有点年头的公司了&#x…...

5.《DevOps》系列K8S部署CICD流水线之K8S通过Yaml部署GitLab

架构 服务器IP服务名称硬件配置192.168.1.100k8s-master8核、16G、120G192.168.1.101k8s-node18核、16G、120G192.168.1.102k8s-node28核、16G、120G192.168.1.103nfs2核、4G、500G操作系统:Rocky9.3 后续通过K8S部署Jenkins NFS的SC创建参考:2.《DevOps》系列K8S部署CICD流…...

[SAP ABAP] 创建数据库视图和维护视图

数据准备 学校表(ZDBT_SCH_437) 学生表(ZDBT_STU_437) 学校表(ZDBT_SCH_437)与学生表(ZDBT_STU_437)字段 学校表(ZDBT_SCH_437)与学生表(ZDBT_STU_437)行数据明细 1.创建数据库视图 使用SE11创建数据库视图 填写视图名称ZV_DATABASEV_437&#xff0c;点击创建按钮 选择数据库视…...

【最快最简单的排序 —— 桶排序算法】

最快最简单的排序 —— 桶排序算法 桶排序是一种排序算法&#xff0c;其工作原理是将数据分到有限数量的桶子里&#xff0c;然后对每个桶内的元素进行单独排序&#xff0c;最后依次把各个桶中的记录列出来。桶排序的效率取决于映射函数的选择和桶的数量。 桶排序适用于数据分…...

AI时代,服务器厂商能否打破薄利的命运?

文&#xff5c;刘俊宏 编&#xff5c;王一粟 AI大模型正在引发新一轮的“算力焦渴”。 近日&#xff0c;OpenAI刚发布的o1大模型再次刷新了大模型能力的上限。对比上一次迭代的版本&#xff0c;o1的推理能力全方位“吊打”了GPT-4o。更优秀的能力&#xff0c;来自与o1将思维…...

2024年9月python二级易错题和难题大全(附详细解析)(二)

2024年9月python二级易错题和难题大全(附详细解析)(二) 第1题第2题第3题第4题第5题第6题第7题第8题第9题第10题第11题第12题第13题第14题第15题第16题第17题第18题第19题第20题第1题 1、以下代码的输出结果是() x = 12 + 3 * ((5 * 8) - 14) // 6 print(x) A、25.0 B、6…...

4.结构型设计模式 - 第1回:引言与适配器模式 (Adapter Pattern) ——设计模式入门系列

一、引言 在现代软件开发中&#xff0c;设计模式是帮助我们解决复杂问题的工具&#xff0c;它们提供了在常见场景下重用已验证解决方案的途径。而结构型设计模式主要关注类与对象之间的组合方式&#xff0c;旨在通过增强灵活性和降低耦合度来改进代码的结构。 本次讨论的是结…...

解决mybatis plus 中 FastjsonTypeHandler无法正确反序列化List类型的问题

由于是根据自动映射类型&#xff0c;我们设置的字段类型是List 也就是反序列化的时候也只是用 FastjsonTypeHandler中的 Override protected Object parse(String json) { return JSON.parseObject(json, type); } 反序列化方法&#xff0c;这是type为List 反序列后我们并没…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

云原生安全实战:API网关Kong的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关&#xff08;API Gateway&#xff09; API网关是微服务架构中的核心组件&#xff0c;负责统一管理所有API的流量入口。它像一座…...

uniapp 字符包含的相关方法

在uniapp中&#xff0c;如果你想检查一个字符串是否包含另一个子字符串&#xff0c;你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的&#xff0c;但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...

Chrome 浏览器前端与客户端双向通信实战

Chrome 前端&#xff08;即页面 JS / Web UI&#xff09;与客户端&#xff08;C 后端&#xff09;的交互机制&#xff0c;是 Chromium 架构中非常核心的一环。下面我将按常见场景&#xff0c;从通道、流程、技术栈几个角度做一套完整的分析&#xff0c;特别适合你这种在分析和改…...

Kafka主题运维全指南:从基础配置到故障处理

#作者&#xff1a;张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1&#xff1a;主题删除失败。常见错误2&#xff1a;__consumer_offsets占用太多的磁盘。 主题日常管理 …...

ArcGIS Pro+ArcGIS给你的地图加上北回归线!

今天来看ArcGIS Pro和ArcGIS中如何给制作的中国地图或者其他大范围地图加上北回归线。 我们将在ArcGIS Pro和ArcGIS中一同介绍。 1 ArcGIS Pro中设置北回归线 1、在ArcGIS Pro中初步设置好经纬格网等&#xff0c;设置经线、纬线都以10间隔显示。 2、需要插入背会归线&#xf…...