【算法挨揍日记】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);}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/230601.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【卫星科普】什么是农业一号卫星和农业二号卫星?

农业一号卫星和农业二号卫星是中国自主研发的两颗重要卫星&#xff0c;主要用于农业领域的监测和研究。 农业一号卫星是中国第一颗具备红边波段传感器的卫星&#xff0c;也是世界上第一颗具备红边波段的宽视场多光谱中高分辨率卫星。这对农业农村遥感监测非常重要&#xff0c;…

认识CUDA

CUDA CUDA&#xff08;Compute Unified Device Architecture&#xff09;&#xff0c;是显卡厂商NVIDIA推出的运算平台。 CUDA™是一种由NVIDIA推出的通用并行计算架构&#xff0c;该架构使GPU能够解决复杂的计算问题。 它包含了CUDA指令集架构&#xff08;ISA&#xff09;以及…

基于YOLOv7算法的高精度实时抽烟行为检测识别系统(PyTorch+Pyside6+YOLOv7)

摘要&#xff1a;基于YOLOv7算法的高精度实时抽烟行为检测系统可用于日常生活中检测与定位抽烟行为&#xff0c;此系统可完成对输入图片、视频、文件夹以及摄像头方式的目标检测与识别&#xff0c;同时本系统还支持检测结果可视化与导出。本系统采用YOLOv7目标检测算法来训练数…

1.1 理解大数据(2)

小肥柴的Hadoop之旅 1.1 理解大数据&#xff08;2&#xff09; 目录1.1 理解大数据1.1.3 大数据概述1.1.4 更多思考 参考文献和资料 目录 1.1 理解大数据 1.1.3 大数据概述 step_0 大数据定义 【《大数据算法设计分析》】&#xff1a; 通常来讲大数据&#xff08;Big Data&am…

互联网分布式应用之RabbitMQ

RabbitMQ Java 是第一大编程语言和开发平台。它有助于企业降低成本、缩短开发周期、推动创新以及改善应用服务。如今全球有数百万开发人员运行着超过 51 亿个 Java 虚拟机&#xff0c;Java 仍是企业和开发人员的首选开发平台。 课程内容的介绍 1. RabbitMQ介绍安装 2. Rabbi…

【C#】知识点实践序列之Lock的输出多线程信息

大家好&#xff0c;我是全栈小5&#xff0c;欢迎来到《小5讲堂之知识点实践序列》文章。 2024年第2篇文章&#xff0c;此篇文章是C#知识点实践序列之Lock知识点&#xff0c;博主能力有限&#xff0c;理解水平有限&#xff0c;若有不对之处望指正&#xff01; 本篇在Lock锁定代码…

P1019 [NOIP2000 提高组] 单词接龙

网址如下&#xff1a;P1019 [NOIP2000 提高组] 单词接龙 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 很怪&#xff0c;不知道该说什么 我试了题目给的第一个测试点的输入&#xff0c;发现输出和测试点的一样&#xff0c;但是还是WA 不是很懂为什么 有没有大佬帮我看一下…

20231228在Firefly的AIO-3399J开发板的Android11使用Firefly的DTS配置单前后摄像头ov13850

20231228在Firefly的AIO-3399J开发板的Android11使用Firefly的DTS配置单前后摄像头ov13850 2023/12/28 19:20 缘起&#xff0c;突然发现只能打开前置的ov13850&#xff0c;或者后置的ov13850。 但是不能切换&#xff01; 【SDK&#xff1a;rk3399-android-11-r20211216.tar.xz】…

Java-replaceAll()同时替换多个字符

今天复现了raplaceAll&#xff08;&#xff09;的用法&#xff0c;但是通常都是对一种字符进行替换&#xff0c;我就在想有没有操作可以一次性替换多个不同的字符&#xff0c;百度一搜&#xff0c;果然有。具体情况如下 首先是替换字的 String str1 "小明&#xff0c;小…

Vue - 多行文本“展开、收起”功能

