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

【LeetCode】【算法】647. 回文子串

LeetCode 647.回文子串

题目描述

给你一个字符串s,请你统计并返回这个字符串中回文子串的数目
回文字符串 是正着读和倒过来读一样的字符串。
子字符串是字符串中的由连续字符组成的一个序列。

思路

思路:中心拓展法
中心拓展法的意思是说:

  1. 假如字符串长度为奇数,从中间的某一位出发,同时向左和向右,能够得到同样的结果,回文子串数量++
  2. 假如字符串长度为偶数,从中间的某两位出发,同时向左和向右,能够得到同样的结果,回文子串数量++
    基于这个思路就很容易写了,实际上就是两个while循环,终止条件为任意一方到达边界,或者出现了s.charAt(i) != s.charAt(j)的情况,就结束while循环;否则指针一直移动,回文子串数量一直++

代码

class Solution {public int countSubstrings(String s) {int count = 0;for (int i = 0; i < s.length(); i++) {// 中心拓展法int cur_count = 0;// 向两边拓展// 如果像下面这种写法,就只是以i作为中心了,事实上并不止这一种情况,还有l=i,r=i+1作为回文中心(即回文子串长度为偶数的情况)int l = i;int r = i;while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {cur_count++;l--;r++;}l = i;r = i + 1;while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {cur_count++;l--;r++;}count += cur_count;}return count;}
}

相关文章:

【LeetCode】【算法】647. 回文子串

LeetCode 647.回文子串 题目描述 给你一个字符串s&#xff0c;请你统计并返回这个字符串中回文子串的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串是字符串中的由连续字符组成的一个序列。 思路 思路&#xff1a;中心拓展法 中心拓展法的意思是说&#xf…...

介绍6种常见的基于知识图谱推荐算法的类型和各自的优缺点

基于知识图谱的推荐算法有多种&#xff0c;每种算法各有其优点和缺点。下面是一些常见的基于知识图谱的推荐算法及其分析&#xff1a; 基于邻域的协同过滤&#xff08;Collaborative Filtering&#xff09; 描述&#xff1a;通过分析用户之间的相似性或项目之间的相似性来进行…...

使用python拟合二元曲线系数

python import numpy as np import pandas as pd注&#xff1a; xlsx 表格中 有 压力P&#xff0c;流量值Q&#xff0c;温度值 K&#xff1b; df pd.read_excel("./i100-10000slm.xlsx",usecols[p1,molboxQm,Dek]) #print(df.head())#column_data df[p1] # 获取行数…...

go 集成viper 配置管理

安装viper go get github.com/spf13/viper 配置文件 读取配置文件 package confimport ("fmt""github.com/spf13/viper" )func Properties() {viper.SetConfigName("application")viper.SetConfigType("yml")viper.AddConfigPath(&q…...

Java:数据结构-再谈String类

字符串常量池 首先我们来思考这段代码&#xff0c;为什么运行结果一个是true&#xff0c;一个是false呢&#xff1f; public class Test {public static void main(String[] args) {String s1"123";String s2"123";String s3new String("555")…...

斗破QT编程入门系列之二:GUI应用程序设计基础:UI文件(四星斗师)

斗破Qt目录&#xff1a; 斗破Qt编程入门系列之前言&#xff1a;认识Qt&#xff1a;Qt的获取与安装&#xff08;四星斗师&#xff09; 斗破QT编程入门系列之一&#xff1a;认识Qt&#xff1a;初步使用&#xff08;四星斗师&#xff09; 斗破QT编程入门系列之二&#xff1a;认识…...

微服务实战系列之玩转Docker(十八)

导览 前言Q&#xff1a;如何保障容器云环境下etcd集群的数据安全一、安全机制身份认证必学必看1. 启动参数2. 授权命令3. 开启认证 二、应用实践1. 访问容器2. 查看认证是否开启3. 查看是否已创建用户4. 创建用户5. 开启认证6. 验证是否开启7. 验证数据 结语系列回顾 前言 etc…...

Javascript 获取设备信息 工具

JS获取设备信息(操作系统信息、地理位置、UUID、横竖屏状态、设备类型、网络状态、浏览器信息、生成浏览器指纹、日期、生肖、周几等) Get Device Info Online GitHub - skillnull/DeviceJs: JS获取设备信息(操作系统信息、地理位置、UUID、横竖屏状态、设备类型、网络状态、浏…...

基于开源 AI 智能名片、S2B2C 商城小程序的用户获取成本优化分析

摘要&#xff1a;本文围绕用户获取成本&#xff08;CAC&#xff09;这一关键指标展开深入剖析&#xff0c;详细阐述其计算方式&#xff0c;并紧密结合开源 AI 智能名片与 S2B2C 商城小程序的独特性质&#xff0c;从多个维度探讨如何通过挖掘新的获客渠道、巧妙运用私域流量池等…...

仿真APP助力汽车零部件厂商打造核心竞争力

汽车零部件是汽车工业的基石&#xff0c;是构成车辆的基础元素。一辆汽车通常由上万件零部件组成&#xff0c;包括发动机系统、传动系统、制动系统、电子控制系统等&#xff0c;它们共同确保了汽车的安全、可靠性及高效运行。 在汽车产业快速发展的今天&#xff0c;汽车零部件…...

vue实现websocket实时短消息通知

1、原理 websocket就是通过服务器向客户端推送消息&#xff0c;客户端也可以主动向服务器发送消息&#xff0c;是真正的双向平等对话&#xff0c;是一种长连接&#xff0c;只需要通过一次请求进行初始化。 2、事件 onopen: 客户端和服务器建立连接后触发&#xff0c;被称为客…...

tinymce扩展功能:1、行高、段落间距、格式刷;2、视频上传进度条;3、对复制的图片设置尺寸

tinymce扩展功能&#xff1a;1、行高、段落间距、格式刷&#xff1b;2、视频上传进度条&#xff1b;3、对复制的图片设置尺寸 一、需求描述二、行高、段落间距、格式刷插件三、实现视频上传的进度条、对复制的图片设置尺寸 一、需求描述 使用技术&#xff1a; vue2 tinymce5.…...

计算机毕业设计Python+图神经网络手机推荐系统 手机价格预测 手机可视化 手机数据分析 手机爬虫 Django Flask Spark 知识图谱

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 作者简介&#xff1a;Java领…...

WPF的<ContentControl>控件

在WPF&#xff08;Windows Presentation Foundation&#xff09;中&#xff0c;<ContentControl>是一个非常有用的控件&#xff0c;它允许你将内容放入一个控件中&#xff0c;这个内容可以是任何对象。ContentControl的主要特点是它有一个Content属性&#xff0c;你可以将…...

Python并发编程——multiprocessing

目录 1. 引言1.1 并发与并行的区别 2. 多进程开发2.1 Process 类的常用方法2.2 进程的生命周期与同步 3. 进程之间的数据共享3.1 使用 Value 和 Array3.2 使用 Manager 实现高级数据共享 4. 进程锁4.1 更复杂的锁应用4.2 锁的死锁与避免4.3 信号量与条件变量 5. 进程池5.1 imap…...

智能家居的未来:AI让生活更智能还是更复杂?

内容概要 智能家居的概念源于将各种家居设备连接到互联网&#xff0c;并通过智能技术进行控制和管理。随着人工智能的迅速发展&#xff0c;这一领域也迎来了前所未有的机遇。从早期简单的遥控器到如今可以通过手机应用、语音助手甚至是环境感应进行操作的设备&#xff0c;智能…...

【物联网技术】ESP8266 WIFI模块在AP模式下作为TCP服务器与多个电脑/手机网络助手(TCP客户端)通信——TCP数据透传

前言:完成ESP8266 WIFI模块在AP模式下作为TCP服务器与多个电脑/手机网络助手(TCP客户端)通信——实现TCP数据透传 AP模式,通俗来说模块可以发出一个WIFI热点提供给电脑/手机连接。 TCP服务端,通俗来说就是模块/单片机作为服务器,可以接收多个客户通道的连接。 本…...

十五:java web(7)-- Spring Boot

目录 1. Spring Boot 简介 1.1 简介 1.2 Spring Boot 的特点 1.3 Spring Boot 和 Spring 的关系 2. Spring Boot 快速入门 2.1 创建第一个 Spring Boot 项目 3. Spring Boot 配置管理 3.1 application.properties 和 application.yml 配置 这两种都可以 好像现在更推荐…...

洛谷每日一题——P1036 [NOIP2002 普及组] 选数、P1045 [NOIP2003 普及组] 麦森数(高精度快速幂)

P1036 [NOIP2002 普及组] 选数 题目描述 [NOIP2002 普及组] 选数 - 洛谷 运行代码 #include <stdio.h> int n, k, a[25], t; int ss(int b) {int i;if (b < 2)return 0;for (i 2; i * i < b; i)if (b % i 0)return 0;return 1; } void dfs(int num, int sum, …...

OpenHarmony开源鸿蒙

OpenHarmony_百度百科 2024年4 月 1 日&#xff0c;开源鸿蒙 OpenHarmony 4.1 Release 版本于昨日发布&#xff0c;开发套件同步升级到 API 11 Release...

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

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

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...