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

【专题刷题】滑动窗口（四）：

news 来源：原创 2025/7/5 13:21:51

📝前言说明：

本专栏主要记录本人的基础算法学习以及LeetCode刷题记录，按专题划分
每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）
文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页愚润泽

视频

30. 串联所有单词的子串
- 个人解
- 优质解：
LCR 017. 最小覆盖子串
- 个人解

30. 串联所有单词的子串

在这里插入图片描述

个人解

思路（实在写不出了，记录错误想法）：
怎么判断当前子串能不能words的单词串联起来（我的想法是利用哈希表，类似第 438. 找异位词）

把word当一个整体，记录words的哈希表
用哈希表记录子串的单词的出现次数
每次 right 和 left 移动的是一个单词的长度，每次改变首尾两个单词在哈希表中的值

用时：30:00
屎山代码（通过了一半用例）：

class Solution {bool is_connect(unordered_map<string, int> wordsmap, unordered_map<string, int> smap){for(auto x: wordsmap){if(x.second != smap[x.first]){return false;}}return true;}
public:vector<int> findSubstring(string s, vector<string>& words) {unordered_map<string, int> wordsmap, smap;for(auto x : words) // 获取words的哈希表{wordsmap[x]++;}int m = words[0].size(), n1 = s.size(), n2 = words.size();vector<int> ans;for(int right = m, left = 0; right <= n1; right += m){string in(s.begin() + right - m, s.begin() + right);smap[in]++; // 进窗口if(right - left > n2 * m){string out(s.begin() + left, s.begin() + left + m);smap[out]--; // 出窗口left += m;}if(right - left == n2 * m && is_connect(wordsmap, smap)){ans.push_back(left);}}return ans;}
};

优质解：

思路：
我的大体思路还是正确的，滑动窗口 + 哈希表
但是问题出在：
在这里插入图片描述
我只考虑了紫色线的这种划分，却没有考虑到还可以以绿色线的这种方式划分，以此类推。

因此，滑动窗口要以不同起点开始执行多次，执行的次数是：单个word的长度

这里还有一手很妙的比较smap和wordsmap两个哈希表是否相等的方法：
在遍历s的时候，用一个count记录有效单词的个数，有效单词指：当往smap中加入某一单词后，此时smap中该单词的个数 <= wordsmap里面该单词的个数，即认为有效，count++，直到count的数值等于words里面单词的个数。
那不会加入到很多冗余字符吗？不用担心，因为我们还有长度约束！

代码：

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {unordered_map<string, int> wordsmap;for(auto x : words) wordsmap[x]++;  // 获取words的哈希表vector<int> ans; // 记录答案int len = words[0].size(), n = words.size();for(int i = 0; i < len; i++) // 进行 len 次滑动窗口{unordered_map<string, int> smap;for(int left = i, right = i, count = 0; right + len <= s.size(); right += len){string in = s.substr(right, len); // 进窗口，维护 countsmap[in]++;if(wordsmap.count(in) && smap[in] <= wordsmap[in]) count++; // 判断字符是否有效if(right - left + len > len * n) // right - left 反映的是上一次的子串的长度，加len是因为，我们在进窗口的时候，没有更新right的位置。{// 出窗口 + 维护 countstring out = s.substr(left, len);if(smap[out] <= wordsmap[out]) count--;smap[out]--;left += len;}if(count == n) ans.push_back(left);}}return ans;}
};

时间复杂度：O(n)
空间复杂度：O(1)

LCR 017. 最小覆盖子串

在这里插入图片描述

个人解

思路：
这道题没什么好说的了，还是哈希 + 滑动窗口，然后用count来记录有效字符。（把 438 和LCR 017 吃透这题就很简单）
用时：15:00
屎山代码：

class Solution {
public:string minWindow(string s, string t) {string ans = "";int count = 0, min_len = INT_MAX;unordered_map<char, int> tmap, smap;for(auto x: t) tmap[x]++;for(int left = 0, right = 0; right < s.size(); right++){char in = s[right]; // 进窗口smap[in]++;if(tmap.count(in) && smap[in] <= tmap[in]) count++;while(count == t.size()) // 判断{if(ans == "" || right - left + 1 < min_len) // 更新结果{min_len = right - left + 1;ans = s.substr(left, min_len);}char out = s[left];if(smap[out] <= tmap[out]) count--;smap[out]--;left++; // 出窗口}}return ans;}
};

时间复杂度：O(n)
空间复杂度：O(1)

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！

【专题刷题】滑动窗口（四）：

📝前言说明： 本专栏主要记录本人的基础算法学习以及LeetCode刷题记录，按专题划分每题主要记录：（1）本人解法本人屎山代码；（2）优质解法优质代码；&#xff…...

编程日记 2025/7/5 13:21:51

小白自学python第一天

学习python的第一天一、常用的值类型（先来粗略认识一下~） 类型说明数字（number）包含整型（int）、浮点型（float）、复数（complex）、布尔（boolean&…...

编程日记 2025/7/5 13:17:27

Redis 服务自动开启、设置密码和闪退问题

一、Redis 服务自动开启 1、以管理员身份运行命令提示符右键点击“命令提示符”图标，选择“以管理员身份运行”。 2、注册为 Windows 服务 redis-server --service-install 3、启动服务 redis-server --service-start 4、测试 Redis 连接 redis-cli ping …...

编程日记 2025/7/5 13:18:15

2025年渗透测试面试题总结-拷打题库14（题目+回答）

网络安全领域各种资源，学习文档，以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具，欢迎关注。目录 2025年渗透测试面试题总结-拷打题库14 1. WAF存在的意义 2. 威胁感知能力衡量指标 3. 感知规则有效性…...

编程日记 2025/7/5 13:19:13

java后端开发day35--集合进阶（四）--双列集合：MapHashMapTreeMap

（以下内容全部来自上述课程） 1.双列集合 1.1 特点双列集合一次需要存一对数据，分别为键和值键不能重复，值可以重复键和值是一一对应的，每一个键只能找到自己对应的值键值这个整体，我们称之为“键值对”…...

编程日记 2025/7/5 12:54:26

进行网页开发时，怎样把function（）中变量值在控制台输出，查看?

在网页开发过程中，为了及时了解JavaScript中的function函数中的变量值，可以用控制台命令console.log()把变量的值在控制台输出，方便调试时对函数变量值进行了解。看下面的一段示例： <!DOCTYPE html> <html> &l…...

编程日记 2025/7/5 12:48:46

【计算机网络】现代网络技术核心架构与实战解析

目录前言技术背景与价值当前技术痛点解决方案概述目标读者说明一、技术原理剖析核心概念图解核心作用讲解关键技术模块说明技术选型对比二、实战演示环境配置要求核心代码实现案例1：TCP服务端/客户端通信案例2：Wireshark抓包分析三、性能对比测试方法…...

编程日记 2025/7/5 11:54:51

Python内置函数---bool()

用于将任意对象转换为布尔值（True或False） 1. 基本语法与参数 bool(x) - 参数：x为可选参数，可以是任意Python对象（如数值、字符串、列表、自定义对象等）。 - 返回值：根据x的真值性返回True或Fa…...

编程日记 2025/7/5 12:52:17

Vue 3中如何封装API请求：提升开发效率的最佳实践

在现代前端开发中，API请求是不可避免的一部分，尤其是与后端交互时。随着Vue 3的广泛应用，如何高效地封装API请求，既能提升代码的可维护性，又能确保代码的高复用性，成为了很多开发者关注的话题。在本文中&…...

编程日记 2025/7/5 11:42:12

【Redis】redis主从哨兵

Redis 主从复制在访问量极高的场景下，单台 Redis 已难以承载所有请求，且单点故障风险高。通过主从复制，可以实现读写分离、数据备份与高可用。概念主节点（Master）：负责写操作，将数据变更同…...

编程日记 2025/6/29 10:50:44

16.第二阶段x64游戏实战-分析二叉树结构

免责声明：内容仅供学习参考，请合法利用知识，禁止进行违法犯罪活动！ 本次游戏没法给内容参考于：微尘网络安全上一个内容：15.第二阶段x64游戏实战-分析怪物血量（遍历周围） 首先通…...

编程日记 2025/7/5 10:46:15

vue | 不同 vue 版本对复杂泛型的支持情况 · vue3.2 VS vue3.5

省流总结：defineProps 的泛型能力，来直接推导第三方组件的 props 类型引入第三方库的类型，并直接在 <script setup> 中作为 props 使用。这种类型一般是复杂泛型（包含联合类型、可选属性、交叉类型、条件类型等&#xff0…...

编程日记 2025/7/5 13:11:25

OpenGL学习笔记（Blinn-Phong、伽马矫正、阴影）

目录 Blinn-PhongGamma矫正GammaGamma矫正实现方法sRGB纹理衰减阴影shadow mapping渲染阴影改进阴影贴图PCF GitHub主页：https://github.com/sdpyy1 OpenGL学习仓库:https://github.com/sdpyy1/CppLearn/tree/main/OpenGLtree/main/OpenGL):https://github.com/sdp…...

编程日记 2025/7/5 12:37:47

GPLT-2025年第十届团体程序设计天梯赛总决赛题解(2025天梯赛题解,266分)

今天偶然发现天梯赛的代码还保存着，于是决定写下这篇题解，也算是复盘一下了 L1本来是打算写的稳妥点，最后在L1-6又想省时间，又忘记了insert，replace这些方法怎么用，也不想花时间写一个文件测试&#xff0c…...

编程日记 2025/7/5 13:20:57

day4 pandas学习

%pip install openxyxl 找一个自己觉得有意思的文件。我找的是成绩单来玩。这节学的比较耗时了，大概用了60分钟。 import pandas as pd data2 pd.read_csv(rD:\python代码区\代码随想录挑战-调试区\python训练营\1_计算类专业分流学生成绩排名.csv) #print(data)…...

编程日记 2025/7/5 12:41:59

【Java学习笔记】循环结构

循环结构一、for循环 for循环结构 for(循环变量初始化;循环条件;循环变量迭代){循环操作（可以多条语句） }for循环写死循环 for(;;){语句 }注意点：循环变量的初始化在for语句内，属于是局部变量，在全局中会出现未定义…...

编程日记 2025/7/5 12:01:59

URP-UGUI交互功能实现

一、非代码层面实现交互（SetActive） Button ：在OnClick（）中添加SetActive方法（但是此时只首次有效） Toggle ：在OnClick（）中添加动态的SetActive方法 &#…...

编程日记 2025/7/5 12:12:39

08-IDEA企业开发工具-集成AI插件通义灵码

需要登陆才可使用！！！ 1. 安装AI编程插件找到插件: 在IDEA的设置中，找到插件（Plugins）部分。安装插件: 搜索“通义灵码”，找到后点击安装（Install），接受条款…...

编程日记 2025/7/5 12:15:25

解决报错：this[kHandle] = new _Hash(algorithm, xofLen)；

前端项目编译报错： node:internal/crypto/hash:68this[kHandle] new _Hash(algorithm, xofLen);^Error: error:0308010C:digital envelope routines::unsupportedat new Hash (node:internal/crypto/hash:68:19)at Object.createHash (node:crypto:138:10)at modu…...

编程日记 2025/7/5 13:03:51

使用 Streamlit 打造一个简单的照片墙应用

在现代 web 开发中，快速构建交互式应用是一项重要的技能。Streamlit 是一个强大的 Python 库，允许开发者以最小的代码量创建美观且功能丰富的 web 应用。今天，我们将通过分析一段简单的 Streamlit 代码，展示如何构建一个照片墙应用…...

编程日记 2025/7/5 11:58:18

深度学习优化器和调度器的选择和推荐

一、常用优化器对比 1. 随机梯度下降（SGD） 原理：每次迭代使用小批量数据计算梯度并更新参数。优点：实现简单，适合大规模数据集。缺点：收敛速度慢，容易陷入局部最优或鞍点。适用场景&#xff1…...

编程日记 2025/7/5 12:40:22

“时间”，在数据处理中的真身——弼马温一般『无所不能』（DeepSeek）

电子表格时间处理真理：数值存储最瘦身，真身闯关通四海。笔记模板由python脚本于2025-04-23 22:25:59创建，本篇笔记适合喜欢在电子表格中探求时间格式的coder翻阅。【学习的细节是欢悦的历程】博客的核心价值：在于输出思考与经验…...

编程日记 2025/7/5 12:59:12

为什么Spring中@Bean注解默认创建单例Bean

在Spring框架中，使用Bean注解定义的对象默认确实是单例的，这是由Spring容器的设计哲学和实际需求决定的。下面我从多个角度解释这一设计选择的原因和机制。 1. Spring Bean作用域基础 Spring定义了多种Bean作用域，其中默认是单例(Singleton…...

编程日记 2025/7/5 12:29:54

GPLT-2025年第十届团体程序设计天梯赛总决赛题解(2025天梯赛题解，共计266分)

编程日记 2025/7/5 11:23:56

JDK（Ubuntu 18.04.6 LTS）安装笔记

一、前言本文与【MySQL 8（Ubuntu 18.04.6 LTS）安装笔记】同批次：先搭建数据库，再安装JDK，后面肯定就是部署Web应用：典型的单机部署。“麻雀虽小五脏俱全”，善始善终，还是记下来吧。…...

编程日记 2025/7/5 12:48:44

Java 拦截器完全指南：原理、实战与最佳实践

一、引言拦截器的基本概念在现代 Java Web 开发中，拦截器（Interceptor）是一种用于在请求处理前后插入自定义逻辑的机制。简单来说，它是一种“横切逻辑处理器”，可以用来对请求进行预处理、后处理，甚至终…...

编程日记 2025/7/5 11:31:23

2025.04.23华为机考第二题-200分

📌 点击直达笔试专栏 👉《大厂笔试突围》 💻 春秋招笔试突围在线OJ 👉 笔试突围OJ 02. 魔法彩灯森林问题描述在卢小姐的魔法花园中，有一棵神奇的彩灯树。这棵树的每个节点都装有一盏魔法灯，灯有三种颜色状态：红色（用数字1表示）、绿色（用数字2表示）和蓝色（…...

编程日记 2025/7/5 12:22:17

【Leetcode 每日一题】1399. 统计最大组的数目

问题背景给你一个整数 n n n。请你先求出从 1 1 1 到 n n n 的每个整数 10 10 10 进制表示下的数位和（每一位上的数字相加），然后把数位和相等的数字放到同一个组中。请你统计每个组中的数字数目，并返回数字数目并列最多的组…...

编程日记 2025/7/5 12:43:36

系统重装——联想sharkbay主板电脑

上周给一台老电脑重装系统系统，型号是lenovo sharkbay主板的电脑，趁着最近固态便宜，入手了两块长城的固态，装上以后插上启动U盘，死活进不去boot系统。提示 bootmgr 缺失，上网查了许久，终于解决了…...

编程日记 2025/7/5 12:49:35

Python数据清洗笔记（上）

一、数据清洗概述数据清洗是数据分析过程中至关重要的一步，约占整个数据分析过程的60%-80%的时间。主要包括处理缺失值、异常值、重复值、格式不一致等问题。二、常用工具主要使用Python的Pandas库进行数据清洗： import pandas as pd import nump…...

编程日记 2025/7/5 13:15:52

三、Python编程基础03

目录一、debug 调试的使用1. 打断点2. 右键 Debug 运行代码3. 单步执行代码,查看过程二、字符串1、定义与下标引用2、切片3、查找4、去除空白字符5、转换大小写与拆分6、其他方法-替换、连接、是否为纯数字7、登录案例优化三、列表 list1、列表基础操作2、案例： …...

编程日记 2025/7/5 12:25:10

西门子S7-200SMART 控制Profinet闭环步进MD-4250-PN (1)电机及专栏介绍

一、前言本系列是我继《西门子S7-1200PLC 控制步进电机 MD-4240-PN》系列专栏后，新开的一篇专栏。系列的主题围绕 S7-200SMART Profinet闭环步进(MD-4250-PN) 触摸屏的硬件，预计作四篇文章，分别为：专栏介绍、硬件介绍、PLC…...

编程日记 2025/7/5 12:22:18

NoSQL 简单讲解

目录 1. NoSQL 的背景与意义 1.1 数据库的演变 1.2 NoSQL 的兴起 2. NoSQL 数据库的分类 2.1 键值存储（Key-Value Stores） 2.2 文档数据库（Document Stores） 2.3 列族存储（Column-Family Stores） 2.…...

编程日记 2025/7/5 12:14:24

TCP 协议：原理、机制与应用

一、引言在当今数字化的时代，网络通信无处不在，而 TCP（Transmission Control Protocol，传输控制协议）作为互联网协议栈中的核心协议之一，扮演着至关重要的角色。无论是浏览网页、发送电子邮件还是进行文件…...

编程日记 2025/6/29 10:22:34

C++23 新特性：令声明顺序决定非静态类数据成员的布局 (P1847R4)

文章目录引言背景知识非静态类数据成员类的内存布局 P1847R4提案内容示例代码影响和优势提高代码的可预测性与其他语言和库的交互更加方便简化代码调试和优化编译器支持情况实际应用场景嵌入式系统开发跨语言编程内存优化总结引言在C的发展历程中，每一个新版…...

编程日记 2025/7/5 11:46:23

Java 环境配置详解（Windows、macOS、Linux）

Java 环境配置是学习和开发 Java 程序的第一步，也是至关重要的一步。一个正确配置的 Java 环境能够保证你的 Java 程序能够顺利编译、运行和调试。本文将详细介绍在 Windows、macOS 和 Linux 三种主流操作系统上配置 Java 环境的步骤，力求详尽、易懂&…...

编程日记 2025/7/5 13:16:37

ChatBEV：一种理解 BEV 地图的可视化语言模型

25年3月来自上海交大、上海AI实验室、同济大学和MAGIC的论文“ChatBEV: A Visual Language Model that Understands BEV Maps”。交通场景理解对于智能交通系统和自动驾驶至关重要，可确保车辆安全高效地运行。虽然 VLM 的最新进展已显示出整体场景理解的前景&…...

编程日记 2025/7/5 11:25:17

利用Python爬虫实现百度图片搜索的PNG图片下载

在图像识别、训练数据集构建等场景中，我们经常需要从互联网上批量下载图片素材。百度图片是中文搜索中最常用的来源之一。本文将介绍如何使用Python构建一个稳定、可扩展的百度图片爬虫，专门用于下载并保存高清PNG格式图片。一、项目目标本项目的目标…...

编程日记 2025/7/5 13:18:15

自主可控鸿道Intewell工业实时操作系统

鸿道Intewell工业实时操作系统是东土科技旗下科东软件自主研发的新一代智能工业操作系统，以下是相关介绍： 系统架构 -Intewell-C全实时构型：设备上只运行自研RTOS的全实时系统，适用于有功能安全认证需求的实时控制场景&#xf…...

编程日记 2025/7/5 10:52:05

【数据结构入门训练DAY-21】信息学奥赛一本通T1334-围圈报数

文章目录前言一、题目二、解题思路结语前言本次训练内容 STL库中队列的使用练习。训练解题思维一、题目有ｎ个人依次围成一圈，从第１个人开始报数，数到第ｍ个人出列，然后从出列的下一个人开始报数&am…...

编程日记 2025/7/5 11:57:29

【C语言】C语言中的字符函数和字符串函数全解析

前言在C语言编程中，字符和字符串的处理是必不可少的。C语言标准库提供了丰富的字符和字符串函数，这些函数极大地简化了字符和字符串的操作。本文将详细介绍这些函数的使用方法、模拟实现以及一些实用的代码示例，帮助你更好地理解和掌握它们…...

编程日记 2025/7/5 12:25:12

声纹振动传感器在电力监测领域的应用

声纹振动传感器在电力监测领域有多种应用，主要包括以下几个方面： 变压器监测故障诊断：变压器在运行过程中会产生特定的声纹和振动信号，当变压器内部出现故障，如绕组短路、铁芯松动、局部放电等，其声纹和振…...

编程日记 2025/7/5 4:53:52

配色之道：解码产品设计中的UI设计配色艺术

在数字化时代，用户界面（UI）作为产品与用户交互的桥梁，其设计质量直接影响着用户体验与产品成败。而配色，作为UI设计中最为直观且富有表现力的元素之一，不仅是视觉美学的体现，更是情感传递、信息…...

编程日记 2025/7/3 6:45:22

python基础语法测试

1. 关于Python语言数值操作符，以下选项中描述错误的是 A x%y表示x与y之商的余数，也称为模运算 B x/y表示x与y之商 C x**y表示x的y次幂，其中，y必须是整数 D x//y表示x与y之整数商，即不大于x与y之商的最大整数2. 下面代码…...

编程日记 2025/7/5 3:55:44

如何安装Visio（win10）

首先下载下面这些文件 HomeStudent2021Retail.img officedeploymenttool_17531-20046.exe office中文语言包.exe 确保这些文件都在一个文件夹内（我已经上传这些资源，这些资源都是官网下载的） 官网资源下载教程 1.下载Office镜像&#xff0…...

编程日记 2025/7/5 9:46:15

Sql刷题日志（day5）

面试： 1、从数据分析角度，推荐模块怎么用指标衡量？ 推荐模块主要目的是将用户进行转化，所以其主指标是推荐的转化率推荐模块的指标一般都通过埋点去收集用户的行为并完成相应的计算而形成相应的指标数据，而这里的驱动…...

编程日记 2025/6/29 11:21:34

.NET、java、python语言连接SAP系统的方法

💡 本文会带给你可用哪些技术与Sap系统连接怎样用Rfc技术连接SAP一. SAP系统与外部系统集成技术 SAP系统提供了多种方式供Java、.NET、Python等外部编程语言进行连接和集成。 1. RFC (Remote Function Call) 连接适用语言：Java, .NET, Python, 其他支持RFC的编程语言 …...

编程日记 2025/7/2 16:18:34

C++ 容器查找效率

C 容器查找效率只要选对容器，多写几行代码就能让程序“飞”起来。下面用生活化的比喻足够多的带注释示例，帮你弄懂常用 STL 容器的查找特性。读完你应该能快速判断：“我的场景该用哪一个？” 0. 先把“查找复杂度”聊明白记号…...

编程日记 2025/7/3 6:46:18

汽车可变转向比系统的全面认识

一、什么是转向比？ 转向比又叫转向传动比，是指方向盘转向角度与车轮转向角度之比。例如，方向盘向左转动了60角，而车轮则向左转动了30角，转向比就是2：1。转向比越大，意味着要使车轮转向达到指…...

编程日记 2025/6/29 10:37:02

知识储备-后仿

仿真环境设定 mem、constant input(scan/test)等设非x初值无复位ff通过force-release处理vcs timing_check、optconfigfile (自定义配置，如指定模块timing check与否）设置运行核数、仿真精度不要过小设置、根据测试目的选择性关闭、dump范围(时间/空间)…...

编程日记 2025/6/29 12:07:50

视频

30. 串联所有单词的子串

个人解

优质解：

LCR 017. 最小覆盖子串

个人解

相关文章：