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

LeetCode LCR 015. 找到字符串中所有字母异位词 (Java)

news 来源：原创 2025/8/12 11:11:06

LCR 015. 找到字符串中所有字母异位词

题目描述

给定两个字符串 s 和 p，要求找到 s 中所有是 p 的变位词（字母相同但排列不同）的子串，并返回这些子串的起始索引。例如：

输入 s = "cbaebabacd", p = "abc"，输出 [0, 6]，因为子串 "cba" 和 "bac" 是 "abc" 的变位词。
输入 s = "abab", p = "ab"，输出 [0, 1, 2]，因为每个长为 2 的子串都是 "ab" 的变位词。

初始思路：暴力滑动窗口

核心思想

固定窗口长度：窗口长度为 p.length()，逐个遍历 s 中所有可能的窗口。
统计字符频率：对每个窗口，统计字符出现次数，与 p 的字符频率比对。
记录匹配结果：若窗口字符频率与 p 完全一致，记录当前窗口的起始索引。

代码实现

public static List<Integer> findAnagrams_2(String s, String p) {int windowLen = p.length();List<Integer> result = new ArrayList<>();int[] pCount = new int[26];// 统计 p 的字符频率for (char c : p.toCharArray()) {pCount[c - 'a']++;}for (int left = 0; left <= s.length() - windowLen; left++) {int[] sCount = new int[26];int sign = 1;// 统计当前窗口的字符频率for (int j = left; j < left + windowLen; j++) {sCount[s.charAt(j) - 'a']++;}// 比对频率是否一致for (int j = 0; j < 26; j++) {if (sCount[j] != pCount[j]) {sign = 0;break; // 优化点：发现不一致立即跳出}}if (sign == 1) {result.add(left);}}return result;
}

复杂度分析

时间复杂度：O(n * m)，其中 n 是 s 的长度，m 是 p 的长度。每次窗口需要遍历 m 个字符，共遍历 n - m + 1 次。
空间复杂度：O(1)，固定使用两个长度为 26 的数组。

优化思路：动态滑动窗口

核心改进

减少重复计算：维护一个固定长度的窗口，每次移动窗口时，只需更新移除的字符和新增的字符。
差异计数器：通过一个变量记录当前窗口与 p 的频率差异，避免每次全量比对。

优化代码

public List<Integer> findAnagrams(String s, String p) {List<Integer> result = new ArrayList<>();if (s.length() < p.length()) return result;int[] pCount = new int[26];int[] sCount = new int[26];int windowLen = p.length();// 初始化 p 的字符频率和第一个窗口的 s 字符频率for (int i = 0; i < windowLen; i++) {pCount[p.charAt(i) - 'a']++;sCount[s.charAt(i) - 'a']++;}int diff = 0;for (int i = 0; i < 26; i++) {if (sCount[i] != pCount[i]) diff++;}if (diff == 0) result.add(0);// 滑动窗口：逐个右移，动态更新频率和差异for (int right = windowLen; right < s.length(); right++) {int leftChar = s.charAt(right - windowLen) - 'a';int rightChar = s.charAt(right) - 'a';// 移除左边界字符if (sCount[leftChar] == pCount[leftChar]) diff++;sCount[leftChar]--;if (sCount[leftChar] == pCount[leftChar]) diff--;// 添加右边界字符if (sCount[rightChar] == pCount[rightChar]) diff++;sCount[rightChar]++;if (sCount[rightChar] == pCount[rightChar]) diff--;if (diff == 0) {result.add(right - windowLen + 1);}}return result;
}

关键点解释

窗口初始化：初始化 p 和第一个窗口的字符频率，计算初始差异值 diff。
滑动更新：
- 移除左边界字符：若该字符原本频率匹配，则移除后差异增加，更新后若重新匹配则差异减少。
- 添加右边界字符：同理更新差异值。
差异判断：当 diff == 0 时，当前窗口是变位词。

复杂度分析

时间复杂度：O(n)，仅遍历 s 一次。
空间复杂度：O(1)，固定使用两个长度为 26 的数组。

总结

暴力滑动窗口法直观易懂，但时间复杂度较高，适用于小规模数据。优化后的动态滑动窗口通过减少重复计算，显著提升了效率，是解决此类问题的标准方法。核心在于维护窗口的字符频率差异，避免全量比对，将时间复杂度从 O(n * m) 优化到 O(n)。

LeetCode LCR 015. 找到字符串中所有字母异位词 (Java)

