剑指 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[i−1]=s[j−1],那么
f[i][j] = false. - 当 s[i−1]=s[j−1]s[i-1] = s[j-1]s[i−1]=s[j−1],
-
- 如果 j−i≤1j - i \leq1j−i≤1,
s[i][j] = true(相当于指针i和j指向了一个字符'a',或者指向了两个相连且相等的字符'aa')。
- 如果 j−i≤1j - i \leq1j−i≤1,
-
- 如果
f[i-1][j+1] = true,s[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,请计算这个字符串中有多少个回文子字符串。 具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。 示例 1: 输入…...
Python实现多键字典
实现背景 在许多场景中,有时需要通过多种信息来获取某个特定的值,而各种编程语言(包括Python)使用的字典(Dict)数据结构通常只支持单个键值寻值key-val对,即“一对一”(一个键对应一…...
【python socket】实现websocket服务端
一、获取握手信息首先通过如下代码,我们使用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上引脚, MODE JTAG时,MODExxx. except 3’b000. 禁止设置为3’b000. Slave Parallel时,MODE 3’b110,不常用。 Slave Serial时,MODE 3’b111,不常用。 Master SPI 时&…...
路由协议(OSPF、ISIS、BGP)实验配置
目录 OSPF基础实验 建立OSPF邻居 配置虚连接 配置接口的网络类型 配置特殊区域 配置路由选路 配置路由过滤 ISIS基础实验配置 配置ISIS邻居建立 配置认证 配置路由扩散 配置路由过滤 配置定时器 BGP基础实验配置 建立BGP对等体 建立IBGP对等体 建立EBGP对等体…...
Python可变对象与不可变对象的浅拷贝与深拷贝
前言 本文主要介绍了python中容易面临的考试点和犯错点,即浅拷贝与深拷贝 首先,针对Python中的可变对象来说,例如列表,我们可以通过以下方式进行浅拷贝和深拷贝操作: import copya [1, 2, 3, 4, [a, b]]b a …...
滑模控制(Sliding mode control)快速入门
0. 简介 最近作者受到邀请,让我帮忙给刚入门的学弟讲讲滑模控制。可是作者也不知道怎么向未入门的学弟讲解这些基础知识,所以作者翻了翻近几年写的很好的文章以及视频。综合起来,来总结出一套比较基础,且适用于初学者的文章吧。这…...
golang的垃圾回收详解
golang的垃圾回收详解 一、三色标记法 作为一门现代化的语言,golang与java一样,都在语言中内置了垃圾回收的功能,不需要程序员自己去回收堆内存。而垃圾回收中,最重要的两个部分就是垃圾检测算法以及垃圾回收算法。垃圾检测算法决…...
线上负载过高排查(top/vmstat/ifstat/free/df)
目录 一、五大命令 二、故障排查步骤 1、top命令找出CPU占比最高的 2、ps -ef 或者 jps -l进一步定位 3、ps -mp位到具体线程或者代码 4、jstack精准定位到错误的地方 本文通过学习:周阳老师-尚硅谷Java大厂面试题第二季 总结的LinuxJDK命令操作相关的笔记 一…...
Java的注解(Annotation)
Java 注解(Annotation)又称 Java 标注,是 JDK5.0 引入的一种注释机制。Java 中的类、构造器、方法、成员变量、参数等都可以被注解进行标注。例如JUnit单元测试中的Test方法,可以使得方法直接运行。JUnit单元测试Test单元测试是针…...
信息系统项目管理师:配置管理
配置管理指的是在一个系统或软件中对配置项的管理,包括对配置项的定义、存储、跟踪和修改等一系列活动。配置项可以是硬件设备、软件组件、系统设置、网络配置等,配置管理旨在确保在不同时间点或环境下系统或软件的配置项的正确性和一致性。通过配置管理…...
web餐饮开源程序
简介 一款专门针对餐饮行业而开发桌面应用程序 技术 借助Panuon.UI.Silver控件库,开发的一款餐饮软件。 运行环境:.NETFramework,Versionv4.8。 运行数据库:MySql。 ORM框架:SqlSugar。 第三方插件:Panuon.UI.Silv…...
28个案例问题分析---027---单表的11个Update接口--MyBatis
一:背景介绍 项目开发中。我们使用的是MyBatis,在MyBatis的xml文件里,两个表的更新功能,写了足足11个更新接口,毫无复用的思想 这种方式可以正常的实现功能,但是没有复用,无论是从时间上还是维…...
大数据开发治理平台 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 可以用于说明一个类的成员;静态成员提供了一个同类对象的共享机制;把一个类的成员说明为 static 时,这个类无论有多少个对象被创建,这些对象共享这个 static …...
开源监控服务uptime-kuma
好久没写文章了,刚好最近用了一个开源的监控服务,感觉蛮有意思的,记录一下 (一)安装 uptime-kuma安装方式有几种,这里当然是选择大家都爱的docker,一条命令搞定 docker run -d --restartalways -p 3001:…...
JavaScript混淆技术:了解其核心原理和常用手段
当今互联网时代,JavaScript已经成为了web前端开发的重点技术之一。其中,JavaScript代码的安全性问题一直是关注的焦点。为了保护JavaScript代码的安全性,很多人对其进行加密处理,众所周知,对于单纯的加密算法ÿ…...
大型医院云HIS系统:采用前后端分离架构,前端由Angular语言、JavaScript开发;后端使用Java语言开发 融合B/S版电子病历系统
一套医院云his系统源码 采用前后端分离架构,前端由Angular语言、JavaScript开发;后端使用Java语言开发。融合B/S版电子病历系统,支持电子病历四级,HIS与电子病历系统均拥有自主知识产权。 文末卡片获取联系! 基于云计…...
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…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...
2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...
在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案
这个问题我看其他博主也写了,要么要会员、要么写的乱七八糟。这里我整理一下,把问题说清楚并且给出代码,拿去用就行,照着葫芦画瓢。 问题 在继承QWebEngineView后,重写mousePressEvent或event函数无法捕获鼠标按下事…...
springboot整合VUE之在线教育管理系统简介
可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生,小白用户,想学习知识的 有点基础,想要通过项…...
排序算法总结(C++)
目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指:同样大小的样本 **(同样大小的数据)**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...
