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

【算法挨揍日记】day34——647. 回文子串、5. 最长回文子串

647. 回文子串 

647. 回文子串

题目描述:

给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

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

解题思路:

算法思路:
我们可以先「预处理」⼀下,将所有⼦串「是否回⽂」的信息统计在 dp 表⾥⾯,然后直接在表
⾥⾯统计 true 的个数即可。
1. 状态表⽰:
为了能表⽰出来所有的⼦串,我们可以创建⼀个 n * n 的⼆维 dp 表,只⽤到「上三⻆部分」
即可。
其中, dp[i][j] 表⽰: s 字符串 [i, j] 的⼦串,是否是回⽂串。
2. 状态转移⽅程:
对于回⽂串,我们⼀般分析⼀个「区间两头」的元素:
i. s[i] != s[j] 的时候:不可能是回⽂串, dp[i][j] = 0
ii. s[i] == s[j] 的时候:根据⻓度分三种情况讨论:
⻓度为 1 ,也就是 i == j :此时⼀定是回⽂串, dp[i][j] = true
⻓度为 2 ,也就是 i + 1 == j :此时也⼀定是回⽂串, dp[i][j] = true
⻓度⼤于 2 ,此时要去看看 [i + 1, j - 1] 区间的⼦串是否回⽂: dp[i][j]
= dp[i + 1][j - 1]
综上,状态转移⽅程分情况谈论即可。
3. 初始化:
因为我们的状态转移⽅程分析的很细致,因此⽆需初始化。
4. 填表顺序:
根据「状态转移⽅程」,我们需要「从下往上」填写每⼀⾏,每⼀⾏的顺序⽆所谓。
5. 返回值:
根据「状态表⽰和题⽬要求」,我们需要返回 dp 表中 true 的个数。

 解题代码:

class Solution {
public:int countSubstrings(string s) {int n=s.size();vector<vector<bool>>dp(n,vector(n,false));for(int i=n-1;i>=0;i--){for(int j=i;j<n;j++){if(s[i]==s[j]){if(i==j)dp[i][j]=true;else if(i+1==j)dp[i][j]=true;else dp[i][j]=dp[i+1][j-1];}}}int ret=0;for(int i=0;i<n;i++){for(int j=i;j<n;j++){if(dp[i][j]==true)ret++;}}return ret;}
};

5. 最长回文子串 

5. 最长回文子串

题目描述:

给你一个字符串 s,找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。

 解题思路:

647. 回文子串icon-default.png?t=N7T8https://leetcode.cn/problems/palindromic-substrings/

在647题的基础上遍历所有dp表中为true的初始位置和长度

解题代码:

class Solution {
public:string longestPalindrome(string s) {int n=s.size();vector<vector<bool>>dp(n,vector(n,false));for(int i=n-1;i>=0;i--){for(int j=i;j<n;j++){if(s[i]==s[j]){if(i==j)dp[i][j]=true;else if(i+1==j)dp[i][j]=true;else dp[i][j]=dp[i+1][j-1];}}}int length=1;int begin=0;for(int i=0;i<n;i++){for(int j=0;j<n;j++)if(dp[i][j]==true&&length<j-i+1){length=max(j-i+1,length);begin=i;}}return s.substr(begin,length);}
};

相关文章:

【算法挨揍日记】day34——647. 回文子串、5. 最长回文子串

647. 回文子串 647. 回文子串 题目描述&#xff1a; 给你一个字符串 s &#xff0c;请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。 具有不同开始位置或结束位置的子串&am…...

欧科云链研究院:奔赴2024,Web3与AI共振引爆数字时代潘多拉魔盒

出品&#xff5c;欧科云链研究院 2024年&#xff0c;Web3与AI两个数字科技的巅峰碰撞&#xff0c;欧科云链研究院探索AI与Web3的技术融合&#xff0c;与澎湃科技联合发布2024年展望&#xff0c;原标题为《2024年展望&#xff1a;Web3与AI共振引爆可信数字社会》&#xff0c;共…...

【Py/Java/C++三种语言OD2023C卷真题】20天拿下华为OD笔试之【数学】2023C-素数之积【欧弟算法】全网注释最详细分类最全的华为OD真题题解