LCR 015. 找到字符串中所有字母异位词题目描述给定两个字符串 s 和 p，要求找到 s 中所有是 p 的变位词（字母相同但排列不同）的子串，并返回这些子串的起始索引。例如： 输入 s "cbaebabacd", p "a…...

编程日记 2025/8/12 11:11:06

幼儿学前教育答辩词答辩技巧问题答辩自述稿

### 📘《幼儿园大班活动开展存在的问题及解决策略》📝 我的论文题目是《幼儿园大班活动开展存在的问题及解决策略》📖。我将从论文框架、研究内容、需要解决的问题、研究结论这四部分来阐述我的论文📝。论文框架由绪论&#x1f4…...

编程日记 2025/8/12 10:50:00

双目立体视觉

文章目录 1，前言2，原理3，组成部分3.1，数字图像采集。3.2 ，相机标定。3.3，图像预处理与特征提取。3.4 ，图像校正。3.5 ，立体匹配。3.6 ，三维重建。 4，主要的算…...

编程日记 2025/7/22 21:33:09

机器人弧焊二八混合气体节约

焊接技术在现代工业生产中作为关键环节之一，其效率和成本直接影响到整个制造流程的经济性与环保性。近年来，随着节能减排理念深入人心，各行业都在积极探索绿色制造方案。在焊接领域，二八混合气体的应用结合WGFACS智能流量调节系统…...

编程日记 2025/8/12 2:29:44

Linux进程通讯和原子性

在Linux系统中，进程间通信（IPC）和原子性是并发编程中的核心问题。以下是对这些概念的详细分步解释： 一、进程间通信（IPC）方法 1. 管道（Pipe） 匿名管道：用于父子进程等有…...

编程日记 2025/7/24 13:13:43

深度学习之用CelebA_Spoof数据集搭建一个活体检测-一些模型训练中的改动带来的改善

实验背景在前面的深度学习之用CelebA_Spoof数据集搭建一个活体检测-模型搭建和训练，我们基于CelebA_Spoof数据集构建了一个用SqueezeNe框架进行训练的活体2D模型，采用了蒸馏法进行了一些简单的工作。在前面提供的训练参数中，主要用了以下几…...

编程日记 2025/7/15 10:56:57

Oracle APEX IR报表列宽调整

1. 问题：如何调整Oracle APEX IR报表列宽 1-1. 防止因标题长而数据短，导致标题行的文字都立起来了，不好看。 1-2. 防止因数据太长而且中间还没有空格，把列撑开的太宽也不换行，不好看。 2. 解决办法针对如上问题解…...

编程日记 2025/7/15 10:56:55

6大核心记忆方法

以下是结合脑科学原理和高效学习策略总结的 6大核心记忆方法，帮助你摆脱“学完就忘”的困境： 一、间隔重复与分散学习遵循艾宾浩斯遗忘曲线：学习后20分钟遗忘58%，1天后遗忘66%。通过设定复习节点（如学后1天、3天、1周…...

编程日记 2025/8/10 19:26:12

conda更换清华源

1、概览 anaconda更换速度更快、更稳定的下载源，在linux环境测试通过。 2、conda源查看在修改之前可以查看下现有conda源是什么，查看conda配置信息，如下： cat ~/.condarc 可以看到你的conda源，以我的conda源举例&am…...

编程日记 2025/8/8 7:15:10

5月15日星期四今日早报简报微语报早读

5月15日星期四，农历四月十八，早报#微语早读。 1、中国至越南河内国际道路运输线路正式开通； 2、免签国1，中乌（兹别克斯坦）互免签证协定6月生效； 3、杭州“放大招”支持足球发展：足…...

编程日记 2025/8/9 13:16:48

网络损伤仪功能介绍与应用场景剖析

以下是关于网络损伤仪（Network Impairment Emulator） 的核心功能介绍及其应用场景的详细说明： 一、网络损伤仪的核心功能带宽限制（Bandwidth Throttling） 模拟不同网络带宽（如从1Mbps到10Gbps&#xff09…...

编程日记 2025/6/29 1:25:48

一、超时检测机制 1. I/O 函数超时设置 1.1 select/poll/epoll 的超时参数 select c struct timeval timeout {3, 0}; // 3秒超时 int n select(maxfd1, &readfds, NULL, NULL, &timeout); if (n 0) printf("select timeout\n"); // 超时无事件poll c …...

编程日记 2025/7/18 12:26:50

经典卷积神经网络

目录经典卷积神经网络一、卷积神经网络基础回顾二、LeNet：开启 CNN 先河三、AlexNet：突破性进展四、ZFNet：继承与优化五、GoogLeNet：引入 Inception 模块六、VggNet：深度与简单结构的融合七、ResNet&a…...

