代码随想录第60天 | 647. 回文子串 、 516.最长回文子序列

2024-05-05 10:04

本文主要是介绍代码随想录第60天 | 647. 回文子串 、 516.最长回文子序列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、前言

参考文献:代码随想录;

转眼间两个月已经过去,五一休息了三天,今天将要结束动态规划了。

今天的主题是用dp解决回文子串;

二、回文子串

1、思路:

我一开始就想用一维dp数组来解决这道题目,但是发现找不到关系,然后就尝试使用了一下暴力解法,感觉不错;

(1)暴力:

class Solution {
private:bool isPalindrom(string &s, int start, int end) {while (start < end) {if (s[start] != s[end]) {return false;}start++;end--;}return true;}
public:int countSubstrings(string s) {int count = 0;for (int i = 0; i < s.size(); i++) {for (int j = i; j < s.size(); j++) {if (isPalindrom(s, i, j)) {count++;}}}return count;}
};

回到dp:

(1)递推公式 + 初始化:

我们需要判断改数组是不是回文串,所以我们定义的dp是bool类型,接着是我们需要一个边界来规定子串,这样才可以求出每个子串(这里顺带初始化了,全部都默认为false):

vector<vector<bool>> dp(s.size(), vector<bool> (s.size(), false));

 (2)递推公式:

我们需要判断三个条件,当i == j时,很显然一个字母也是回文串,所以为false;

当 j - i == 1时,也是一个回文串,例如“aba”;

当 j - i > 1时,我们就需要利用dp数组来解决了,判断 i + 1 到 j - 1这个区间是不是回文串,才能判断是不是回文串

(3)遍历顺序:

看这个图片发现,新的状态是之前的状态得出来的,但是这个状态在新状态的左下角,所以需要从下往上,从左往右遍历;

2、整体代码如下:

class Solution {
public:int countSubstrings(string s) {// 1、定义dp数组+初始化// 在下标i与j之间的范围内,是否是回文子串vector<vector<bool>> dp(s.size(), vector<bool> (s.size(), false));int count = 0;// 2、遍历顺序,从下往上,从左往右for (int i = s.size() - 1; i >= 0; i--) {for (int j = i; j < s.size(); j++) {// 3、递推公式(三种情况)if (s[i] == s[j]) {if (j - i <= 1 ) {dp[i][j] = true;} else {dp[i][j] = dp[i + 1][j - 1];}}if (dp[i][j]) count++;}}return count;}
};

三、最长回文序列

1、思路:

本题感觉有点小绕,所以我看了题解之后还是有点蒙蔽;

(1)dp数组定义:

可以看出这个与上一题目很像,但是求的是最长回文子串的长度,所以还是需要创建二维的int类型数组;

(2)递推公式:

分为两种情况,当 s[i] == s[j]时,就需要在原有的dp[i + 1][j - 1]的基础上加2;

(3)初始化:

首先要考虑当i 和j 相同的情况,从递推公式:dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出 递推公式是计算不到 i 和j相同时候的情况。

所以要初始化这个对角线:

for (int i = 0; i < s.size(); i++) dp[i][i] = 1;

(4)遍历顺序:

这里的遍历还是从下到上,从左到右

 

 

 只是现在可以选择不连续的情况了,所以就如下(为什么不能把初始化的情况放到遍历中去?因为会越界,i == 0的时候就越界了):

for (int i = s.size() - 1; i >= 0; i--) {for (int j = i + 1; j < s.size(); j++) {if (s[i] == s[j]) {dp[i][j] = dp[i + 1][j - 1] + 2;} else {dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);}}}

2、完整代码如下:

