回文子串-中心拓展
给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。
示例 1:
输入:s = “abc”
输出:3
解释:三个回文子串: “a”, “b”, “c”
示例 2:输入:s = “aaa”
输出:6
解释:6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”提示:
1 <= s.length <= 1000
s 由小写英文字母组成
计算有多少个回文子串的最朴素方法就是枚举出所有的回文子串,而枚举出所有的回文字串又有两种思路,分别是:
-
枚举出所有的子串,然后再判断这些子串是否是回文;
-
枚举每一个可能的回文中心,然后用两个指针分别向左右两边拓展,当两个指针指向的元素相同的时候就拓展,否则停止拓展。
假设字符串的长度为 n。我们可以看出前者会用 O ( n 2 ) O(n^2) O(n2) 的时间枚举出所有的子串 s [ l i . . . r i ] s[l_i...r_i] s[li...ri], 然后再用 O ( r i − l i + 1 ) O(r_i - l_i + 1) O(ri−li+1) 的时间检测当前的子串是否是回文,整个算法的时间复杂度是 O ( n 3 ) O(n^3) O(n3)。而后者枚举回文中心的是 O ( n ) O(n) O(n) 的,对于每个回文中心拓展的次数也是 O ( n ) O(n) O(n)的,所以时间复杂度是 O ( n 2 ) O(n^2) O(n2)。所以我们选择第二种方法来枚举所有的回文子串。
在实现的时候,我们需要处理一个问题,即如何有序地枚举所有可能的回文中心,我们需要考虑回文长度是奇数和回文长度是偶数的两种情况。如果回文长度是奇数,那么回文中心是一个字符;如果回文长度是偶数,那么中心是两个字符。
class Solution:def countSubstrings(self, s: str) -> int:n = len(s)ans = 0for i in range(n):#奇数长度ans += 1l, r = i - 1, i + 1while l > -1 and r < n:if s[l] == s[r]:ans += 1else:breakl -= 1r += 1#偶数长度if (i + 1) < n and s[i] == s[i+1]:ans += 1l, r = i - 1, i + 2while l > -1 and r < n:if s[l] == s[r]:ans += 1else:breakl -= 1r += 1return ansif __name__ == '__main__':s = Solution()print(s.countSubstrings("abc"))print(s.countSubstrings("aaa"))
复杂度分析
- 时间复杂度: O ( n 2 ) O(n^2) O(n2)。
- 空间复杂度: O ( 1 ) O(1) O(1)。
复杂度更低的方法参考:https://leetcode.cn/problems/palindromic-substrings/solution/hui-wen-zi-chuan-by-leetcode-solution/
相关文章:
回文子串-中心拓展
给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。 具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不…...

2023.8各大浏览器11家对比:Edge/Chrome/Opera/Firefox/Tor/Vivaldi/Brave,安全性,速度,体积,内存占用
测试环境:全默认设置的情况下,均在全新的系统上进行测试,系统并未进行任何改动,没有杀毒软件,浏览器进程全部在后台,且为小窗模式,小窗分辨率均为浏览器厂商默认缩放大小(变量不唯一)࿰…...

python中的matplotlib画散点图(数据分析与可视化)
python中的matplotlib画散点图(数据分析与可视化) import numpy as np import pandas as pd import matplotlib.pyplot as pltpd.set_option("max_columns",None) plt.rcParams[font.sans-serif][SimHei] plt.rcParams[axes.unicode_minus]Fa…...

2023前端面试笔记 —— HTML5
系列文章目录 内容链接2023前端面试笔记HTML5 文章目录 系列文章目录前言一、HTML 文件中的 DOCTYPE 是什么作用二、HTML、XML、XHTML 之间有什么区别三、前缀为 data- 开头的元素属性是什么四、谈谈你对 HTML 语义化的理解五、HTML5 对比 HTML4 有哪些不同之处六、meta 标签有…...

