刷题记录|Day57
● 516.最长回文子序列

● 647. 回文子串

题目描述

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

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

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

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

示例 1：

输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：

输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：

• 1 <= s.length <= 1000
• s 由小写英文字母组成

解题思路

动规五部曲：

1. 确定dp数组（dp table）以及下标的含义

如果大家做了很多这种子序列相关的题目，在定义dp数组的时候 很自然就会想题目求什么，我们就如何定义dp数组。

绝大多数题目确实是这样，不过本题如果我们定义，dp[i] 为 下标i结尾的字符串有 dp[i]个回文串的话，我们会发现很难找到递归关系。

dp[i] 和 dp[i-1] ，dp[i + 1] 看上去都没啥关系。

我们在判断字符串S是否是回文，那么如果我们知道 s[1]，s[2]，s[3] 这个子串是回文的，那么只需要比较 s[0]和s[4]这两个元素是否相同，如果相同的话，这个字符串s 就是回文串。

那么此时我们是不是能找到一种递归关系，也就是判断一个子字符串（字符串的下表范围[i,j]）是否回文，依赖于，子字符串（下表范围[i + 1, j – 1]）） 是否是回文。

所以为了明确这种递归关系，我们的dp数组是要定义成一位二维dp数组。

布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。

2. 确定递推公式

在确定递推公式时，就要分析如下几种情况。

整体上是两种，就是s[i]与s[j]相等，s[i]与s[j]不相等这两种。

当s[i]与s[j]不相等，那没啥好说的了，dp[i][j]一定是false。

当s[i]与s[j]相等时，这就复杂一些了，有如下三种情况

• 情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
• 情况二：下标i 与 j相差为1，例如aa，也是回文子串
• 情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j – 1]是否为true。

if s[i] == s[j]) {if j - i <= 1) { // 情况一 和 情况二result++;dp[i][j] = true;} else if dp[i + 1][j - 1]) { // 情况三result++;dp[i][j] = true;}
}

result就是统计回文子串的数量。
3. dp数组如何初始化

dp[i][j]可以初始化为true么？ 当然不行，怎能刚开始就全都匹配上了。

所以dp[i][j]初始化为false。

4. 确定遍历顺序

遍历顺序可有有点讲究了。

首先从递推公式中可以看出，情况三是根据dp[i + 1][j – 1]是否为true，在对dp[i][j]进行赋值true的。
如果这矩阵是从上到下，从左到右遍历，那么会用到没有计算过的dp[i + 1][j – 1]，也就是根据不确定是不是回文的区间[i+1,j-1]，来判断了[i,j]是不是回文，那结果一定是不对的。

所以一定要从下到上，从左到右遍历，这样保证dp[i + 1][j – 1]都是经过计算的。

有的代码实现是优先遍历列，然后遍历行，其实也是一个道理，都是为了保证dp[i + 1][j – 1]都是经过计算的。

for int i = s.size) - 1; i >= 0; i--) {  // 注意遍历顺序for int j = i; j < s.size); j++) {if s[i] == s[j]) {if j - i <= 1) { // 情况一 和 情况二result++;dp[i][j] = true;} else if dp[i + 1][j - 1]) { // 情况三result++;dp[i][j] = true;}}}
}

注意因为dp[i][j]的定义，所以j一定是大于等于i的，那么在填充dp[i][j]的时候一定是只填充右上半部分。

class Solution {
public:int countSubstringsstring s) {vector<vector<bool>> dps.size), vector<bool>s.size), false));int result = 0;for int i = s.size) - 1; i >= 0; i--) {  // 注意遍历顺序for int j = i; j < s.size); j++) {if s[i] == s[j]) {if j - i <= 1) { // 情况一 和 情况二result++;dp[i][j] = true;} else if dp[i + 1][j - 1]) { // 情况三result++;dp[i][j] = true;}}}}return result;}
};

● 516.最长回文子序列

题目描述

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

示例 2：

输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

提示：