编程日记 2025/8/8 12:19:53

Reactor模型详解与C++实现

Reactor模型详解与C实现一、Reactor模型核心思想 Reactor模式是一种事件驱动的并发处理模型，核心通过同步I/O多路复用实现对多个I/O源的监听，当有事件触发时，派发给对应处理器进行非阻塞处理。关键特征： 非阻塞I/O&#xff…...

编程日记 2025/8/8 12:19:51

观测云产品更新 | 安全监测、事件中心、仪表板AI智能分析等

观测云更新安全监测新增 SIEM 功能模块：实时分析企业各类系统（如服务器、应用、网络设备）的日志和事件数据，自动发现潜在威胁，帮助团队迅速定位异常，充分发挥安全监控中枢的作用。注意：目…...

编程日记 2025/8/8 11:25:48

【HTML】个人博客页面

目录页面视图编辑页面代码解释： HTML (<body>): 使用了更加语义化的HTML5标签，例如<header>, <main>, <article>, <footer>。文章列表使用了<article>包裹，结构清晰。添加了分页导航。使用了Font…...

编程日记 2025/8/12 4:20:24

OrangePi Zero 3学习笔记（Android篇）10 - SPI和从设备

目录 1. 配置内核 2. 修改设备数 3. 修改权限 4. 验证 Zero 3的板子有2个SPI Master接口，其中SPI0接的是板载16MB大小的SPI Nor Flash，SPI1则是导出到26pin的接口上。 spi和i2c有点不同，spi是直接生成spi虚拟设备，所以在dev里…...

编程日记 2025/8/8 12:19:45

《Java 大视界——Java 大数据在智能电网分布式能源协同调度中的应用与挑战》

随着风电、光伏等分布式能源大规模接入电网，传统调度系统面临数据规模激增、响应延迟显著、多源异构数据融合困难等核心问题。本文聚焦Java生态下的大数据技术体系，深入探讨其在智能电网实时监测、负荷预测、资源优化配置等场景中的落地实践。通过分析Sp…...

编程日记 2025/8/9 16:26:51

基于正点原子探索者开发板的简易音乐播放器

1、概述本次实验的名称叫做“基于正点原子探索者开发板的简易音乐播放器”。本实验的功能框图如下： 从图上我们可以清晰的看到本实验所需的实现的功能、以及每个功能需要怎么实现。这次实验使用的是正点原子的探索者开发板，此开发板采用的MCU是STM32F4…...

编程日记 2025/8/8 10:43:29

【CF】Day59——Codeforces Round 914 (Div. 2) D

D. Set To Max 题目： Easy 思路： 简单题由于题目的数据给的很小，所以我们可以用 n 的复杂度过，那我们来观察一下我们应该怎么操作显然，如果 a[i] > b[i] 时是无法构造的，同时 a[i] b[i] 时就不用管…...

编程日记 2025/8/10 12:56:57

【Linux专栏】Linux进程间关系和守护进程

文章目录 1、进程间关系1.1 进程组1.2 组长进程 2、会话？2.1 查看会话2.2 创建会话 3、控制终端4、作业控制4.1 前台/后台进程 5、守护进程5.1 如何创建守护进程？5.2 杀掉守护进程 1、进程间关系主要描述两个名称概念：即进程组和组长进程。…...

编程日记 2025/8/10 5:38:42

AutoVACUUM (PostgreSQL) 与 DBMS_STATS.GATHER_DATABASE_STATS_JOB_PROC (Oracle) 对比