文章目录 题目描述与示例题目描述输入描述输出描述示例输入输出说明 解题思路暴力解质数筛 代码PythonJavaC时空复杂度 华为OD算法/大厂面试高频题算法练习冲刺训练 题目描述与示例 题目描述 RSA加密算法在网络安全世界中无处不在&#xff0c;它利用了极大些数因数分解的闲难…...

uniapp路由

1、路由登记 uni-app页面路由为框架统一管理&#xff0c;开发者需要在pages.json里配置每个路由页面的路径及页面样式。 类似小程序在 app.json 中配置页面路由一样。 所以 uni-app 的路由用法与 Vue Router 不同&#xff0c;如仍希望采用 Vue Router 方式管理路由&#xff0c;…...

湖南大学-数据库系统-2023期末考试【原题】

前言 早上11&#xff1a;00考完的考试&#xff0c;下午回来打了三把LOL之后&#xff0c;凭着回忆把题目重现出来了。 在复习的时候刷了15&#xff0c;16&#xff0c;17&#xff0c;18&#xff0c;19&#xff0c;21六年的卷子&#xff0c;感觉题目都差不多&#xff0c;但是难度…...

【Java EE初阶九】多线程案例(线程池)

一、线程池的引入 引入池---->主要是为了提高效率&#xff1b; 最开始&#xff0c;进程可以解决并发编程的问题&#xff0c;但是代价有点大了&#xff0c;于是引入了 “轻量级进程” ---->线程 线程也能解决并发编程的问题&#xff0c;而且线程的开销比进程要小的多&…...

理解 Node.js 中的事件循环

你已经使用 Node.js 一段时间了&#xff0c;构建了一些应用程序&#xff0c;尝试了不同的模块&#xff0c;甚至对异步编程感到很舒适。但是有些事情一直在困扰着你——事件循环&#xff08;Event Loop&#xff09;。 如果你像我一样&#xff0c;花费了无数个小时阅读文档和观看…...

Mac 软件出现「意外退出」及「打不开」解决方法

Mac 软件出现「意外退出」及「打不开」解决方法 软件出现意外退出及软件损坏的情况&#xff0c;这是因为苹果删除了TNT的证书&#xff0c;所以大部分TNT破解的Mac软件会出现无法打开&#xff0c;提示意外退出。 终端需先安装Xcode或Apple命令行工具 如未装Xcode可以使用下列命…...

随机森林 3(代码)

通过随机森林 1和随机森林 2 的介绍&#xff0c;相信大家对理论已经了解的很透彻&#xff0c;接下来带大家敲一下代码&#xff0c;不懂得可以加我入群讨论。 第一份代码是比较原始的代码&#xff0c;第二份代码是第一段代码中引用的primitive_plot&#xff0c;第三份代码是使用…...

勒索事件急剧增长,亚信安全发布《勒索家族和勒索事件监控报告》

近期(12.15-12.21)态势快速感知 近期全球共发生了247起攻击和勒索事件&#xff0c;勒索事件数量急剧增长。 近期需要重点关注的除了仍然流行的勒索家族lockbit3以外&#xff0c;还有本周top1勒索组织toufan。toufan是一个新兴勒索组织&#xff0c;本周共发起了108起勒索攻击&a…...

LeetCode1523. Count Odd Numbers in an Interval Range

文章目录 一、题目二、题解 一、题目 Given two non-negative integers low and high. Return the count of odd numbers between low and high (inclusive). Example 1: Input: low 3, high 7 Output: 3 Explanation: The odd numbers between 3 and 7 are [3,5,7]. Exam…...

E中国铜金属行业需求前景及未来发展机遇分析报告2024-2030年

E中国铜金属行业需求前景及未来发展机遇分析报告2024-2030年 &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 《报告编号》: BG471816 《出…...

python SVM 保存和加载模型参数

在 Python 中&#xff0c;你可以使用 scikit-learn 库中的 joblib 或 pickle 模块来保存和加载 SVM 模型的参数。以下是一个简单的示例代码&#xff0c;演示了如何使用 joblib 模块保存和加载 SVM 模型的参数&#xff1a; 保存模型参数&#xff1a; from sklearn import svm …...

JAVA进化史: JDK12特性及说明

