当前位置: 首页 > 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…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

MySQL 8.0 事务全面讲解

以下是一个结合两次回答的 MySQL 8.0 事务全面讲解&#xff0c;涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容&#xff0c;并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念&#xff08;ACID&#xff09; 事务是…...

CVPR2025重磅突破:AnomalyAny框架实现单样本生成逼真异常数据,破解视觉检测瓶颈!

本文介绍了一种名为AnomalyAny的创新框架&#xff0c;该方法利用Stable Diffusion的强大生成能力&#xff0c;仅需单个正常样本和文本描述&#xff0c;即可生成逼真且多样化的异常样本&#xff0c;有效解决了视觉异常检测中异常样本稀缺的难题&#xff0c;为工业质检、医疗影像…...

提升移动端网页调试效率:WebDebugX 与常见工具组合实践

在日常移动端开发中&#xff0c;网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时&#xff0c;开发者迫切需要一套高效、可靠且跨平台的调试方案。过去&#xff0c;我们或多或少使用过 Chrome DevTools、Remote Debug…...