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

剑指 Offer II 020. 回文子字符串的个数

题目链接

剑指 Offer II 020. 回文子字符串的个数 mid

题目描述

给定一个字符串 s,请计算这个字符串中有多少个回文子字符串。

具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。

示例 1:

输入:s = “abc”
输出:3
解释:三个回文子串: “a”, “b”, “c”

示例 2:

输入:s = “aaa”
输出:6
解释:6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

提示:

  • 1<=s.length<=10001 <= s.length <= 10001<=s.length<=1000
  • s由小写英文字母组成

分析:

使用 动态规划 解决本题。

我们定义 f(i,j)f(i,j)f(i,j)s[i - 1,j - 1]区间是否为回文串。

  • s[i−1]≠s[j−1]s[i-1] \neq s[j-1]s[i1]=s[j1],那么 f[i][j] = false.
  • s[i−1]=s[j−1]s[i-1] = s[j-1]s[i1]=s[j1]
    • 如果 j−i≤1j - i \leq1ji1s[i][j] = true(相当于指针 ij指向了一个字符'a',或者指向了两个相连且相等的字符 'aa')。
    • 如果 f[i-1][j+1] = trues[i][j] = true

时间复杂度: O(n2)O(n^2)O(n2)

C++代码:

class Solution {
public:int countSubstrings(string s) {int n = s.size();bool f[n+1][n+1];memset(f,false,sizeof f);int ans = 0;for(int i = n;i >= 1;i--){for(int j = i;j <= n;j++){if((s[i-1] == s[j - 1]) && (j - i <= 1 || f[i+1][j-1])){ans++;f[i][j] = true;}}}return ans;}
};

Java代码:

class Solution {public int countSubstrings(String s) {int n = s.length();boolean[][] f = new boolean[n+1][n+1];int ans = 0;for(int i = n;i >= 1;i--){for(int j = i;j <= n;j++){if((s.charAt(i-1) == s.charAt(j-1)) && (j - i <= 1 || f[i+1][j-1])){ans++;f[i][j] = true;}}}return ans;}
}

相关文章:

剑指 Offer II 020. 回文子字符串的个数

题目链接 剑指 Offer II 020. 回文子字符串的个数 mid 题目描述 给定一个字符串 s&#xff0c;请计算这个字符串中有多少个回文子字符串。 具有不同开始位置或结束位置的子串&#xff0c;即使是由相同的字符组成&#xff0c;也会被视作不同的子串。 示例 1&#xff1a; 输入…...

Python实现多键字典

实现背景 在许多场景中&#xff0c;有时需要通过多种信息来获取某个特定的值&#xff0c;而各种编程语言&#xff08;包括Python&#xff09;使用的字典&#xff08;Dict&#xff09;数据结构通常只支持单个键值寻值key-val对&#xff0c;即“一对一”&#xff08;一个键对应一…...

【python socket】实现websocket服务端

一、获取握手信息首先通过如下代码&#xff0c;我们使用socket来获取客户端的握手信息import socketsock socket.socket(socket.AF_INET, socket.SOCK_STREAM) sock.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1) sock.bind(("127.0.0.1", 8002)) sock.li…...

PANGO的CFG那些事

先来看位于VCCIOCFG这个bank上引脚&#xff0c; MODE JTAG时&#xff0c;MODExxx. except 3’b000. 禁止设置为3’b000. Slave Parallel时&#xff0c;MODE 3’b110&#xff0c;不常用。 Slave Serial时&#xff0c;MODE 3’b111&#xff0c;不常用。 Master SPI 时&…...

路由协议(OSPF、ISIS、BGP)实验配置

目录 OSPF基础实验 建立OSPF邻居 配置虚连接 配置接口的网络类型 配置特殊区域 配置路由选路 配置路由过滤 ISIS基础实验配置 配置ISIS邻居建立 配置认证 配置路由扩散 配置路由过滤 配置定时器 BGP基础实验配置 建立BGP对等体 建立IBGP对等体 建立EBGP对等体…...

Python可变对象与不可变对象的浅拷贝与深拷贝

前言 本文主要介绍了python中容易面临的考试点和犯错点&#xff0c;即浅拷贝与深拷贝 首先&#xff0c;针对Python中的可变对象来说&#xff0c;例如列表&#xff0c;我们可以通过以下方式进行浅拷贝和深拷贝操作&#xff1a; import copya [1, 2, 3, 4, [a, b]]b a …...

滑模控制(Sliding mode control)快速入门

0. 简介 最近作者受到邀请&#xff0c;让我帮忙给刚入门的学弟讲讲滑模控制。可是作者也不知道怎么向未入门的学弟讲解这些基础知识&#xff0c;所以作者翻了翻近几年写的很好的文章以及视频。综合起来&#xff0c;来总结出一套比较基础&#xff0c;且适用于初学者的文章吧。这…...

golang的垃圾回收详解

