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

剑指Offer|LCR 014. 字符串的排列

LCR 014. 字符串的排列

给定两个字符串 s1s2,写一个函数来判断 s2 是否包含 s1 的某个变位词。

换句话说,第一个字符串的排列之一是第二个字符串的 子串

示例 1:

输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").

示例 2:

输入: s1= "ab" s2 = "eidboaoo"
输出: False

提示:

  • 1 <= s1.length, s2.length <= 104
  • s1s2 仅包含小写字母

法1:滑动窗口

分析:

建立一个hash表,键是26个字母,对应值是各自出现的次数,为方便键0就代表a,1代表b这样。

看例子:s1 = "ab" s2 = "eidbaooo"

在这里插入图片描述

表格中没写的都是填充0。接着遍历后面的s2

在这里插入图片描述

i=2,遍历s2中的d,
counts[s2.charCodeAt(i) - ‘a’.charCodeAt(0)]–=counts[d-a]–=counts[3]–
counts[s2.charCodeAt(i - s1.length) - ‘a’.charCodeAt(0)]++=counts[e-a]++=counts[4]++

i=3,遍历s2中的b
counts[s2.charCodeAt(i) - ‘a’.charCodeAt(0)]–=counts[b-a]–=counts[1]–
counts[s2.charCodeAt(i - s1.length) - ‘a’.charCodeAt(0)]++=counts[i-a]++=counts[8]++

i=4,遍历s2中的a
counts[s2.charCodeAt(i) - ‘a’.charCodeAt(0)]–=counts[a-a]–=counts[0]–
counts[s2.charCodeAt(i - s1.length) - ‘a’.charCodeAt(0)]++=counts[d-a]++=counts[3]++

到这,counts全都为0,就返回true

 var checkInclusion = function(s1, s2) {if (s2.length < s1.length)  return false;let counts = new Array(26).fill(0);// 初始填充 counts 数组for (let i = 0; i < s1.length; ++i) {counts[s1.charCodeAt(i) - 'a'.charCodeAt(0)]++; // s1 计数 ++counts[s2.charCodeAt(i) - 'a'.charCodeAt(0)]--; // s2 计数 --}// 检查是否已匹配if (areAllZero(counts)) {return true;}// 滑动窗口// 滑动窗口的大小始终为 s1.length。for (let i = s1.length; i < s2.length; ++i) {counts[s2.charCodeAt(i) - 'a'.charCodeAt(0)]--;counts[s2.charCodeAt(i - s1.length) - 'a'.charCodeAt(0)]++;if (areAllZero(counts)) {return true;}}
};/*** 辅助函数:检查 counts 数组是否全部为零* @param {number[]} counts* @return {boolean}*/
function areAllZero(counts) {for (let count of counts) {if (count !== 0) {return false;}}return true;
}

相关文章:

剑指Offer|LCR 014. 字符串的排列

LCR 014. 字符串的排列 给定两个字符串 s1 和 s2&#xff0c;写一个函数来判断 s2 是否包含 s1 的某个变位词。 换句话说&#xff0c;第一个字符串的排列之一是第二个字符串的 子串 。 示例 1&#xff1a; 输入: s1 "ab" s2 "eidbaooo" 输出: True 解…...

【Agent】Chatbot、Copilot与Agent如何帮助我们的提升效率?

人工智能&#xff08;AI&#xff09;技术的迅猛发展正在深刻改变我们的生活和工作方式。你是否曾想过&#xff0c;未来的工作场景会是什么样子&#xff1f;AI的崛起不仅仅是科技的进步&#xff0c;更是我们生活方式的革命。今天&#xff0c;我们将深入探讨三种主要的AI能力&…...

QT笔记- QTreeView + QFileSystemModel 当前位置的保存与恢复 #选中 #保存当前索引

保存当前位置 QString currentPath model->filePath(view->currentIndex()); // 获得当前位置路径 恢复位置 view->setCurrentIndex(model->index(currentPath)); // 设置此路径所在位置为当前位置...

OpenResty开发环境搭建

简介 OpenResty 是一个基于 Nginx的高性能 Web 平台&#xff0c;用于方便地搭建能够处理超高并发、扩展性极高的动态 Web 应用、Web 服务和动态网关。官方地址&#xff1a;http://openresty.org/cn/ 具备下列特点&#xff1a; 具备Nginx的完整功能基于Lua语言进行扩展&#…...

linux提示结构需要清理

1. df -hT 查看出问题的文件夹所在的挂载磁盘及文件格式 2. umount 挂载磁盘&#xff0c;如果提示在忙, lsof 目录查看正在使用的进程&#xff0c;将其kill掉 3. 修复磁盘 根据文件格式修复磁盘fsck.ext4 /dev/sda1 或者 xfs_repair /dev/sda1 4. 重启系统 “结构需要清理…...

【扩展卡尔曼滤波理论推导与实践】【理论】【2/3 公式推导】

目录 非线性系统泰勒展开卡尔曼滤波卡尔曼增益模型误差协方差矩阵 公式总结 本节默认你能够完整推导标准卡尔曼滤波&#xff0c;将会简化一些推导的描述。如果你还不会完整推导标准卡尔曼滤波&#xff0c;请先从 【卡尔曼滤波理论推导与实践】系列开始看起。 非线性系统 扩展…...

springboot494基于java的综合小区管理系统(论文+源码)_kaic

摘 要 如今社会上各行各业&#xff0c;都喜欢用自己行业的专属软件工作&#xff0c;互联网发展到这个时候&#xff0c;人们已经发现离不开了互联网。新技术的产生&#xff0c;往往能解决一些老技术的弊端问题。因为传统综合小区管理系统信息管理难度大&#xff0c;容错率低&am…...