class Solution {
public:int longestPalindromeSubseq(string s) {// 1、初始化+定义dp数组vector<vector<int>> dp(s.size(), vector<int> (s.size(), 0));for (int i = 0; i < s.size(); i++) dp[i][i] = 1;// 2、遍历顺序for (int i = s.size() - 1; i >= 0; i--) {for (int j = i + 1; j < s.size(); j++) {if (s[i] == s[j]) {dp[i][j] = dp[i + 1][j - 1] + 2;} else {dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);}}}return dp[0][s.size() - 1];}
};

Study time 1h

Leave message:

Young people have changed the course of history time and time again.

年轻人一次又一次的改变了历史的进程。

 

这篇关于代码随想录第60天 | 647. 回文子串 、 516.最长回文子序列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/961435

相关文章

Java中调用数据库存储过程的示例代码

《Java中调用数据库存储过程的示例代码》本文介绍Java通过JDBC调用数据库存储过程的方法,涵盖参数类型、执行步骤及数据库差异,需注意异常处理与资源管理,以优化性能并实现复杂业务逻辑,感兴趣的朋友... 目录一、存储过程概述二、Java调用存储过程的基本javascript步骤三、Java调用存储过程示

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性:

MySQL数据库的内嵌函数和联合查询实例代码

《MySQL数据库的内嵌函数和联合查询实例代码》联合查询是一种将多个查询结果组合在一起的方法,通常使用UNION、UNIONALL、INTERSECT和EXCEPT关键字,下面:本文主要介绍MyS... 目录一.数据库的内嵌函数1.1聚合函数COUNT([DISTINCT] expr)SUM([DISTIN

Java实现自定义table宽高的示例代码

《Java实现自定义table宽高的示例代码》在桌面应用、管理系统乃至报表工具中,表格(JTable)作为最常用的数据展示组件,不仅承载对数据的增删改查,还需要配合布局与视觉需求,而JavaSwing... 目录一、项目背景详细介绍二、项目需求详细介绍三、相关技术详细介绍四、实现思路详细介绍五、完整实现代码

Go语言代码格式化的技巧分享

《Go语言代码格式化的技巧分享》在Go语言的开发过程中,代码格式化是一个看似细微却至关重要的环节,良好的代码格式化不仅能提升代码的可读性,还能促进团队协作,减少因代码风格差异引发的问题,Go在代码格式... 目录一、Go 语言代码格式化的重要性二、Go 语言代码格式化工具:gofmt 与 go fmt(一)

HTML5实现的移动端购物车自动结算功能示例代码

《HTML5实现的移动端购物车自动结算功能示例代码》本文介绍HTML5实现移动端购物车自动结算,通过WebStorage、事件监听、DOM操作等技术,确保实时更新与数据同步,优化性能及无障碍性,提升用... 目录1. 移动端购物车自动结算概述2. 数据存储与状态保存机制2.1 浏览器端的数据存储方式2.1.

基于 HTML5 Canvas 实现图片旋转与下载功能(完整代码展示)

《基于HTML5Canvas实现图片旋转与下载功能(完整代码展示)》本文将深入剖析一段基于HTML5Canvas的代码,该代码实现了图片的旋转(90度和180度)以及旋转后图片的下载... 目录一、引言二、html 结构分析三、css 样式分析四、JavaScript 功能实现一、引言在 Web 开发中,

Python如何去除图片干扰代码示例

《Python如何去除图片干扰代码示例》图片降噪是一个广泛应用于图像处理的技术,可以提高图像质量和相关应用的效果,:本文主要介绍Python如何去除图片干扰的相关资料,文中通过代码介绍的非常详细,... 目录一、噪声去除1. 高斯噪声(像素值正态分布扰动)2. 椒盐噪声(随机黑白像素点)3. 复杂噪声(如伪

Java Spring ApplicationEvent 代码示例解析

《JavaSpringApplicationEvent代码示例解析》本文解析了Spring事件机制,涵盖核心概念(发布-订阅/观察者模式)、代码实现(事件定义、发布、监听)及高级应用(异步处理、... 目录一、Spring 事件机制核心概念1. 事件驱动架构模型2. 核心组件二、代码示例解析1. 事件定义

Python实例题之pygame开发打飞机游戏实例代码

《Python实例题之pygame开发打飞机游戏实例代码》对于python的学习者,能够写出一个飞机大战的程序代码,是不是感觉到非常的开心,:本文主要介绍Python实例题之pygame开发打飞机... 目录题目pygame-aircraft-game使用 Pygame 开发的打飞机游戏脚本代码解释初始化部