golang的垃圾回收详解 一、三色标记法 作为一门现代化的语言&#xff0c;golang与java一样&#xff0c;都在语言中内置了垃圾回收的功能&#xff0c;不需要程序员自己去回收堆内存。而垃圾回收中&#xff0c;最重要的两个部分就是垃圾检测算法以及垃圾回收算法。垃圾检测算法决…...

线上负载过高排查(top/vmstat/ifstat/free/df)

目录 一、五大命令 二、故障排查步骤 1、top命令找出CPU占比最高的 2、ps -ef 或者 jps -l进一步定位 3、ps -mp位到具体线程或者代码 4、jstack精准定位到错误的地方 本文通过学习&#xff1a;周阳老师-尚硅谷Java大厂面试题第二季 总结的LinuxJDK命令操作相关的笔记 一…...

Java的注解(Annotation)

Java 注解&#xff08;Annotation&#xff09;又称 Java 标注&#xff0c;是 JDK5.0 引入的一种注释机制。Java 中的类、构造器、方法、成员变量、参数等都可以被注解进行标注。例如JUnit单元测试中的Test方法&#xff0c;可以使得方法直接运行。JUnit单元测试Test单元测试是针…...

信息系统项目管理师:配置管理

配置管理指的是在一个系统或软件中对配置项的管理&#xff0c;包括对配置项的定义、存储、跟踪和修改等一系列活动。配置项可以是硬件设备、软件组件、系统设置、网络配置等&#xff0c;配置管理旨在确保在不同时间点或环境下系统或软件的配置项的正确性和一致性。通过配置管理…...

web餐饮开源程序

简介 一款专门针对餐饮行业而开发桌面应用程序 技术 借助Panuon.UI.Silver控件库&#xff0c;开发的一款餐饮软件。 运行环境&#xff1a;.NETFramework,Versionv4.8。 运行数据库&#xff1a;MySql。 ORM框架&#xff1a;SqlSugar。 第三方插件&#xff1a;Panuon.UI.Silv…...

28个案例问题分析---027---单表的11个Update接口--MyBatis

一&#xff1a;背景介绍 项目开发中。我们使用的是MyBatis&#xff0c;在MyBatis的xml文件里&#xff0c;两个表的更新功能&#xff0c;写了足足11个更新接口&#xff0c;毫无复用的思想 这种方式可以正常的实现功能&#xff0c;但是没有复用&#xff0c;无论是从时间上还是维…...

大数据开发治理平台 DataWorks

序言学习下阿里DataWorks的设计理念以及要做的事情cuiyaonan2000163.com参考文档:https://www.aliyun.com/product/bigdata/idehttps://help.aliyun.com/document_detail/73015.htmlhttps://help.aliyun.com/document_detail/324149.html ----数据治理LaunchDataWorks基于阿里云…...

Xshell的下载、使用、配置【ssh、telnet、串口】

目录 一、概述 二、Xshell的使用  2.1 Xshell使用ssh协议远程连接Linux主机或服务器  2.2 Xshell使用telnet协议远程连接Linux开发板  2.3 Xshell使用SERIAL协议远程连接Linux开发板 三、Xshell常用配置  3.1 配置默认会话属性 一、概述 Xshell是由NetSarang公司开发的强大…...

C++回顾(七)—— 面向对象模型

7.1 静态成员变量和静态成员函数 7.1.1 静态成员变量 关键字 static 可以用于说明一个类的成员&#xff1b;静态成员提供了一个同类对象的共享机制&#xff1b;把一个类的成员说明为 static 时&#xff0c;这个类无论有多少个对象被创建&#xff0c;这些对象共享这个 static …...

开源监控服务uptime-kuma

好久没写文章了&#xff0c;刚好最近用了一个开源的监控服务&#xff0c;感觉蛮有意思的&#xff0c;记录一下 &#xff08;一&#xff09;安装 uptime-kuma安装方式有几种&#xff0c;这里当然是选择大家都爱的docker,一条命令搞定 docker run -d --restartalways -p 3001:…...

JavaScript混淆技术:了解其核心原理和常用手段

当今互联网时代&#xff0c;JavaScript已经成为了web前端开发的重点技术之一。其中&#xff0c;JavaScript代码的安全性问题一直是关注的焦点。为了保护JavaScript代码的安全性&#xff0c;很多人对其进行加密处理&#xff0c;众所周知&#xff0c;对于单纯的加密算法&#xff…...

大型医院云HIS系统:采用前后端分离架构,前端由Angular语言、JavaScript开发;后端使用Java语言开发 融合B/S版电子病历系统

一套医院云his系统源码 采用前后端分离架构&#xff0c;前端由Angular语言、JavaScript开发&#xff1b;后端使用Java语言开发。融合B/S版电子病历系统&#xff0c;支持电子病历四级&#xff0c;HIS与电子病历系统均拥有自主知识产权。 文末卡片获取联系&#xff01; 基于云计…...

SAP UI5 Upload/Download file through NetWeaver Gateway