JDK 12于2019年3月发布。这个版本相对于之前的版本来说规模较小&#xff0c;主要集中在一些改进和实验性的特性上。以下是JDK 12的一些主要特性&#xff1a; 引入了实验性的Shenandoah垃圾收集器 JDK 12引入了实验性的Shenandoah垃圾收集器&#xff0c;旨在实现极低的暂停时间…...

Databend 的算力可扩展性

作者&#xff1a;尚卓燃&#xff08;PsiACE&#xff09; 澳门科技大学在读硕士&#xff0c;Databend 研发工程师实习生 Apache OpenDAL(Incubating) Committer PsiACE (Chojan Shang) GitHub 对于大规模分布式数据处理系统&#xff0c;为了更好应对数据、流量、和复杂性的增长…...

「解析」Windows 如何优雅使用 Terminal

所谓工欲善其事必先利其器&#xff0c;对于开发人员 Linux可能是首选&#xff0c;但是在家学习的时候&#xff0c;我还是更喜欢使用 Windows系统&#xff0c;首先是稳定&#xff0c;其次是习惯了。当然了&#xff0c;我还有一台专门安装 Linux系统的小主机用于学习Linux使用&am…...

Linux第18步_安装“Ubuntu系统下的C语言编译器GCC”

Ubuntu系统没有提供C/C的编译环境&#xff0c;因此还需要手动安装build-essential软件包&#xff0c;它包含了 GNU 编辑器&#xff0c;GNU 调试器&#xff0c;和其他编译软件所必需的开发库和工具。本节用于重点介绍安装“Ubuntu系统下的C语言编译器&#xff27;&#xff23;&a…...

【Linux】Linux 基础命令 crontab命令

1.crontab命令 crond 是linux下用来周期性的执行某种任务或等待处理某些事件的一个守护进程,与windows下的计划任务类似,当安装完成操作系统后,默认会安装此服务 工具,并且会自动启动crond进程,crond进程每分钟会定期检查是否有要执行的任务,如果有要执行的任务,则自动…...

14:00面试,14:08就出来了,问的问题过于变态了。。。

从小厂出来&#xff0c;没想到在另一家公司又寄了。 到这家公司开始上班&#xff0c;加班是每天必不可少的&#xff0c;看在钱给的比较多的份上&#xff0c;就不太计较了。没想到10月一纸通知&#xff0c;所有人不准加班&#xff0c;加班费不仅没有了&#xff0c;薪资还要降40…...

Ubuntu envs setting

1. change the chmod of folders sudo chown -R $USER:$USER /home/anaconda3 2. torch.cuda.is_available()返回false change conda installation to pip. zai qi ta huan jing pei zhi dou mei wen ti de qing kuang xia , zai shi shi zhe ge fang fa. # CUDA 11.7 con…...

Windows 下用 C++ 调用 Python

文章目录 Part.I IntroductionChap.I InformationChap.II 预备知识 Part.II 语法Chap.I PyRun_SimpleStringChap.II C / Python 变量之间的相互转换 Part.III 实例Chap.I 文件内容Chap.II 基于 Visual Studio IDEChap.III 基于 cmakeChap.IV 运行结果 Part.IV 可能出现的问题Ch…...

九州金榜|家庭教育一招孩子不在任性

有一次和朋友一块聚餐&#xff0c;邻座是一位妈妈、和她大概七八岁的儿子&#xff0c;小男孩长得很帅气&#xff0c;没有像同龄人那样调皮捣乱&#xff0c;而是和妈妈很温馨的就餐。 看的出来一家人的素质很高&#xff0c;就餐过程中桌面保持的很整洁&#xff0c;交流声音也不…...

爬虫案列 --抖音视频批量爬取

