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

29-验证回文串

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后,短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。 字母和数字都属于字母数字字符。 给你一个字符串 s,如果它是 回文串 ,返回 true ;否则,返回 false 。

方法一:筛选反转法

该方法的核心思路是先筛选出字符串中的字母和数字字符,并将大写字母转换为小写字母,然后将筛选后的字符串反转,最后比较原筛选字符串和反转后的字符串是否相同。

function isPalindrome(s: string): boolean {// 筛选出字母和数字字符,并转换为小写let filtered = '';for (let char of s) {if (/[a-zA-Z0-9]/.test(char)) {filtered += char.toLowerCase();}}// 反转筛选后的字符串let reversed = filtered.split('').reverse().join('');return filtered === reversed;
}
复杂度分析
  • 时间复杂度:(O(n)),其中 n 是字符串 s 的长度。首先需要遍历一次字符串 s 进行筛选,时间复杂度为 (O(n));然后对筛选后的字符串进行反转,其长度最多为 n,时间复杂度也为 (O(n))。因此,总的时间复杂度为 (O(n))。
  • 空间复杂度:(O(n)),主要用于存储筛选后的字符串和反转后的字符串,其长度最多为 n。

方法二:双指针法

双指针法使用两个指针分别从字符串的首尾开始向中间移动,在移动过程中跳过非字母数字字符,并比较对应位置的字符是否相同。

