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

面试经典题---30.串联所有单词的子串

30.串联所有单词的子串

我的解法:

滑动窗口:

  • 解法中用到了两个哈希表map1和map2,分别用于记录words中各个单词的出现频数和当前滑动窗口[left, right)中单词的出现频数;
  • 外部for循环i从0到len - 1,内部while循环每次会让滑动窗口滑动len步,即开头位置为i时,这一轮就可以遍历到i + k*len开头的子串,因此i取0到len - 1可以覆盖所有的子串开头情况;
  • 内部while循环每次先取right开头的长度为len的子串tmp,判断tmp是否是words中的单词:
    • 不是则更新窗口左端点,清空count和哈希表map2
    • 属于words中的单词时count加1,更新哈希表map2,若tmp重复出现了,则要收缩滑动窗口左端,并更新count和map2(注意判断重复出现这里用的是while循环)
class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> res;if(s.empty() || words.empty()){return res;}int len = words[0].size();int size = words.size();unordered_map<string, int> map1;for(auto w : words){map1[w]++;}for(int i = 0; i < len; ++i){int left = i, right = i;int count = 0;unordered_map<string,int> map2;while(right + len <= s.size()){string tmp = s.substr(right, len);right += len;if(map1.count(tmp) == 0){left = right;count = 0;map2.clear();}else{count++;map2[tmp]++;while(map1[tmp] < map2[tmp]){string re_word = s.substr(left, len);count--;map2[re_word]--;left += len;}if(count == size){res.push_back(left);}}}}return res;}
};

相关文章:

面试经典题---30.串联所有单词的子串

30.串联所有单词的子串 我的解法&#xff1a; 滑动窗口&#xff1a; 解法中用到了两个哈希表map1和map2&#xff0c;分别用于记录words中各个单词的出现频数和当前滑动窗口[left, right)中单词的出现频数&#xff1b;外部for循环i从0到len - 1&#xff0c;内部while循环每次会…...

字符串随机生成工具(开源)-Kimen(奇门)

由于最近笔者在开发数据脱敏相关功能&#xff0c;其中一类脱敏需求为能够按照指定的格式随机生成一个字符串来代替原有信息&#xff0c;数据看起来格式需要与原数据相同&#xff0c;如&#xff1a;电话号码&#xff0c;身份证号以及邮箱等。在网上搜索了下&#xff0c;发现没有…...

UE4 CustomDepthMobile流程小记

原生UE opaque材质中获取CustomDepth/CustomStencil会报错 在其Compile中调用的函数中没有看到报错逻辑 材质节点的逻辑都没有什么问题&#xff0c;所以看一下报错 在HLSLMaterialTranslator::Translate中 修改之后 mobile流程的不透明材质可以直接获取SceneTexture::customd…...

Docker 基础篇

目录 一、Docker 简介 1. Docker 2. Linux 容器 3. 传统虚拟机和容器的对比 4. Docker 的作用 5. Docker 的基本组成&#xff08;Docker 三要素&#xff09; 6. Docker 工作原理 7. Docker 架构 8. Docker 下载 二、Docker 安装 1. CentOS Docker 安装 2. CentOS8 …...

Idea上操作Git回退本地版本,怎么样保留已修改的文件,回退本地版本的四种方式代表什么?

Git的基本概念:Git是一个版本控制系统,用于管理代码的变更历史记录。核心概念包括仓库、分支、提交和合并。 1、可以帮助开发者合并开发的代码 2、如果出现冲突代码的合并,会提示后提交合并代码的开发者,让其解决冲突 3、代码文件版本管理 问题描述 当我们使用git提交代码…...

vue3封装el-pagination分页组件

1、效果如图&#xff1a; 2、分页组件代码&#xff1a; <template><div class"paging"><el-config-provider :locale"zhCn"><el-paginationv-model:current-page"page.currentPage"v-model:page-size"page.pageSize…...

负载均衡下Webshell连接思路及难点

君衍. 一、应用场景二、环境搭建三、思路以及难点1、查看内部结构2、查看webshell3、使用蚁剑进行连接4、难点1 shell文件上传问题5、难点2 命令执行时飘逸6、难点3 大工具上传失败7、难点4 脚本失效 四、解决方式1、关闭对方节点服务器2、基于IP地址判断是否执行3、脚本实现流…...

基于链表实现贪吃蛇游戏

本文中&#xff0c;我们将使用链表和一些Win32 API的知识来实现贪吃蛇小游戏 一、功能 &#xff08;1&#xff09;游戏载入界面 &#xff08;2&#xff09;地图的绘制 &#xff08;3&#xff09;蛇身的移动和变长 &#xff08;4&#xff09;食物的生成 &#xff08;5&…...

Python网络爬虫实战——实验6:Python实现js逆向与加解密

【实验内容】 本实验主要介绍在数据采集过程中对js代码进行分析从而对加密字段进行解密。 【实验目的】 1、理解js逆向工程的概念 2、学会逆向工程中的加解密分析 【实验步骤】 步骤1 理解js逆向工程的概念 步骤2 学会逆向工程中的加解密分析 步骤3 采集广东政府采购网 步…...

【python】使用aiohttp库编写一个简单的异步服务器

1. aiohttp介绍 aiohttp 是一个用于编写异步 HTTP 客户端和服务器的 Python 库。它建立在 Python 的 asyncio 库之上&#xff0c;提供了一种方便的方式来处理异步请求和响应。 官网地址&#xff1a;Welcome to AIOHTTP — aiohttp 3.9.1 documentation 以下是 aiohttp 的一些…...