• 1 <= s.length <= 1000
• s 仅由小写英文字母组成

解题思路

class Solution {
public:int longestPalindromeSubseqstring s) {vector<vector<int>> dps.size), vector<int> s.size), 0));for int i = 0; i < s.size); i++) dp[i][i] = 1;for int i = s.size)-1; i >= 0; --i) {forint j = i+1; j < s.size); ++j) {ifs[i] == s[j]) {dp[i][j] = dp[i+1][j-1] + 2;} else {dp[i][j] = maxdp[i+1][j],dp[i][j-1]);}}}return dp[0][s.size) - 1];}
};

查看全文

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

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章：

刷题记录|Day57 ● 647. 回文子串 ● 516.最长回文子序列

刷题记录|Day57 ● 516.最长回文子序列
● 647. 回文子串
题目描述
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结……

编程日记2023/4/12 15:15:36

JAVA System.nanoTime)与GO time.Now).UnixNano)区别

JAVA System.nanoTime) public static void mainString[] args) {long nano System.nanoTime);System.out.printlnnano);}
输出：701863191254000，这个值有点奇怪，System.currentTimeMillis)不是System.nanoTime)的1000000倍。
这个值……

编程日记2023/4/12 15:15:09

enote笔记法之附录1——“语法词”（即“关联词”）（ver0.22）

章节：enote笔记法之附录1——“语法词”（即“关联词”）（ver0.22）
上面的是截屏的完整版，分割线下面的是纯文字版本： 作者姓名（本人的真实姓名）：胡佳吉
居……

编程日记2023/4/12 15:14:57

数据结构——排序（4）

作者：几冬雪来 时间：2023年4月12日 内容：数据结构排序内容讲解 目录
前言：
1.快速排序中的递归：
2.小区间优化：
3.递归改非递归：
4.归并排序：
5.归并排序的非递归形式&amp……

编程日记2023/4/12 15:14:44

视图的使用

为什么引入视图（Views）
如果您读过其他类似的书，可能会看到这些书在介绍视图时列举了许多引入视图的原因。其中认为最重要的原因是维护数据的独立性。那么什么是数据的独立性呢？
早期信息系统的设计与开发多采用模块驱动方式&am……

编程日记2023/4/12 15:14:31

2024软件工程考研之《软件工程导论》专业课复习

一、考察《软件工程导论》的学校
截止目前，考察《软件工程导论》的学校主要有： 大连理工大学887 北京航天航空大学991 北京交通大学901 河海大学846 海南大学835 新疆大学841 成都信息工程大学809 长安大学846 天津工业大学840 华东交通大学837 大连交通……

编程日记2023/4/12 15:14:17

Visual Studio 2022如何安装和使用MSDN

我是荔园微风，作为一名在IT界整整25年的老兵，在后台收到提问，问我Visual Studio 2022如何安装和使用MSDN，这个我之前也没有在这个版本上装过MSDN，我之前是在Visual Studio 2017版上装过MSDN，那既然有人问了……

编程日记2023/4/12 15:14:08

论文浅尝 | 大语言模型在in-context learning中的不同表现

笔记整理：毕祯，浙江大学博士，研究方向为知识图谱、自然语言处理链接：https://arxiv.org/pdf/2303.03846.pd本文是谷歌等机构最新发表的论文，旨在研究大模型上下文学习的能力。这篇论文研究了语言模型中的上下文学习是如……

编程日记2023/4/12 15:13:59

【hello Linux】Linux第一个小程序 – 进度条

目录 先来区分两个标识符：回车和换行 1. 倒计时 2. 进度条 Linux🌷 下面来编写Linux系统下的第一个小程序 – 进度条 先来区分两个标识符：回车和换行 \r 和 \n \r 回车 ：代表回到本行的开头；
\n 换行 ：代表……

编程日记2023/4/12 15:13:48

DC插装式流量阀压力阀