TextClamp 使用 js 实现文本展开、收起&#xff0c;并非纯 CSS 实现。 Props&#xff1a; fontSize&#xff1a;Number&#xff0c;默认&#xff1a;14lines&#xff1a;Number&#xff0c;默认&#xff1a;1lineHeight&#xff1a;Number&#xff0c;默认&#xff1a;20 F…

双碳管理系统任务需求分析(第10套)

需求规格说明书 一、引言 &#xff08;一&#xff09;项目背景 编写本需求规格说明书的目的是为了详细呈现碳足迹产品需求和系统的功能描述&#xff0c;以进一步定制应用软件系统开发的细节问题&#xff0c;便于与项目开发协调工作。本文档面向的读者主要是项目委托单位的管…

vivado 管理宏

管理宏 宏存储为XDC约束。根据定义&#xff0c;它们是Tcl命令。这允许要在XDC约束文件和Tcl脚本中使用并交互使用的宏。宏是使用write_xdc命令编写的。使用read_xdc读取宏命令-cell选项可用于将作用域限制为特定的单元格。-cell选项特别适用于将一个宏的相对放置应用到不同层次…

4.快速实现增删改查,模糊查询功能

打开springboot项目&#xff0c;在com.example下建包common,在common下新建Result.java 4.1封装统一的返回数据结构 1.在Result.java中编写如下代码&#xff1a; private static final String *SUCCESS*"0"; private static final String *ERROR*"-1"; p…

ROS学习笔记(8)进一步深入了解ROS第二步

0.前提 在上一讲中我提到过该系列是基于宾夕法尼亚大学工程学院的ROS公开课&#xff0c;系列文章将来源于公开课中的课后习题。该系列可以很好的帮助大家更加深入的了解ROS的一些概念。&#xff08;有效面对HR的提问。&#xff09; 1. (C)What is a nodehandle object? Can we…

项目经验简单总结

引擎 unity 2020 语言 C# lua python(用于工具链) java (用于SDK对接) js&#xff08;PC WEB SDK对接&#xff09; 编辑器 VS VSCODE IDEA eclipse 项目开发模块规划分 主项目工程&#xff0c;UI资源项目工程&#xff0c;模型场景资源项目工程 主项目工程&#xff1a;所有的…

Excel模板填充:从minio上获取模板使用easyExcel填充

最近工作中有个excel导出的功能&#xff0c;要求导出的模板和客户提供的模板一致&#xff0c;而客户提供的模板有着复杂的表头和独特列表风格&#xff0c;像以往使用poi去画是非常耗时间的&#xff0c;比如需要考虑字体大小&#xff0c;单元格合并&#xff0c;单元格的格式等问…

vue-打包

打包的作用 说明&#xff1a;vue脚手架只是开发过程中&#xff0c;协助开发的工具&#xff0c;当真正开发完了>脚手架不参与上线 打包的作用&#xff1a; 1&#xff09;将多个文件压缩合并成一个文件 2&#xff09;语法降级 3&#xff09;less sass ts语法解析 打包后…

liunx操作系统基础及进阶

一、基础入门 1、Linux系统简介 什么是Liunx&#xff1f; Linux在设计之初&#xff0c;是一个基于POSIX的多用户、多任务并且支持多线程和多CPU的操作系统&#xff0c;它是由世界各地成千上万的程序员设计和开发实现&#xff1b; 在当今社会&#xff0c;Linux 系统主要被应…

【智慧零售】东胜物联蓝牙网关硬件解决方案,促进零售门店数字化管理

依托物联网&#xff08;IoT&#xff09;、大数据、人工智能&#xff08;AI&#xff09;等快速发展&#xff0c;数字化和智能化已成为零售企业的核心竞争力。更多的企业通过引入人工智能、大数据等先进技术手段&#xff0c;提高门店运营效率和服务质量。 某连锁咖啡企业牢牢抓住…

[嵌入式C][入门篇] 快速掌握基础(9个语句)

开发环境&#xff1a; 网页版&#xff1a;跳转本地开发(Vscode)&#xff1a;跳转 文章目录 一、基础语法&#xff08;1&#xff09;if (如果)示例1: 普通使用 if示例2: 带否则 else示例3: 否则如果 else if &#xff08;2&#xff09;switch case (选择)规则示例1: &#xff0…