深度学习blog-Transformer-注意力机制和编码器解码器

注意力机制&#xff1a;当我们看一个图像或者听一段音频时&#xff0c;会根据自己的需求&#xff0c;集中注意力在关键元素上&#xff0c;以获取相关信息。 同样地&#xff0c;注意力机制中的模型也会根据输入的不同部分&#xff0c;给它们不同的权重&#xff0c;并集中注意力在…...

敏感词 v0.24.0 新特性支持标签分类,内置实现多种策略

开源项目 敏感词核心 https://github.com/houbb/sensitive-word 敏感词控台 https://github.com/houbb/sensitive-word-admin 版本特性 大家好&#xff0c;我是老马。 敏感词标签分类一直是大家比较想要的一个功能特性&#xff0c;v0.24.0 了开始内置支持标签分类&#xff0c…...

随身 WiFi 连接 X-Wrt 共享网络与 IPv6 中继配置

本文首发于只抄博客&#xff0c;欢迎点击原文链接了解更多内容。 前言 之前分享的《随身 WiFi 通过 USB 连接路由器共享网络 扩展网络覆盖范围》介绍了随身 WiFi 通过 USB 连接到路由器共享网络&#xff0c;其中留下两个小问题没有解决&#xff1a; OpenWrt 无法识别中兴微的…...

Keil-编译按钮Translate,Build,Rebuild

在Keil编程环境中&#xff0c;有三个编译源文件相关的按钮Translate&#xff0c;Build&#xff0c;Rebuild&#xff1a; Translate 仅仅&#xff08;狭义&#xff09;编译一下当前编辑的源文件&#xff08;main.c 仅生成 main.o&#xff09;&#xff0c;并不生成最终可执行文件…...

No.1免费开源ERP:Odoo自定义字段添加到配置页中的技术分享

文 / 开源智造&#xff08;OSCG&#xff09; Odoo亚太金牌服务 在Odoo18之中&#xff0c;配置设定于管控各类系统配置层面发挥着关键之效用&#xff0c;使您能够对软件予以定制&#xff0c;以契合您特定的业务需求。尽管 Odoo 提供了一组强劲的默认配置选项&#xff0c;然而有…...

Linux 更改Jenkins使用其他账户启动

Linux 更改Jenkins使用其他账户启动 步骤一&#xff1a;修改 Jenkins 配置文件1. 编辑 Jenkins 的 systemd 服务文件&#xff1a;2. 在编辑器中添加以下内容&#xff1a;3. 保存并退出编辑器 步骤二&#xff1a;更改 Jenkins 目录的权限步骤三&#xff1a;重新加载 systemd 配置…...

wordpres当前分类调用父分类的名称和链接

在WordPress中&#xff0c;如果你想在当前分类页面调用并显示父分类的名称和链接&#xff0c;你可以使用以下代码片段&#xff1a; <?php // 获取当前分类的ID $cat_id get_queried_object_id();// 获取当前分类的父分类ID $parent_id get_term($cat_id, category)->…...

TCP客户端模拟链接websocket服务端发送消息(二)

兄弟们&#xff0c;我来填坑了&#xff0c;o(╥﹏╥)o o(╥﹏╥)o o(╥﹏╥)o o(╥﹏╥)o o(╥﹏╥)o o(╥﹏╥)o&#xff0c;前几天写了个tcp模拟websocket客户端的以为完成&#xff0c;后面需要发送消息给服务端&#xff0c;以为简单不就是一个发送消息么&#xff0c;这不是一…...

操作系统之同步与互斥的基本概念

1. 同步的基本概念 定义&#xff1a;同步是指在多个并发执行的进程或线程之间协调其行为&#xff0c;以使它们能够正确地相互合作。在计算机科学中&#xff0c;同步通常指对共享资源进行访问控制&#xff0c;以避免竞争条件和死锁等问题。 实现方式&#xff1a;为了实现同步&a…...

详细讲解axios封装与api接口封装管理

一、axios封装 axios是基于promise的http客户端&#xff0c;用于浏览器和nodejs发送http请求 &#xff0c;对它进行封装主要是为了统一管理请求配置和处理请求和响应的通用逻辑等。以下是常用的封装逻辑和要点 1&#xff1a;引入axios相关依赖 首先引用项目中的axios库&…...

API 接口如何确保数据的安全?

在API接口的对接中&#xff0c;确保数据的安全性是至关重要的。以下是一些关键措施&#xff0c;可以帮助实现这一目标&#xff1a; 一、认证与授权 API密钥&#xff1a;为每个调用方分配唯一的API密钥&#xff0c;客户端在请求时携带该密钥&#xff0c;服务器端验证其有效性。…...

HAL库STM32硬件IIC驱动数字电位器MCP4017

目录 一、芯片特性 二、硬件电路 三、工程搭建 四、IIC硬件地址 五、驱动程序 项目需要&#xff0c;最近用到了一个IIC接口的数字电位器&#xff0c;型号&#xff1a;MCP4017T-502E。对应阻值5K&#xff0c;使用STM32G030F6的硬件IIC驱动&#xff0c;发现简单的不得了&…...

「地平线」副总裁余轶南与「理想汽车」智驾产品总监赵哲伦联手创业,入局具身智能赛道!

小编早期文章&#xff1a;智驾领域从业者&#xff0c;疯狂涌入人形机器人赛道&#xff01;就有提到智驾领域从业者入局人形机器人赛道是趋势并分析原因。 之前媒体报道的智驾芯片上市公司【地平线】创始成员、副总裁、前软件平台产品线总裁余轶南&#xff08;博士&#xff09;…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...