function isPalindrome(s: string): boolean {let left = 0;let right = s.length - 1;while (left < right) {// 跳过非字母数字字符while (left < right &&!isAlphanumeric(s[left])) {left++;}while (left < right &&!isAlphanumeric(s[right])) {right--;}// 比较字符,忽略大小写if (left < right && s[left].toLowerCase()!== s[right].toLowerCase()) {return false;}left++;right--;}return true;
}function isAlphanumeric(char: string): boolean {return /[a-zA-Z0-9]/.test(char);
}
复杂度分析
  • 时间复杂度:(O(n)),其中 n 是字符串 s 的长度。两个指针最多遍历字符串一次,因此时间复杂度为 (O(n))。
  • 空间复杂度:(O(1)),只使用了常数级的额外空间,主要用于存储指针。

方法三:递归法

递归法通过不断缩小字符串的范围,递归地判断子字符串是否为回文串。

function isPalindrome(s: string): boolean {return helper(s, 0, s.length - 1);
}function helper(s: string, left: number, right: number): boolean {// 跳过非字母数字字符while (left < right &&!isAlphanumeric(s[left])) {left++;}while (left < right &&!isAlphanumeric(s[right])) {right--;}if (left >= right) {return true;}// 比较字符,忽略大小写if (s[left].toLowerCase()!== s[right].toLowerCase()) {return false;}return helper(s, left + 1, right - 1);
}function isAlphanumeric(char: string): boolean {return /[a-zA-Z0-9]/.test(char);
}
复杂度分析
  • 时间复杂度:(O(n)),其中 n 是字符串 s 的长度。递归过程中,每次递归调用都会将问题规模缩小,最多需要 (n/2) 次递归调用,因此时间复杂度为 (O(n))。
  • 空间复杂度:(O(n)),主要是递归调用栈的空间开销,最坏情况下递归深度为 (n/2),因此空间复杂度为 (O(n))。

测试用例

const testString = "A man, a plan, a canal: Panama";
console.log(isPalindrome(testString)); 

相关文章:

29-验证回文串

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后&#xff0c;短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。 字母和数字都属于字母数字字符。 给你一个字符串 s&#xff0c;如果它是 回文串 &#xff0c;返回 true &#xff1b;否则&#xf…...

(57)[HGAME 2023 week1]easyasm

nss&#xff1a;3477 [HGAME 2023 week1]easyasm 关于这个题吧&#xff0c;我还是和上一个题一样&#xff0c;我观察到了异或0x33 所以我就把result的结果跟0x33异或&#xff0c;然后我就就这样&#xff0c;做出来了...

FY-3D MWRI亮温绘制

1、FY-3D MWRI介绍 风云三号气象卫星&#xff08;FY-3&#xff09;是我国自行研制的第二代极轨气象卫星&#xff0c;其有效载荷覆 盖了紫外、可见光、红外、微波等频段&#xff0c;其目标是实现全球全天候、多光谱、三维定量 探测&#xff0c;为中期数值天气预报提供卫星观测数…...

Java集合面试题

引言 Java集合框架是Java编程中不可或缺的一部分&#xff0c;它提供了一系列用于存储和操作对象的接口和类。在Java面试中&#xff0c;集合框架的相关知识往往是必考的内容。本文将汇总一系列关于Java集合的面试题&#xff0c;帮助求职者更好地准备面试。 一、Java集合框架概…...

知识蒸馏综述Knowledge Distillation: A Survey解读

论文链接&#xff1a;Knowledge Distillation: A Survey 摘要&#xff1a;近年来&#xff0c;深度神经网络在工业界和学术界都取得了成功&#xff0c;尤其是在计算机视觉任务方面。深度学习的巨大成功主要归功于它能够扩展以对大规模数据进行编码&#xff0c;并且能够处理数十…...

ES映射知识

映射 映射类似于关系型数据库的Schema&#xff08;模式&#xff09;。 映射来定义字段列和存储的类型等基础信息。 {"mappings": {"properties": {"username": {"type": "keyword","ignore_above": 256 // 忽略…...

Spring Boot拦截器(Interceptor)与过滤器(Filter)深度解析:区别、实现与实战指南

Spring Boot拦截器&#xff08;Interceptor&#xff09;与过滤器&#xff08;Filter&#xff09;深度解析&#xff1a;区别、实现与实战指南 一、核心概念对比 1. 本质区别 维度过滤器&#xff08;Filter&#xff09;拦截器&#xff08;Interceptor&#xff09;规范层级Serv…...

Debian二次开发一体化工作站:提升科研效率的智能工具

在科研领域&#xff0c;数据处理是实验成功的关键环节之一。随着实验数据的复杂性和规模不断增加&#xff0c;传统的数据处理方法已经难以满足科研人员的需求。这时&#xff0c;一体化工作站应运而生&#xff0c;成为科研实验数据处理的 “智能大脑”。 一体化工作站&#xff…...

swift-5-汇编分析闭包本质

一、枚举、结构体、类都定义方法 方法占用对象的内存么&#xff1f; 不占用 方法的本质就是函数 方法、函数都存放在代码段&#xff0c;因为方法都是公共的&#xff0c;不管 对象一还是对对象二调用都是一样的&#xff0c;所以放在代码段&#xff0c;但是每个对象的成员不一样所…...

Linux安装升级docker

Linux 安装升级docker Linux 安装升级docker背景升级停止docker服务备份原docker数据目录移除旧版本docker安装docker ce恢复数据目录启动docker参考 安装找到docker官网找到docker文档删除旧版本docker配置docker yum源参考官网继续安装docker设置开机自启配置加速测试 Linux …...

小程序事件系统 —— 33 事件传参 - data-*自定义数据

事件传参&#xff1a;在触发事件时&#xff0c;将一些数据作为参数传递给事件处理函数的过程&#xff0c;就是事件传参&#xff1b; 在微信小程序中&#xff0c;我们经常会在组件上添加一些自定义数据&#xff0c;然后在事件处理函数中获取这些自定义数据&#xff0c;从而完成…...

推荐一些免费开源支持Vue3甘特图组件

文章目录 前言一、dhtmlxGantt二、frappe-gantt三、vue-ganttastic四、gantt-elastic五、v-gantt六、vue-gantt-schedule-timeline-calendar七、vue-gantt八、总结 前言 在现代项目管理和任务调度中&#xff0c;甘特图是一种非常实用的工具。它能够直观地展示任务的时间安排、…...

Dify 本地部署教程

目录 一、下载安装包 二、修改配置 三、启动容器 四、访问 Dify 五、总结 本篇文章主要记录 Dify 本地部署过程&#xff0c;有问题欢迎交流~ 一、下载安装包 从 Github 仓库下载最新稳定版软件包&#xff0c;点击下载~&#xff0c;当然也可以克隆仓库或者从仓库里直接下…...

nlp培训重点-5

1. LoRA微调 loader&#xff1a; # -*- coding: utf-8 -*-import json import re import os import torch import numpy as np from torch.utils.data import Dataset, DataLoader from transformers import BertTokenizer """ 数据加载 """cl…...

XWiki使用war部署在tomcat9

xwiki部署 官方文档&#xff0c;比较详细。 https://www.xwiki.org/xwiki/bin/view/Documentation/AdminGuide/Installation/InstallationWAR/ xwiki是基于java的开源知识库&#xff0c;可以替代Confluence。有多种部署方式&#xff0c;本文使用war方式部署在tomca下&#x…...

CTA策略【量化理论】

CTA策略演变史 全称&#xff1a;Commodity Trading Advisor &#xff08;商品交易顾问&#xff09; CTA最开始是指通过为客户提供期权、期货方面的交易建议&#xff0c;或者直接通过受管理的期货账户参与实际交易&#xff0c;来获得收益的机构或个人。 随着市场的发展&#…...

旋转编码器原理与应用详解:从结构到实战 | 零基础入门STM32第四十七步

主题内容教学目的/扩展视频旋转编码器电路原理&#xff0c;跳线设置&#xff0c;结构分析。驱动程序与调用。熟悉电路和驱动程序。 师从洋桃电子&#xff0c;杜洋老师 &#x1f4d1;文章目录 一、旋转编码器是什么&#xff1f;二、内部结构揭秘2.1 机械组件解剖2.2 核心部件说明…...

计算机视觉cv2入门之图像的读取,显示,与保存

在计算机视觉领域&#xff0c;Python的cv2库是一个不可或缺的工具&#xff0c;它提供了丰富的图像处理功能。作为OpenCV的Python接口&#xff0c;cv2使得图像处理的实现变得简单而高效。 示例图片 目录 opencv获取方式 图像基本知识 颜色空间 RGB HSV 图像格式 BMP格式 …...

基于Canvas和和原生JS实现俄罗斯方块小游戏

这里是一个完整的H5俄罗斯方块游戏&#xff0c;使用了 HTML CSS JavaScript (原生) 实现&#xff0c;支持基本的俄罗斯方块玩法&#xff0c;如&#xff1a; ✅ 方块自动下落 ✅ 方向键控制移动、旋转、加速下落 ✅ 方块堆叠、消行 ✅ 计分系统 在 canvas 上绘制游戏&#x…...

阿里云 QwQ-32B 模型调研文档

阿里云 QwQ-32B 模型调研文档 ——技术解析、部署实践与微调指南 一、模型概述 QwQ-32B 是阿里云开源的轻量化大语言模型,以 320 亿参数 实现与 DeepSeek-R1(6710 亿参数)相当的推理性能。其核心优势包括: 参数效率:1/20 参数量达成竞品性能,显存需求降低 70%部署灵活性…...

【玩转23种Java设计模式】结构型模式篇:组合模式

软件设计模式&#xff08;Design pattern&#xff09;&#xff0c;又称设计模式&#xff0c;是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结。使用设计模式是为了可重用代码、让代码更容易被他人理解、保证代码可靠性、程序的重用性。 汇总目录链接&…...

Eolink:专为开发者设计的API协作平台

Eolink Apikit 是一款集 API 设计、管理、自动化测试、Mock 和异常监控于一体的全生命周期智能协作平台&#xff0c;旨在提升 API 研发和管理的效率。以下是对其功能和特点的详细介绍&#xff1a; 核心功能&#xff1a; API 设计与文档管理&#xff1a;Apikit 提供了强大的 API…...

【Python】为什么要写__init__.py

文章目录 PackageA(__init__特性)应该往__init__.py里放什么东西&#xff1f;1、包的初始化2、管理包的公共接口3、包的信息 正常我们直接导入就可以执行&#xff0c;但是在package的时候&#xff0c;有一种__init__.py的特殊存在 引入moduleA.py&#xff0c;执行main.py&…...

golang 从零单排 (一) 安装环境

1.下载安装 打开网址The Go Programming Language 直接点击下载go1.24.1.windows-amd64.msi 下载完成 直接双击下一步 下一步 安装完成 环境变量自动设置不必配置 2.验证 win r 输入cmd 打开命令行 输入go version...

30-判断子序列

给定字符串 s 和 t &#xff0c;判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些&#xff08;也可以不删除&#xff09;字符而不改变剩余字符相对位置形成的新字符串。&#xff08;例如&#xff0c;"ace"是"abcde"的一个子序列&#…...

AI 驱动的软件测试革命:从自动化到智能化的进阶之路

&#x1f680;引言&#xff1a;软件测试的智能化转型浪潮 在数字化转型加速的今天&#xff0c;软件产品的迭代速度与复杂度呈指数级增长。传统软件测试依赖人工编写用例、执行测试的模式&#xff0c;已难以应对快速交付与高质量要求的双重挑战。人工智能技术的突破为测试领域注…...

深度相机进行目标物体的空间姿态(位姿)估计

利用深度相机&#xff08;如Kinect、Intel Realsense、Zed相机等&#xff09;进行目标物体的空间姿态&#xff08;位姿&#xff09;估计&#xff0c;通常结合了3D点云处理、目标识别和位姿优化算法。以下是完整的实现流程、算法选择及注意事项&#xff1a; 一、实现流程 1. 目…...

3月8日实验

拓扑&#xff1a; 需求&#xff1a; 1.学校内部的HTTP客户端可以正常通过域名www.baidu.com访问到白度网络中的HTTP服务器 2.学校网络内部网段基于192.168.1.0/24划分&#xff0c;PC1可以正常访问3.3.3.0/24网段&#xff0c;但是PC2不允许 3.学校内部路由使用静态路由&#…...

GO语言学习笔记

一、viper笔记【七米】 https://liwenzhou.com/posts/Go/viper/ 二、优雅关机和平滑重启 https://liwenzhou.com/posts/Go/graceful-shutdown/ 三、gin使用zap https://liwenzhou.com/posts/Go/zap-in-gin/ 四、flag 用于命令行传参 https://liwenzhou.com/posts/Go/flag/ 五、…...

Autosar技术栈总目录

总目录 Autosar架构理解Autosar Mcal配置开发&#xff08;TC3xx系列 基于EB&#xff09;Autosar Mcal配置开发&#xff08;S32K3xx系列 基于EB&#xff09;Autosar BSW服务开发&#xff08;基于Davinci CFG &Dev&#xff09;Makefile编译自动化脚本 持续更新中… Autosar架…...

开发指南107-谷歌内核浏览器滚动条设置

平台上统一制定了滚动条样式(仅限于webkit内核)&#xff1a;/* ------美化谷歌浏览器滚动条 开始-----------*/ ::-webkit-scrollbar{width:12px;height:12px;background-color: #E1E1E1;} ::-webkit-scrollbar-button:single-button { background-color:#E1E1E1; display: …...

25年携程校招社招求职能力北森测评材料计算部分:备考要点与误区解析

在求职过程中&#xff0c;能力测评是筛选候选人的重要环节之一。对于携程这样的知名企业&#xff0c;其能力测评中的材料计算部分尤为关键。许多求职者在备考时容易陷入误区&#xff0c;导致在考试中表现不佳。本文将深入解析材料计算部分的实际考察方向&#xff0c;并提供针对…...

Linux系统编程--线程同步

目录 一、前言 二、线程饥饿 三、线程同步 四、条件变量 1、cond 2、条件变量的使用 五、条件变量与互斥锁 一、前言 上篇文章我们讲解了线程互斥的概念&#xff0c;为了防止多个线程同时访问一份临界资源而出问题&#xff0c;我们引入了线程互斥&#xff0c;线程互斥其实…...

李沐《动手学深度学习》——14.9. 用于预训练BERT的数据集——wiki数据集问题以及存在的其他问题

问题1&#xff1a;出现"file is not a zip file" 原因是链接已经失效。 解决方法&#xff1a;打开下面链接自行下载&#xff0c;需要魔法。下载完解压到特定位置。 下载链接&#xff1a;项目首页 - Wikitext-2-v1数据包下载:Wikitext-2-v1 数据包下载本仓库提供了一…...

【英伟达AI论文】多模态大型语言模型的高效长视频理解

摘要&#xff1a;近年来&#xff0c;基于视频的多模态大型语言模型&#xff08;Video-LLMs&#xff09;通过将视频处理为图像帧序列&#xff0c;显著提升了视频理解能力。然而&#xff0c;许多现有方法在视觉主干网络中独立处理各帧&#xff0c;缺乏显式的时序建模&#xff0c;…...

深入理解 DOM 元素

深入理解 DOM 元素&#xff1a;构建动态网页的基石 在网页开发的世界里&#xff0c;DOM&#xff08;Document Object Model&#xff0c;文档对象模型&#xff09;元素宛如一座桥梁&#xff0c;连接着静态的 HTML 结构与动态的 JavaScript 交互逻辑。它让原本呆板的网页变得鲜活…...

linux如何判断进程对磁盘是随机写入还是顺序写入?

模拟工具&性能测试工具&#xff1a;fio fio参数说明&#xff1a; filename/dev/sdb1&#xff1a;测试文件名称&#xff0c;通常选择需要测试的盘的data目录。 direct1&#xff1a;是否使用directIO&#xff0c;测试过程绕过OS自带的buffer&#xff0c;使测试磁盘的结果更真…...

实现静态网络爬虫(入门篇)

一、了解基本概念以及信息 1.什么是爬虫 爬虫是一段自动抓取互联网信息的程序&#xff0c;可以从一个URL出发&#xff0c;访问它所关联的URL&#xff0c;提取我们所需要的数据。也就是说爬虫是自动访问互联网并提取数据的程序。 它可以将互联网上的数据为我所用&#xff0c;…...

[Web]get请求和post请求

Get get请求的特点是&#xff1a; 1.所有的参数都通过URL进行传递。其中传输的参数的书写的格式为?key1value1&key2value2。具体示例&#xff1a;https://example.com/search?qapple&limit10。访问的时候&#xff0c;先写/xxx&#xff0c;确定本次请求要访问的资源u…...

【落羽的落羽 C++】C++入门基础:引用,内联,nullptr

文章目录 一、引用1. 引用的概念2. 引用的特点3. 引用的使用4. const引用5. 引用和指针 二、inline内联三、nullptr 一、引用 1. 引用的概念 引用是C中的一个较为重要的概念。它是给已存在变量取的“别名”&#xff0c;编译器不会为引用变量开辟内存空间&#xff0c;它和它引…...

RabbitMQ应用问题大全(精心整理版)

前言 其实这部分知识我是整理在语雀上了&#xff0c;这里是直接复制粘贴过来的。不是很好阅读&#xff0c;可以直接点下方链接去语雀看&#xff0c;那个看的会舒服很多。 https://www.yuque.com/g/ngioig/upbg6b/fkarhyo8fpgrtyq8/collaborator/join?tokenGvlO0di8KaIfO8aF&am…...

【人工智能】卷积神经网络的奥秘:深度学习的视觉革命

卷积神经网络(CNN)是深度学习中处理图像、视频等高维数据的主流模型,因其局部特征提取和参数共享特性而效率高且效果优异。本文深入探讨了CNN的理论基础,包括卷积操作、池化层、激活函数和全连接层的数学原理,并通过LaTeX公式推导其前向传播和反向传播过程。接着,我们提供…...

掌握MiniQMT:程序化下单与撤单的高效实现

掌握MiniQMT&#xff1a;程序化下单与撤单的高效实现 &#x1f680;量化软件开通 &#x1f680;量化实战教程 在量化交易领域&#xff0c;程序化下单与撤单是实现自动化交易策略的关键环节。通过MiniQMT平台&#xff0c;我们可以高效地执行这些操作&#xff0c;从而快速响应…...

【高级篇】大疆Pocket 3加ENC编码器实现无线RTMP转HDMI进导播台

【高级篇】大疆Pocket 3加ENC编码器实现无线RTMP转HDMI进导播台 文章目录 准备工作连接设备RTMP概念ENCSHV2推流地址设置大疆Pocket 3直播设置总结 老铁们好&#xff01; 很久没写软文了&#xff0c;今天给大家带了一个干货&#xff0c;如上图&#xff0c;大疆Pocket 3加ENC编…...

Nacos学习笔记-占位符读取其他命名空间内容

Nacos当前命名空间下的配置文件需要跨命名空间读取其他配置文件的内容。可以先通过Nacos提供的API接口获取配置文件内容&#xff0c;然后解析数据将其放入环境的PropertySource中。 相关依赖包 <!-- Nacos依赖包 --> <dependency><groupId>com.alibaba.clo…...

每天五分钟深度学习框架PyTorch:使用残差块快速搭建ResNet网络

本文重点 前面我们使用pytorch搭建了残差块&#xff0c;本文我们更进一步&#xff0c;我们使用残差块搭建ResNet网络&#xff0c;当学会如何搭建残差块之后&#xff0c;搭建ResNet就会非常简单了&#xff0c;因为ResNet就是由多个残差块组成的。 残差块 残差块我们前面已经介…...

python操作java文件的一种方法

对于python操作java代码的场景来说&#xff0c;比较多的可能就是涉及加密的场景&#xff0c;尤其涉及到登录的场景&#xff0c;对于输入的账号密码可能会涉及到加密&#xff0c;如果开发告诉我们如何加密&#xff0c;那么&#xff0c;OK&#xff0c;我们可以直接通过代码去实现…...

自然语言处理:最大期望值算法

介绍 大家好&#xff0c;博主又来给大家分享知识了&#xff0c;今天给大家分享的内容是自然语言处理中的最大期望值算法。那么什么是最大期望值算法呢&#xff1f; 最大期望值算法&#xff0c;英文简称为EM算法&#xff0c;它的核心思想非常巧妙。它把求解模型参数的过程分成…...

leetcode-sql数据库面试题冲刺(高频SQL五十题)

题目&#xff1a; 197.上升的温度 表&#xff1a; Weather ---------------------- | Column Name | Type | ---------------------- | id | int | | recordDate | date | | temperature | int | ---------------------- id 是该表具有唯一值的列。 没有具有相同 recordDate …...

开发者社区测试报告(功能测试+性能测试)

功能测试 测试相关用例 开发者社区功能背景 在当今数字化时代&#xff0c;编程已经成为一项核心技能&#xff0c;越来越多的人开始学习编程&#xff0c;以适应快速变化的科技 环境。基于这一需求&#xff0c;我设计开发了一个类似博客的论坛系统&#xff0c;专注于方便程序员…...