【LeetCode】面试题总结 消失的数字 最小k个数
1.消失的数字 两种思路 1.先升序排序,再遍历并且让后一项与前一项比较 2.转化为数学问题求等差数列前n项和 (n的大小为数组的长度),将根据公式求得的应有的和数与数组中实际的和作差 import java.util.*; class Solution {public …...
导入功能importExcel (现成直接用)
1. 实体类字段上加 Excel(name "xxx"), 表示要导入的字段 Excel(name "用户名称")private String nickName; 2. controller (post请求) /*** 导入用户数据** param file 文件* param updateSupport 是否更新支持,如果已存在,则进…...

cvc-complex-type.2.4.a: 发现了以元素 ‘base-extension‘ 开头的无效内容。应以 ‘{layoutlib}‘ 之一开头
不能飞的猪只是没用的猪。 —— 宫崎骏 《红猪》 常见的1种case 记录一下,新电脑安装android studio导入公司那些gradle还是5.5左右的工程以后,各种不适应。编译问题出现了。老电脑都是好好的。 cvc-complex-type.2.4.a: 发现了以元素 ‘base-extensi…...
cortex-A7核IIC实验
iic.h: #ifndef __IIC_H__ #define __IIC_H__ #include "stm32mp1xx_gpio.h" #include "stm32mp1xx_rcc.h"/* 通过程序模拟实现I2C总线的时序和协议* GPIOF ---> AHB4* I2C1_SCL ---> PF14* I2C1_SDA ---> PF15** */#define SET_SDA_…...
task.run()和 await task.run() 区别 await 运行机制
Task.Run() 和 await Task.Run() 都涉及异步编程,但它们在使用场景和效果上有一些区别。1. **Task.Run():**- Task.Run() 是一个用于在后台线程上执行代码块的方法。它将指定的代码块包装在一个新的Task中,并在后台线程上运行。它不会阻塞调用…...

LeetCode面试经典150题(day 2)
26. 删除有序数组中的重复项 难度:简单 给你一个 升序排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。 考虑 nums 的唯…...

阿里云机器学习PAI全新推出特征平台 (Feature Store),助力AI建模场景特征数据高效利用
推荐算法与系统在全球范围内已得到广泛应用,为用户提供了更个性化和智能化的产品推荐体验。在推荐系统领域,AI建模中特征数据的复用、一致性等问题严重影响了建模效率。阿里云机器学习平台 PAI 推出特征平台(PAI-FeatureStore) 。…...

网络安全工具和资源推荐: 介绍网络安全领域中常用的工具、框架、资源和学习资料
章节1: 前言 随着数字化时代的不断深入,网络安全的重要性愈发凸显。在这个信息爆炸的时代,我们必须保护个人隐私、敏感数据以及网络基础设施免受各种威胁。本文将为您介绍一些网络安全领域中常用的工具、框架、资源和学习资料,帮助您更好地入…...
『C语言入门』探索C语言函数
文章目录 导言一、函数概述定义与作用重要性 二、函数分类库函数自定义函数定义使用好处 三、函数参数实际参数(实参)形式参数(形参)内存分配 四、函数调用传值调用传址调用 五、函数嵌套调用与链式访问嵌套调用链式访问 六、函数…...

Django基础3——视图函数
文章目录 一、基本了解1.1 Django内置函数1.2 http请求流程 二、HttpRequest对象(接受客户端请求)2.1 常用属性2.2 常用方法2.3 服务端接收URL参数2.4 QueryDict对象2.5 案例2.5.1 表单GET提交2.5.2 表单POST提交2.5.3 上传文件 三、HttpResponse对象&am…...
python 基础篇 day 4 选择结构—— if 结构
文章目录 if 基础结构单 if 语句if-else 语句if-elif-else 语句嵌套的 if 语句 if 进阶用法使用比较运算符使用逻辑运算符使用 in 关键字range() 函数使用 is 关键字使用 pass 语句 三目运算符语法例子注意补充举例注意 if 基础结构 单 if 语句 if 条件: 执行条件为真时的代码…...

科技赋能,教育革新——大步迈向体育强国梦
在 "全民健身"、"体育强国建设"战略的推进下,体育考试成绩被纳入重要升学考试且分值不断提高,体育科目的地位逐步上升到前所未有的高度,在此趋势下,体育教学正演变出更多元化、个性化的需求。然而现实中却面临…...
【秋招基础】后端开发——笔面试常见题目
综述: 💞目的:本系列是个人整理为了秋招算法的,整理期间苛求每个知识点,平衡理解简易度与深入程度。 🥰来源:材料主要源于网上知识点进行的,每个代码参考热门博客和GPT3.5࿰…...

自定义loadbalance实现feignclient的自定义路由
自定义loadbalance实现feignclient的自定义路由 项目背景 服务A有多个同事同时开发,每个同事都在dev或者test环境发布自己的代码,注册到注册中心有好几个(本文nacos为例),这时候调用feign可能会导致请求到不同分支的服务上面,会…...

论文笔记:从不平衡数据流中学习的综述: 分类、挑战、实证研究和可重复的实验框架
0 摘要 论文:A survey on learning from imbalanced data streams: taxonomy, challenges, empirical study, and reproducible experimental framework 发表:2023年发表在Machine Learning上。 源代码:https://github.com/canoalberto/imba…...
C#设计模式六大原则之--迪米特法则
设计模式六大原则是单一职责原则、里氏替换原则、依赖倒置原则、接口隔离原则、迪米特法则、开闭原则。它们不是要我们刻板的遵守,而是根据实际需要灵活运用。只要对它们的遵守程度在一个合理的范围内,努为做到一个良好的设计。本文主要介绍一下.NET(C#)…...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
pam_env.so模块配置解析
在PAM(Pluggable Authentication Modules)配置中, /etc/pam.d/su 文件相关配置含义如下: 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块,负责验证用户身份&am…...

USB Over IP专用硬件的5个特点
USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中,从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备(如专用硬件设备),从而消除了直接物理连接的需要。USB over IP的…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
Leetcode33( 搜索旋转排序数组)
题目表述 整数数组 nums 按升序排列,数组中的值 互不相同 。 在传递给函数之前,nums 在预先未知的某个下标 k(0 < k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现指南针功能
指南针功能是许多位置服务应用的基础功能之一。下面我将详细介绍如何在HarmonyOS 5中使用DevEco Studio实现指南针功能。 1. 开发环境准备 确保已安装DevEco Studio 3.1或更高版本确保项目使用的是HarmonyOS 5.0 SDK在项目的module.json5中配置必要的权限 2. 权限配置 在mo…...