新手使用代理IP接入代码教程

“实现匿名访问与数据保护在当今互联网高速发展的时代&#xff0c;网络安全和隐私保护成为了越来越重要的议题。代理IP可以隐藏用户的真实IP地址&#xff0c;从而实现匿名访问。为了保护用户的隐私和数据安全&#xff0c;许多网站和应用程序都采用了代理IP技术。” 一、代理IP的…...

JVM问题排查手册

三万字长文&#xff1a;JVM内存问题排查Cookbook 一、Heap快照 # jmap命令保存整个Java堆&#xff08;在你dump的时间不是事故发生点的时候尤其推荐&#xff09; jmap -dump:formatb,fileheap.bin <pid> # jmap命令只保存Java堆中的存活对象, 包含live选项&#xff0c;…...

前端canvas项目实战——简历制作网站(三)——右侧属性栏(线条宽度样式)

目录 前言一、效果展示二、实现步骤1. 实现线条宽度&#xff08;strokeWidth&#xff09;的属性模块2. 实线线条样式&#xff08;strokeDashArray&#xff09;的属性模块3. 意料之外的“联动” 三、Show u the code后记 前言 上一篇博文中&#xff0c;我们初步实现了右侧属性栏…...

字节跳动二面经典题目

前言 语论即为「语兴式论语」&#xff0c;以语录体及对话的形式&#xff0c;沉淀球友实际工作学习中存在的疑难杂症解答&#xff0c;希望能够更好的帮助到球友和粉丝。欢迎关注公众号&#xff1a;语数 本期投稿 本期语数精选来源于球友应对字节跳动二面时候的场景问题 数仓工程…...

微搭低代码从入门到精通01应用介绍

目录 1 学习路线图2 应用介绍3 编辑器介绍总结 低代码的概念于2014年由 Forrester 首次正式提出。其将低代码定义为&#xff1a;能够以“最少的手写代码”和设置快速开发应用、配置和部署业务应用程序。 不同应用厂商的解法不一样&#xff0c;Gartner评估了400多款低代码/无代码…...

论文阅读《thanking frequency fordeepfake detection》

项目链接&#xff1a;https://github.com/yyk-wew/F3Net 这篇论文从频域的角度出发&#xff0c;提出了频域感知模型用于deepfake检测的模型 整体架构图&#xff1a; 1.FAD&#xff1a; 频域感知分解&#xff0c;其实就是利用DCT变换&#xff0c;将空间域转换为频域&#xff…...

ArcgisForJs快速入门

文章目录 0.引言1.前端代码编辑工具2.使用ArcgisForJs创建一个简单应用3.切片地图服务图层4.动态地图服务图层5.地图事件 0.引言 ArcGIS API for JavaScript是一款由Esri公司开发的用于创建WebGIS应用的JavaScript库。它允许开发者通过调用ArcGIS Server的REST API&#xff0c…...

【解决方法】git pull报错ssh: connect to host github.com port 22: Connection timed out

问题 git pull ssh: connect to host github.com port 22: Connection timed out fatal: Could not read from remote repository.解决方法 在C:\Users\username.ssh文件夹下新建config文件&#xff0c;填入以下文本&#xff08;如有则直接在文件最后一行新增&#xff09;&am…...

30天精通Nodejs--第三十天:项目实战-物联网应用

目录 引言架构设计编码创建项目数据服务模拟设备消息接收并保存设备数据后端接口项目启动及接口测试项目启动测试源码地址结语引言 在之前的一系列文章中,我们已系统性地探讨了诸多Node.js相关的技术要点与理论背景。随着知识体系的铺垫到位,我们现在步入了实战环节。接下来…...

java 社区资源管理系统Myeclipse开发mysql数据库web结构java编程计算机网页项目

一、源码特点 java Web社区资源管系统是一套完善的java web信息管理系统 &#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。开发环境为TOMCAT7.0,Myeclipse8.5开发&#xff0c;数据库为Mysql5.…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

基于IDIG-GAN的小样本电机轴承故障诊断

目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) ​梯度归一化(Gradient Normalization)​​ (2) ​判别器梯度间隙正则化(Discriminator Gradient Gap Regularization)​​ (3) ​自注意力机制(Self-Attention)​​ 3. 完整损失函数 二…...

Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么&#xff1f;它的作用是什么&#xff1f; Spring框架的核心容器是IoC&#xff08;控制反转&#xff09;容器。它的主要作用是管理对…...

热烈祝贺埃文科技正式加入可信数据空间发展联盟

2025年4月29日&#xff0c;在福州举办的第八届数字中国建设峰会“可信数据空间分论坛”上&#xff0c;可信数据空间发展联盟正式宣告成立。国家数据局党组书记、局长刘烈宏出席并致辞&#xff0c;强调该联盟是推进全国一体化数据市场建设的关键抓手。 郑州埃文科技有限公司&am…...

Vue 3 + WebSocket 实战:公司通知实时推送功能详解

&#x1f4e2; Vue 3 WebSocket 实战&#xff1a;公司通知实时推送功能详解 &#x1f4cc; 收藏 点赞 关注&#xff0c;项目中要用到推送功能时就不怕找不到了&#xff01; 实时通知是企业系统中常见的功能&#xff0c;比如&#xff1a;管理员发布通知后&#xff0c;所有用户…...