AutoVACUUM (PostgreSQL) 与 DBMS_STATS.GATHER_DATABASE_STATS_JOB_PROC (Oracle) 对比核心功能对比特性PostgreSQL AutoVACUUMOracle GATHER_DATABASE_STATS_JOB_PROC主要目的空间回收统计信息更新仅优化器统计信息收集底层机制MVCC(多版本并发控制)维护CBO(基于成本的…...

编程日记 2025/8/8 10:43:23

go依赖查询工具之godepgraph（分析main.go的依赖树）

文章目录 go依赖查询工具之godepgraph（分析main.go的依赖树）什么是服务间的隐式耦合？分析main.go的依赖树方法1. godepgraph (配合 Graphviz 可视化) - 最直观【推荐】方法2. go list go依赖查询工具之godepgraph（分析main.go的依…...

编程日记 2025/8/12 8:46:18

市场差分探头信号输出形式的一些因素考量

在5G/6G通信、新能源汽车电控等高频测量场景中，差分探头的信号输出架构直接影响测试系统的信噪比与可靠性。根据IEEE仪器与测量协会2024年度报告，单端输出方案的市场渗透率较2020年提升42%，这一趋势背后蕴含着深刻的技术变革逻辑。一、核心…...

编程日记 2025/8/12 7:52:30

SQL练习——day01

力扣——SQL练习总结 DENSE_RANK()窗口函数这是排名函数的一种，它在处理相同值时，会给相同的值分配相同的排名，并且后续的排名不会跳过。比如有三个分数并列第一，那么它们的排名都是 1，接下来的分数排名就是 2&#…...

编程日记 2025/8/8 10:43:17

断点续传使用场景，完整前后端实现示例，包括上传，下载，验证

断点续传在多个场景中非常有用，包括但不限于大文件上传、跨国或跨区域文件传输、移动设备文件传输、备份和同步以及软件更新等。接下来，我将为你提供一个基于Java的后端实现示例，结合前端逻辑来完成整个断点续传的功能，包括上传、…...

编程日记 2025/8/8 10:43:15

Xinference推理框架

概述 GitHub，官方文档。核心优势性能优化：通过vLLM、SGLang等引擎实现低延迟推理，吞吐量提升2-3倍；企业级支持：支持分布式部署、国产硬件适配及模型全生命周期管理；生态兼容：无缝对接LangC…...

编程日记 2025/8/9 18:34:31

技术更新频繁，团队如何适应变化

构建持续学习机制、引入技术雷达与预研机制、通过敏捷方法快速响应变化、推动跨团队知识协作与传承是应对技术更新频繁、团队保持适应力的核心策略。其中，构建持续学习机制尤为关键。通过制度化、场景化的学习安排，团队可以主动追踪新技术趋势&#xff…...

编程日记 2025/8/11 21:08:37

解密企业级大模型智能体Agentic AI 关键技术：MCP、A2A、Reasoning LLMs-MCP大模型上下文解析

解密企业级大模型智能体Agentic AI 关键技术：MCP、A2A、Reasoning LLMs-MCP大模型上下文解析我们首先来看一下整个MCP的一个基本的一个流程，他解决的一个问题。我们回到这里，他解决的一个问题是什么呢？他解决这个问题就是你的大…...

编程日记 2025/8/8 10:43:09

游戏代码混淆的作用与应用分析

1. 防止逆向工程核心保护对象：游戏引擎、算法（如物理模拟、AI行为树）、加密逻辑等。实例：Unity游戏使用 ConfuserEx 混淆C#代码，使反编译工具（如dnSpy）只能显示杂乱命名，难以理解逻…...

编程日记 2025/8/7 22:33:01

信息系统运行管理员：临阵磨枪版

信息系统运行管理员考试 - 全覆盖详细背诵大纲 (根据考情分析和原始材料，力求完整覆盖考点细节) 第一部分：基础知识与运维概览 Chapter 1: 信息系统运维概述 (上午题 5分) 信息： 含义：香农 - 减少随机不确定性的东西&#xff1b…...

编程日记 2025/8/8 10:43:05

PWM（脉宽调制）的配置参数[预分频器\自动重载值]的自动计算

文章目录前言一、数据结构二、二分法搜索最佳预分频器和自动重载值三、示例前言 pwm是嵌入式开发过程中很常见的一个模块，而配置pwm的过程中就少不了频率参数的计算，大多数32位机的pwm频率都由时钟、预分频器（prescaler）、自动…...

编程日记 2025/8/9 19:20:31

manuskript开源程序是面向作家的开源工具

一、软件介绍文末提供程序和源码下载 manuskript开源程序是面向作家的开源工具，Manuskript 可在 GNU/Linux、Mac OS X 和 Windows 上运行。二、Features 特征 Manuskript provides a rich environment to help writers create their first draft and then furt…...

编程日记 2025/8/9 12:21:07

antd 主题色定制

定制方案： 1. 全局定制整个应用范围内的组件都生效全局文件 theme.css :root:root {--adm-color-primary: #a062d4; } antd-mobile 中的主题变量也是在 :root 下声明的，所以在有些情况会由于优先级的问题无法覆盖。通过 :root:root 显式地让你所…...

编程日记 2025/8/8 10:43:00

召回11：地理位置召回、作者召回、缓存召回

GeoHash 召回属于地理位置召回，用户可能对附近发生的事情感兴趣。GeoHash 是一种对经纬度的编码，地图上每个单位矩形的 GeoHash 的前几位是相同的，GeoHash 编码截取前几位后，将相同编码发布的内容按时间顺序（先是时间…...

编程日记 2025/8/11 1:22:16

leetcode0767. 重构字符串-medium

1 题目：重构字符串官方标定难度：中给定一个字符串 s ，检查是否能重新排布其中的字母，使得两相邻的字符不同。返回 s 的任意可能的重新排列。若不可行，返回空字符串 “” 。示例 1: 输入: s “aab” 输出: “…...

编程日记 2025/8/8 10:42:55

vue基本介绍

Vue是一款流行的JavaScript前端框架，以下是其基本介绍： 发展历程 - 2014年，尤雨溪发布了Vue的第一个版本。 - 此后，Vue不断发展和完善，陆续发布了多个版本，功能逐渐强大，社区也日益活跃。 …...

编程日记 2025/8/8 10:42:53

【vue】【环境配置】项目无法npm run serve，显示node版本过低

解决方案：安装高版本node，并且启用高版本node 步骤： 1、查看当前版本 node -v2、配置nvm下载镜像源 1）查看配置文件位置 npm root2）找到settings.txt文件修改镜像源为： node_mirror: https://npmmirro…...

编程日记 2025/8/8 10:42:51

第35周Zookkeeper+Dubbo JDK不同版本介绍

一、JDK 新特性全解析 JDK9 - 模块化：化繁为简的魔法模块化特性：JDK9 给 Java 程序带来模块化特性，就像把一个大公司划分成多个部门，每个部门（模块）各司其职。模块比包更大，一个模块包含多个…...

编程日记 2025/8/8 10:42:49

【ORB-SLAM3】CreateNewKeyFrame()函数阅读

void Tracking::CreateNewKeyFrame() void Tracking::CreateNewKeyFrame() {// 如果局部建图线程正在初始化且没做完或关闭了,就无法插入关键帧if(mpLocalMapper->IsInitializing() && !mpAtlas->isImuInitialized())return;if(!mpLocalMapper->SetNotStop(t…...

编程日记 2025/8/10 4:40:28

腾讯开源实时语音大模型VITA-audio，92mstoken极速响应，支持多语言～

简介 VITA-Audio 是一个由腾讯优图实验室（Tencent Youtu Lab）、南京大学和厦门大学的研究人员共同开发的项目，旨在解决现有语音模型在流式生成（streaming）场景下生成第一个音频令牌（token）时的高…...

编程日记 2025/8/10 2:20:32

使用 TypeScript + dhtmlx-gantt 在 Next.js 中实现

1. 安装依赖（确保已安装） npm install dhtmlx-gantt2. 创建 pages/gantt.tsx use clientimport { useRef, useEffect } from react import { gantt } from dhtmlx-gantt import dhtmlx-gantt/codebase/dhtmlxgantt.cssinterface Task {id: number | st…...

编程日记 2025/8/8 10:42:42

web第四次课后作业--页面操作实现数据库的增删查改

一、环境配置 1. 创建一个java web（maven构建）的项目2. 配置tomcat3. 连接数据库二、页面呈现登录页面详细信息删除一条信息后更新更新后的信息三、目录结构四、代码实现 4.1 denglu.jsp <% page language"java" cont…...

编程日记 2025/8/8 10:42:40

DeepSearch：字节新一代 DeerFlow 框架

项目地址：https://github.com/bytedance/deer-flow/ 【全新的 Multi-Agent 架构设计】独家设计的 Research Team 机制，支持多轮对话、多轮决策和多轮任务执行。与 LangChain 原版 Supervisor 相比，显著减少 Tokens 消耗和 API 调用次数&#…...

编程日记 2025/8/8 10:42:38

uniapp中vue3和pinia安装依赖npm install失败

目录一、问题描述二、问题原因三、问题解析及解决方案一、问题描述用uni-app开发小程序的时候，使用了vue3pinia,安装依赖的时候发现vue和pinia的版本问题，安装失败， npm ERR! code ERESOLVE npm ERR! ERESOLVE could not resolve np…...

编程日记 2025/8/8 10:42:36

【java】synchronized关键字详解

目录一、线程同步与线程安全问题线程不安全Demo线程不安全的原因二、synchronized关键字关键字锁粒度修饰对象修饰代码块修饰方法修饰静态方法修饰类 synchronized 锁总结 synchronized加锁原理MarkWordsynchronized锁升级synchronized锁原理synchronized关键字总结其他同步…...

编程日记 2025/8/8 10:42:32