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

力扣 438.找到字符串中所有字母异位词

题目:

给定两个字符串 s 和 p,找到 s 中所有 p 的 

异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

 示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

分析:

借鉴了力扣49题的思路,拼接p中字符和字符出现次数来作为判断异位词的条件。从头开始遍历,计算s字符串中当前下标以及当前下标+p.length()-1之间字符的出现次数,进行拼接,与p的拼接结果进行比较,相同则保存当前下标。

这种方法虽然能通过但是太慢,每次都要拼接,都要进行一个26次的循环。

改进:

49题进行拼接是因为要在一堆字符串中找出其中的异位词组,所以要用拼接的结果作为unordered_map的键值,去和异位词做映射,保存拼接结果与键值相同的异位词。这题并不不需要,题目已经给出要找的字符串,所以直接比较字符出现次数就行。

采用滑动窗口,由于已经给出要查找的字符串,那么滑动窗口的大小就确定,是p的长度。在s和p中,都先从头开始,计算窗口大小字符串中字符的出现次数,保存在数组(scount,pcount)中(字符与下标映射)。然后s开始滑动:将窗口的首元素滑出,同时改变数组中该字符对应下标的元素的值(-1),然后将新字符加入滑动窗口,同理,改变scount数组中该字符对应下标的元素的值(+1)。滑动完一次,比较一次sount数组与pcount数组,相同则将窗口首元素在字符串中对应的下标保存。

代码:

class Solution {public:vector<int> findAnagrams(string s, string p) {vector<int>res;vector<int>scount(26);vector<int>pcount(26);for(int i=0;i<p.length();++i){scount[s[i]-'a']++;pcount[p[i]-'a']++;}if(scount==pcount){res.push_back(0);}for(int i=0;i<(s.length()-p.length());++i){//移除滑动窗口队头,增加新元素--scount[s[i]-'a'];++scount[s[i+p.length()]-'a'];if(scount==pcount){res.push_back(i+1);}}return res;}};

相关文章:

力扣 438.找到字符串中所有字母异位词

题目&#xff1a; 给定两个字符串 s 和 p&#xff0c;找到 s 中所有 p 的 异位词 的子串&#xff0c;返回这些子串的起始索引。不考虑答案输出的顺序。 示例 1: 输入: s "cbaebabacd", p "abc" 输出: [0,6] 解释: 起始索引等于 0 的子串是 "cb…...

【Python】Python入门——基础语法及顺序语句

Python入门——基础语法及顺序语句 官方文档地址&#xff1a;https://docs.python.org/zh-cn/3/tutorial/index.htmlPython 是一门易于学习、功能强大的编程语言。它提供了高效的高级数据结构&#xff0c;还能简单有效地面向对象编程。Python 优雅的语法和动态类型以及解释型语…...

2.2 反向传播:神经网络如何“学习“?

一、神经网络就像小学生 想象一个刚学算术的小学生&#xff0c;老师每天布置练习题&#xff0c;学生根据例题尝试解题&#xff0c;老师批改后指出错误。神经网络的学习过程与此相似&#xff1a; 输入层&#xff1a;相当于练习题&#xff08;如数字图片&#xff09;输出层&…...

frp-tool,客户端frp命令行工具

在日常开发和运维过程中&#xff0c;端口转发和配置管理是常见的需求。 如果有自己一台服务器&#xff0c;并且已经开放好端口&#xff0c;配置好token后&#xff0c;这个工具一定能帮到你。 今天给大家推荐一款非常好用的frpc命令行工具&#xff0c;它是一个用Python编写的命令…...

【学术投稿-第五届应用数学、建模与智能计算国际学术会议】CSS伪类选择器深度解析:分类、应用与技巧

大会官网&#xff1a;www.cammic.org 大会时间&#xff1a;2025年3月21-23日 大会地点&#xff1a;中国-上海&#xff08;上海大学宝山校区北大门乐乎新楼&#xff09; 简介 第五届应用数学、建模与智能计算&#xff08;CAMMIC 2025&#xff09;将于2025年3月21-23日在中国…...

常用查找算法整理(顺序查找、二分查找、哈希查找、二叉排序树查找、平衡二叉树查找、红黑树查找、B树和B+树查找、分块查找)

常用的查找算法&#xff1a; 顺序查找&#xff1a;最简单的查找算法&#xff0c;适用于无序或数据量小的情况&#xff0c;逐个元素比较查找目标值。二分查找&#xff1a;要求数据有序&#xff0c;通过不断比较中间元素与目标值&#xff0c;将查找范围缩小一半&#xff0c;效率…...

Express 中 res 响应方法详解

一、res.send() 1. 功能 该方法用于发送各种类型的响应&#xff0c;包括字符串、对象、数组、Buffer 等。它会自动设置响应的 Content-Type 头。 2. 示例代码 const express require("express");const app express();app.get("/", (req, res) > {…...

DeepAR:一种用于时间序列预测的深度学习模型

介绍 DeepAR是一种基于递归神经网络&#xff08;RNN&#xff09;的时间序列预测模型&#xff0c;由亚马逊在2017年提出。它特别适用于处理多变量时间序列数据&#xff0c;并能够生成概率预测。DeepAR通过联合训练多个相关时间序列来提高预测性能&#xff0c;从而在实际应用中表…...

权限模型深度解析:RBAC vs ABAC vs PBAC vs TBAC,如何选择最适合的方案?

在数字化系统的安全架构中&#xff0c;权限管理如同一把“隐形钥匙”&#xff0c;既需精准控制访问边界&#xff0c;又要灵活适配复杂多变的业务需求。从传统的角色划分到动态属性策略&#xff0c;从合规驱动的集中管控到任务流程的临时授权&#xff0c;RBAC、ABAC、PBAC、TBAC…...

Windows逆向工程入门之堆栈结构与信息获取

公开视频 -> 链接点击跳转公开课程博客首页 -> ​​​链接点击跳转博客主页 目录 1. 堆栈结构基础 堆栈的主要操作&#xff1a; 2. 代码功能解析 2.1 加载 ntdll.dll 2.2 获取 NtQueryInformationThread 函数指针 2.3 调用 NtQueryInformationThread 获取线程信息…...

【c++初阶】类和对象②默认成员函数以及运算符重载初识

目录 ​编辑 默认成员函数&#xff1a; 构造函数 构造函数的特性&#xff1a; 析构函数&#xff1a; 拷贝构造函数&#xff1a; 1. 拷贝构造函数是构造函数的一个重载形式。 2. 拷贝构造函数的参数只有一个且必须是类类型对象的引用&#xff0c;使用传值方式编译器直接报…...

【做一个微信小程序】校园地图页面实现

前言 上一个教程我们实现了小程序的一些的功能&#xff0c;有背景渐变色&#xff0c;发布功能有的呢&#xff0c;已支持图片上传功能&#xff0c;表情和投票功能开发中&#xff08;请期待&#xff09;。下面是一个更高级的微信小程序实现&#xff0c;包含以下功能&#xff1a;…...

成熟开发者需具备的能力

精业务 • 指深入理解和熟悉所开发软件的业务逻辑和需求。 • 开发者需要明确软件要解决的问题、面向的用户群体以及核心功能等。 • 精业务有助于开发者更好地设计系统架构、编写符合业务需求的代码&#xff0c;并能根据业务变化灵活调整开发计划。 懂原理 • 指掌握编程的基…...

计算机毕业设计--基于深度学习技术(Yolov11、v8、v7、v5)算法的高效人脸检测模型设计与实现(含Github代码+Web端在线体验界面)

基于深度学习技术&#xff08;Yolov11、v8、v7、v5&#xff09;算法的高效人脸检测模型 Yolo算法应用之《基于Yolo的花卉识别算法模型设计》&#xff0c;请参考这篇CSDN作品&#x1f447; 计算机毕业设计–基于深度学习技术&#xff08;Yolov11、v8、v7、v5&#xff09;算法的…...

力扣做题记录 (二叉树)

二叉树 打算先来了解二叉树基础&#xff0c;都是简单题&#xff0c;目的是熟悉代码格式和解题基础思路。 1、二叉树最大深度 二叉树最大深度 方法一、深度搜索 直接用原函数做递归&#xff0c;比较简单 /*** Definition for a binary tree node.* struct TreeNode {* …...

机试刷题_字符串的排列【python】

题目&#xff1a;字符串的排列 from os import dup # # 代码中的类名、方法名、参数名已经指定&#xff0c;请勿修改&#xff0c;直接返回方法规定的值即可 # # # param str string字符串 # return string字符串一维数组 # class Solution:def backtrack(self,res,state,choi…...

百度智能云—千帆 ModelBuilder API的简单调用(Java)

百度简介 百度&#xff08;Baidu&#xff09;是拥有强大互联网基础的领先AI公司。百度愿景是&#xff1a;成为最懂用户&#xff0c;并能帮助人们成长的全球顶级高科技公司。 “百度”二字&#xff0c;来自于八百年前南宋词人辛弃疾的一句词&#xff1a;众里寻他千百度。这句话…...

unity学习43:子状态机 sub-state machine

目录 1sub-state machine子状态机 1.1 创建 sub-state machine 1.2 sub-state machine 内容 1.3 子状态机的应用 2 子状态机不同于blend tree的嵌套 3 应用例子&#xff1a;若角色拿不同武器的动画设计&#xff0c;可以使用2种方法 3.1 在1个图层layer里&#xff0c;使用…...

Qt MainWindow

文章目录 0. 概述1. 菜单栏 QMenuBar1.1 例子1&#xff0c;使用图形化界面1.2 例子2&#xff0c;使用代码创建1.3 例子3&#xff0c;添加快捷键1.4 例子4&#xff0c;添加子菜单1.5 例子5&#xff0c;添加分割线和图标1.6 内存泄漏问题 2. 工具栏 QToolBar2.1 例子1&#xff0c…...

GDB QUICK REFERENCE (GDB 快速参考手册)

GDB QUICK REFERENCE {GDB 快速参考手册} References GDB QUICK REFERENCE GDB Version 4 https://users.ece.utexas.edu/~adnan/gdb-refcard.pdf 查看方式&#xff1a;在新标签页中打开图片 References [1] Yongqiang Cheng, https://yongqiang.blog.csdn.net/ [2] gdb-refc…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

(一)单例模式

一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...

基于单片机的宠物屋智能系统设计与实现(论文+源码)

本设计基于单片机的宠物屋智能系统核心是实现对宠物生活环境及状态的智能管理。系统以单片机为中枢&#xff0c;连接红外测温传感器&#xff0c;可实时精准捕捉宠物体温变化&#xff0c;以便及时发现健康异常&#xff1b;水位检测传感器时刻监测饮用水余量&#xff0c;防止宠物…...

如何通过git命令查看项目连接的仓库地址?

要通过 Git 命令查看项目连接的仓库地址&#xff0c;您可以使用以下几种方法&#xff1a; 1. 查看所有远程仓库地址 使用 git remote -v 命令&#xff0c;它会显示项目中配置的所有远程仓库及其对应的 URL&#xff1a; git remote -v输出示例&#xff1a; origin https://…...

java 局域网 rtsp 取流 WebSocket 推送到前端显示 低延迟

众所周知 摄像头取流推流显示前端延迟大 传统方法是服务器取摄像头的rtsp流 然后客户端连服务器 中转多了&#xff0c;延迟一定不小。 假设相机没有专网 公网 1相机自带推流 直接推送到云服务器 然后客户端拉去 2相机只有rtsp &#xff0c;边缘服务器拉流推送到云服务器 …...