Cartridge Valves
电磁阀
止回阀
运动控制阀
流量控制阀
溢流阀
压力控制阀
顺序阀
梭阀
方向阀
配件
Zero Profile Valves
止回阀
运动控制阀
流量控制阀
溢流阀
梭阀
In-Line Valves
止回阀和梭阀
方向阀
配件
微型系列 AB20S APIDC-30S C10B C10S C10S……

编程日记2023/4/12 15:13:36

反序列化渗透与攻防五)之shiro反序列化漏洞

Shiro反序列化漏洞
Shiro介绍
Apache Shiro是一款开源安全框架，提供身份验证、授权、密码学和会话管理。Shiro框架直观、易用，同时也能提供健壮的安全性
Apache Shiro 1.2.4及以前版本中，加密的用户信息序列化后存储在名为remember-me的Cookie中。攻击者可以使用Shiro的默……

编程日记2023/4/16 14:52:13

vue2+vue3

vue2vue3尚硅谷vue2vue2 课程简介【02:24】vue2 Vue简介【17:59】vue2 Vue官网使用指南【14:07】vue2 搭建Vue开发环境【13:54】vue2 Hello小案例【22:25】了解： 不常用常用：id 更常用 简单class差值总结vue 实例vue 模板 ： 先 取 &#xff0……

编程日记2023/4/16 14:52:00

【hello Linux】环境变量

目录 1. 环境变量的概念 2. 常见的环境变量 3. 查看环境变量 4. 和环境变量相关的命令 5. 环境变量的组织方式 6. 通过代码获取环境变量 7. 通过系统调用获取环境变量 Linux🌷 在开始今天的内容之前，先来看一幅图片吧！ 不知道你们是否和我一……

编程日记2023/4/16 14:51:36

【Linux基础】常用命令整理

ls命令
-a选项，可以展示隐藏的文件和文件夹-l选项，以列表形式展示内容-h，需要和-l搭配使用，可以展示文件的大小单位ls -lah等同于la -a -l -h
cd命令（change directory）
语法：cd [Linux路径]……

编程日记2023/4/16 14:51:26

客快物流大数据项目（一百一十二）：初识Spring Cloud

文章目录
初识Spring Cloud
一、Spring Cloud简介
二、SpringCloud 基础架构图…

编程日记2023/4/16 14:51:11

C和C++中的struct有什么区别

区别一： C语言中： Struct是用户自定义数据类型（UDT）。 C语言中： Struct是抽象数据类型（ADT），支持成员函数的定义。
区别二：
C中的struct是没有权限设置的&#xff0c……

编程日记2023/4/16 14:50:59

docker的数据卷详解

数据卷 数据卷是宿主机中的一个目录或文件，当容器目录和数据卷目录绑定后，对方修改会立即同步
一个数据卷可以同时被多个容器同时挂载，一个容器也可以被挂载多个数据卷
数据卷作用：容器数据持久化 /外部机器和容器间接通信 /容器……

编程日记2023/4/16 14:50:50

13、Qt生成dll-QLibrary方式使用

Qt创建dll，使用QLibrary类方式调用dll
一、创建项目
1、新建项目->其他项目->Empty qmake Project->Choose 2、输入项目名，选择项目位置，下一步 3、选择MinGW，下一步 4、完成 5、.pro中添加TEMPLATE subdirs&#xff……

编程日记2023/4/16 14:50:38

基于mapreduce 的 minHash 矩阵压缩

Minhash作用： 对大矩阵进行降维处理，在进行计算俩个用户之间的相似度。
比如： 俩个用户手机下载的APP的相似度，在一个矩阵中会有很多很多的用户要比较没俩个用户之间的相似度是一个很大的计算任务 如果首先对这个矩阵降维处理&am……

编程日记2023/4/16 14:50:37

关于hashmap使用迭代器的问题

keySet获得的只是key值的集合，valueSet获得的是value集合，entryset获得的是键值对的集合。 package com.test2.test;import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;public class mapiterator……

编程日记2023/4/16 14:50:37