""" 项目名称: 唯品会商品数据爬取 项目描述: 通过requests框架获取网页数据 项目环境: pycharm && python3.8 作者所属: 几许1. 对主页抓包 , 鼠标移动到视频位置视频自动播放获得视频数据包 2. 对视频数据包地址进行解析 , 复制链接 , 进行检索 3. 获…...

【React系列】React中的CSS

本文来自#React系列教程&#xff1a;https://mp.weixin.qq.com/mp/appmsgalbum?__bizMzg5MDAzNzkwNA&actiongetalbum&album_id1566025152667107329) 一. React中的css方案 1.1. react 中的 css 事实上&#xff0c;css 一直是 React 的痛点&#xff0c;也是被很多开发…...

基于Kettle开发的web版数据集成开源工具(data-integration)-应用篇

目录 &#x1f4da;第一章 基本流程梳理&#x1f4d7;页面基本操作&#x1f4d7;对应后台服务流程 &#x1f4da;第二章 二开思路&#x1f4d7;前端&#x1f4d7;后端 &#x1f53c;上一集&#xff1a;基于Kettle开发的web版数据集成开源工具(data-integration)-介绍篇 *️⃣主…...

51单片机三种编译模式的相互关系

51单片机三种编译模式的相互关系 编译模式默认存储类型RAM使用规模变量使用特点SAMLLdata128B片内RAM使用规模CPU访问数据速度快&#xff0c;但存储容量较小COMPACTpdata258B片外分页RAM速度和容量介于上下两者之间LARGExdata64KB片外RAMCPU访问数据的速度较慢&#xff0c;但存…...

java 千帆大模型 流式返回

聊天有两个接口,第一个是获取token, 第二个是聊天接口,具体参照官方文档 下面是流式调用聊天接口,单次的,不含上下文 Value("${qianfan.apiKey}")private String apiKey;Value("${qianfan.secretKey}")private String secretKey;Value("${qianfan.to…...

全新互联网洗衣洗鞋小程序平台新模式

互联网洗衣洗鞋新模式&#xff0c; 全新软件升级 对接各大平台 扩大营销渠道&#xff0c;增加效益&#xff01;...

js 对于一些脚本中对于url的一些参数获取

js 对于一些脚本中对于url的一些参数获取 获取当前浏览器的链接上的参数(不使用vue / react 等框架&#xff09;仅用在一些脚本上的使用 获取当前浏览器的链接上的参数(不使用vue / react 等框架&#xff09;仅用在一些脚本上的使用 const query {} const params new URLSear…...

IEDA中tomcat日志乱码解决

文章目录 乱码样式原因解决方案参考 乱码样式 原因 乱码原因是编码格式的问题&#xff0c;编码格式不统一&#xff0c;导致显示乱码。 解决方案 统一编码格式。 打开tomcat的配置文件&#xff0c;conf/logging.properties,进行如下修改 进入idea的安装文件中&#xff0c;b…...

最好的网站模版/竞价点击软件排名

小例题&#xff1a; n 个数 目前为三个数 x%32; x%53; x%72; 1.求最小公倍数&#xff1a;M357105。 2.依照余数求各个数的基础数&#xff1a; 105/335&#xff0c;35%32&#xff1b; 105/521&#xff0c;21%51&#xff0c;即63%53&#xff1b; 105/715&#xff0c;15%71&a…...

文字域名可以做网站/浙江网络推广

安装完成后不能编译&#xff0c;提示&#xff1a;**Error**: You must have glib installed.解决sudo apt-get install libglib2.0-dev pkg-config转载于:https://www.cnblogs.com/sdq928/archive/2010/09/13/1825335.html...

网站seo分析工具/sem推广是什么意思

记录一下最近做的项目&#xff0c;使用布控球识别陌生的人脸&#xff0c;在电力系统的施工现场&#xff0c;通常是不允许陌生人进入的&#xff0c;所以需要使用监控识别哪些人是陌生人&#xff0c;并在监控图像中标出他们的位置。一般来说有成熟的解决方案优先使用成熟的解决方…...

办公室装修风格图/竞价关键词优化软件

找到webpack.config.prod.js 在loaders增加 {test: /\.less$/,loader: ExtractTextPlugin.extract(style, css!less) },...

wap版网站 加app提示/互联网营销师考试题库

参考资料&#xff1a; 1、 JVM(二)Java8内存划分 https://blog.csdn.net/yjp198713/article/details/78759933 2、JAVA7、JAVA8的堆内存有啥变化 https://blog.csdn.net/chlu113/article/details/51890469 3、Java8—底层内存结构方法区 https://blog.csdn.net/u01281320…...

wordpress 注释/今日头条权重查询

拼多多商家参加了平台活动后&#xff0c;就需要去建立一个营销账户并且进行充值&#xff0c;那么拼多多营销账户该如何进行提现呢?无法提现又是为什么? 拼多多营销账户如何提现&#xff1f; 在你的手机上打开拼多多app&#xff0c;菜单栏里有我的设置&#xff0c;并且点击&…...