1、创建 SEGW对象 2、创建Entity Type 要把Media 标识打上 3、 激活对象然后到DPC Class的扩展对象里面重定义 /IWBEP/IF_MGW_APPL_SRV_RUNTIME~GET_STREAM /IWBEP/IF_MGW_APPL_SRV_RUNTIME~CREATE_STREAM /IWBEP/IF_MGW_APPL_SRV_RUNTIME~UPDATE_STREAM METHOD /iwbep/if_m…...

如何评估你的 Agent 是否真的在思考

重新审视智能:如何用科学、工程与可量化标准评估你的 Agent 是否真的在思考 警告:全文约 12.7 万字,由 8 个核心章节组成,单节最低字数超过 1.1 万字。建议分段阅读,配合工具与项目实践,可获得最佳学习效果。 0. 章节导航与阅读建议 为了帮助不同背景的读者(从 AI 产品…...

书匠策AI:2026年写毕业论文的“开挂说明书“——一个教育博主的硬核拆解

你离毕业&#xff0c;可能只差一个书匠策AI的距离 各位还在和毕业论文"互相折磨"的同学们&#xff0c;我是一个专门教人写论文的教育博主。今天不聊理论&#xff0c;不灌鸡汤&#xff0c;直接给你们安利一个我最近扒了很久的工具——书匠策AI&#xff08;官网 官网直…...

别再踩坑了!Ubuntu 20.04下用Docker一键编译OLLVM 4.0(附完整Dockerfile)

基于Docker的OLLVM 4.0高效编译指南&#xff1a;Ubuntu 20.04最佳实践 在移动安全与逆向工程领域&#xff0c;OLLVM作为代码混淆的黄金标准工具链&#xff0c;其环境搭建一直是开发者面临的痛点。传统源码编译方式需要处理复杂的依赖关系、版本冲突和系统污染风险&#xff0c;而…...

保姆级教程:用ISO镜像给Vcenter 6.7 U3e无损升级到7.0(附每一步截图和注意事项)

从vCenter 6.7 U3e到7.0的无损升级实战指南 在虚拟化运维领域&#xff0c;vCenter的版本迭代往往意味着性能提升和功能增强。对于仍在使用6.7版本的管理员而言&#xff0c;升级到7.0不仅能获得更高效的资源管理能力&#xff0c;还能体验更直观的操作界面。本文将详细解析从6.7 …...

高通Android音频HAL揭秘:从AudioFlinger到libaudiohal.so的加载与设备打开流程

高通Android音频HAL深度解析&#xff1a;从框架设计到硬件交互的全链路实现 在Android系统的多媒体生态中&#xff0c;音频子系统扮演着至关重要的角色。作为连接应用层与物理硬件的桥梁&#xff0c;音频硬件抽象层&#xff08;HAL&#xff09;的设计直接决定了设备的音频性能…...

ETS2LA:欧洲卡车模拟2自动驾驶插件的完整指南

ETS2LA&#xff1a;欧洲卡车模拟2自动驾驶插件的完整指南 【免费下载链接】Euro-Truck-Simulator-2-Lane-Assist Plugin based interface program for ETS2/ATS. 项目地址: https://gitcode.com/gh_mirrors/eur/Euro-Truck-Simulator-2-Lane-Assist 你是否曾经在长途运输…...

微信小程序逆向工程:wxappUnpacker技术深度解析与实战指南

微信小程序逆向工程&#xff1a;wxappUnpacker技术深度解析与实战指南 【免费下载链接】wxappUnpacker forked from https://github.com/qwerty472123/wxappUnpacker 项目地址: https://gitcode.com/gh_mirrors/wxappu/wxappUnpacker 微信小程序逆向分析是理解小程序架构…...

Cursor编辑器深度解析:AI驱动的智能编程助手如何重塑开发工作流

1. 项目概述&#xff1a;一个为开发者而生的“智能副驾”如果你是一名开发者&#xff0c;最近一定在某个技术社区、朋友圈或者同事的聊天里&#xff0c;听到过“Cursor”这个名字。它不是某个新的编程语言&#xff0c;也不是一个框架&#xff0c;而是一个被许多一线工程师私下称…...

LinkedIn Liger Kernel:移动设备内核定制与性能优化实战

1. 项目概述&#xff1a;一个面向移动设备的开源内核探索如果你在移动设备开发、嵌入式系统或者内核研究的圈子里待过一段时间&#xff0c;大概率听说过或者接触过“Liger Kernel”这个名字。它不是一个商业产品&#xff0c;而是一个在GitHub上由LinkedIn开源并维护的Android内…...

Skeleton骨架系统:基于Tailwind CSS的现代前端UI架构实践

1. 项目概述&#xff1a;骨架系统在现代前端开发中的价值回归如果你在前端领域摸爬滚打了一段时间&#xff0c;尤其是深度使用过 Tailwind CSS&#xff0c;那么你很可能已经对“组件库”这三个字又爱又恨。爱的是它们能极大提升开发效率&#xff0c;恨的是它们往往伴随着沉重的…...