【Java程序设计】动态规划算法专题（六）：回文串问题

目录

1、回文子串（"引子题"）

1.1 算法原理 

1.2 算法代码

2、最长回文子串

2.1 算法原理

2.2 算法代码

3、分割回文串 IV（hard）

3.1 算法原理

3.2 算法代码

4、分割字符串 II（hard）

4.1 算法原理 

4.2 算法代码

5、最长回文子序列

5.1 算法原理 

5.2 算法代码

6、让字符串成为回文串的最少插入次数（hard）

6.1 算法原理

6.2 算法代码

1、回文子串（"引子题"）

. - 力扣（LeetCode）

1.1 算法原理 

  • 状态表示：

dp[i][j]：[i, j]区间内的子串，是否回文(i <= j)

  • 状态转移方程：

s[i] == s[j]：

1. i == j --> true 
2. i+1==j --> s(i) == s(j) ? true : false
3. s(i) == s(j) --> dp[i+1][j-1]

  • 初始化：

无需初始化（状态转移方程的前两种情况已处理特殊的边界情况）

  • 建表顺序：

从下往上(根据状态转移方程)

  • 返回值：

dp表中有几个true

1.2 算法代码

class Solution {public int countSubstrings(String ss) {char[] s = ss.toCharArray();int n = s.length;boolean[][] dp = new boolean[n][n];int ret = 0;// 填表 --> 从下往上for(int i = n - 1; i >= 0; i--) {// j >= ifor(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];}if(dp[i][j]) ret++;}}return ret;}
}

2、最长回文子串

. - 力扣（LeetCode）

2.1 算法原理

本题算法原理与题一完全一致，最终返回最长的回文子串即可。

  • 状态表示：

dp[i][j]：[i, j]区间内的子串，是否回文(i <= j)

  • 状态转移方程：

s[i] == s[j]：

1. i == j --> true 
2. i+1==j --> s(i) == s(j) ? true : false
3. s(i) == s(j) --> dp[i+1][j-1]

  • 初始化：

无需初始化（状态转移方程的前两种情况已处理特殊的边界情况）

  • 建表顺序：

从下往上(根据状态转移方程)

  • 返回值：

最长回文子串

2.2 算法代码

class Solution {public String longestPalindrome(String ss) {char[] s = ss.toCharArray();int n = s.length;boolean[][] dp = new boolean[n][n];String ret = "";int begin = 0;int end = 0;// 建表 --> 从下往上for(int i = n - 1; i >= 0; i--) {for(int j = i; j < n; j++) {// i <= jif(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];}if(dp[i][j]) {// 记录最长回文子串的起始和末尾位置if(j - i + 1 > end - begin + 1) {begin = i;end = j;}} }}return ss.substring(begin, end + 1);}
}

3、分割回文串 IV（hard）

. - 力扣（LeetCode）

3.1 算法原理

本题算法原理依旧是在题一判断好哪些子串是回文的基础上，分割字符串，判断是否存在三个回文串即可。

  • 状态表示：

dp[i][j]：[i, j]区间内的子串，是否回文(i <= j)

  • 状态转移方程：

s[i] == s[j]：

1. i == j --> true 
2. i+1==j --> s(i) == s(j) ? true : false
3. s(i) == s(j) --> dp[i+1][j-1]

  • 初始化：

无需初始化（状态转移方程的前两种情况已处理特殊的边界情况）

  • 建表顺序：

从下往上(根据状态转移方程)

  • 返回值：

是否存在三个回文串。

3.2 算法代码

class Solution {public boolean checkPartitioning(String ss) {char[] s = ss.toCharArray();int n = s.length;boolean[][] dp = new boolean[n][n];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];}}}// 从 i,j 位置 分割字符串for(int i = 1; i < n; i++) {for(int j = i; j < n - 1; j++) {if(dp[0][i - 1] && dp[i][j] && dp[j + 1][n - 1]) return true;}}return false;}
}

4、分割字符串 II（hard）

. - 力扣（LeetCode）

4.1 算法原理 

本题仍然在题一中 通过二维dp保存所有子串的是否回文的信息 的基础上解题。

  • 状态表示：

dp[i]：以[0, i]区间内的子串，最少的分割次数

  • 状态转移方程：

1. 0~i 回文 --> 0
2. 0~i 不回文 --> 0 < j < = i --> 若子串[ j, i ]回文 --> min(dp[ j - 1 ] + 1)

  • 初始化：

dp表中所有元素初始化为Integer.MAX_VALUE

  • 建表顺序：

从左往右

  • 返回值：

dp[n-1]

4.2 算法代码

class Solution {public int minCut(String ss) {char[] s = ss.toCharArray();int n = s.length;boolean[][] isPal = new boolean[n][n];for (int i = n - 1; i >= 0; i--) {for (int j = i; j < n; j++) {if (s[i] == s[j]) {if (i == j)isPal[i][j] = true;else if (i + 1 == j)isPal[i][j] = true;elseisPal[i][j] = isPal[i + 1][j - 1];}}}int[] dp = new int[n];// 初始化Arrays.fill(dp, Integer.MAX_VALUE);for (int i = 0; i < n; i++) {if (isPal[0][i])dp[i] = 0;else {// j --> (0, i]for (int j = 1; j <= i; j++) {if (isPal[j][i])dp[i] = Math.min(dp[i], dp[j - 1] + 1);}}}return dp[n - 1];}
}

5、最长回文子序列

. - 力扣（LeetCode）

5.1 算法原理 

  • 状态表示：

dp[i][j]：s字符串[i , j]区间内的所有子序列中，最长回文子序列的长度

  • 状态转移方程：

1. s[i] == s[j]：

i==j --> 1
i+1==j --> 2
dp[i+1][j-1]+2

2. s[i] != s[j]：

max(dp[i][j-1], dp[i+1][j])

  • 初始化：

无需初始化

  • 建表顺序：

从下往上填写每一行，每一行从左往右填写每一列

  • 返回值：

dp[0][n-1]

5.2 算法代码

class Solution {public int longestPalindromeSubseq(String ss) {char[] s = ss.toCharArray();int n = s.length;int[][] dp = new int[n][n];// 从下往上填每一行// 每一行从左往右填每一列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] = 1;else if(i + 1 == j) dp[i][j] = 2;else dp[i][j] = dp[i + 1][j - 1] + 2;}else {dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);}}}return dp[0][n - 1];}
}

6、让字符串成为回文串的最少插入次数（hard）

. - 力扣（LeetCode）

6.1 算法原理

  • 状态表示：

dp[i][j]：字符串[i, j]区间内的子串，使它成为回文串的最小插入次数

  • 状态转移方程：

s[i] == s[j]：

1. i == j --> 0

2. i + 1 == j --> 0

3. dp[i + 1][j - 1]

s[i] != s[j]：

min(dp[i + 1][j], dp[i][j - 1]) + 1;

  • 初始化：

无需初始化

  • 建表顺序：

从上到下每一行
从左往右每一列

  • 返回值：

dp[0][n-1]

6.2 算法代码

class Solution {public int minInsertions(String ss) {char[] s = ss.toCharArray();int n = s.length;int[][] dp = new int[n][n];// 无需初始化// 建表 --> 从上往下每一行，从左往右每一列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] = 0;else if(i + 1 == j) dp[i][j] = 0;else dp[i][j] = dp[i + 1][j - 1];}else dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;}}return dp[0][n - 1];}
}

END

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

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

相关文章

HAL库常用的函数：

HAL库常用的函数：

目录 HAL库&#xff1a; 1.GPIO常用函数&#xff1a; 1.HAL_GPIO_ReadPin( ) 2.HAL_GPIO_WritePin( ) 3.HAL_GPIO_TogglePin( ) 4.HAL_GPIO_EXTI_IRQHandler( ) 5.HAL_GPIO_EXTI_Callback( ) 2.UART常用函数&#xff1a; 1.HAL_U…
阅读更多...
深度学习笔记（持续更新）

深度学习笔记（持续更新）

注&#xff1a;本文所有深度学习内容都是基于PyTorch&#xff0c;PyTorch作为一个开源的深度学习框架&#xff0c;具有可以动态计算图、拥有简洁易用的API、支持GPU加速等特点&#xff0c;在计算机视觉、自然语言处理、强化学习等方面有广泛应用。 使用matplotlib绘图&#xff…
阅读更多...
Python | Leetcode Python题解之第468题验证IP地址

Python | Leetcode Python题解之第468题验证IP地址

题目&#xff1a; 题解&#xff1a; class Solution:def validIPAddress(self, queryIP: str) -> str:if queryIP.find(".") ! -1:# IPv4last -1for i in range(4):cur (len(queryIP) if i 3 else queryIP.find(".", last 1))if cur -1:return &q…
阅读更多...
计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-10-10

计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-10-10

计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-10-10 1. Characterizing and Efficiently Accelerating Multimodal Generation Model Inference Y Lee, A Sun, B Hosmer, B Acun, C Balioglu, C Wang… - arXiv preprint arXiv …, 2024 https://arxiv.org/pdf…
阅读更多...
如何使用Colly库进行大规模数据抓取？

如何使用Colly库进行大规模数据抓取？

在互联网时代&#xff0c;数据的价值日益凸显&#xff0c;大规模数据抓取成为获取信息的重要手段。Go语言因其高效的并发处理能力&#xff0c;成为编写大规模爬虫的首选语言。Colly库作为Go语言中一个轻量级且功能强大的爬虫框架&#xff0c;能够满足大规模数据抓取的需求。本文…
阅读更多...
C语言 | Leetcode C语言题解之第467题环绕字符串中唯一的子字符串

C语言 | Leetcode C语言题解之第467题环绕字符串中唯一的子字符串

题目&#xff1a; 题解&#xff1a; #define MAX(a, b) ((a) > (b) ? (a) : (b))int findSubstringInWraproundString(char * p) {int dp[26];int len strlen(p);memset(dp, 0, sizeof(dp));int k 0;for (int i 0; i < len; i) {if (i && (p[i] - p[i - 1] …
阅读更多...
动态线程池设计与实现

动态线程池设计与实现

为什么要有动态线程池 ThreadPoolExecutor 核心线程参数对某些业务不知到设置多少合适调整参数需要重新启动服务没有告警功能 设计思路 流程设计 库表抽象 更新操作流程图 代码实现 GitCode - 全球开发者的开源社区,开源代码托管平台
阅读更多...
太阳诱电电感选型方法及产品介绍

太阳诱电电感选型方法及产品介绍

功率电感在电子电路中被广泛应用&#xff0c;太阳诱电的功率电感从原材料开始进行研发&#xff0c;生产和销售。 本次研讨会将带领大家更加了解功率电感的选型方法&#xff0c;以及各种功率电感的种类和特征。 此外&#xff0c;也将介绍太阳诱电的最新产品阵容。本次研讨会预计…
阅读更多...
python之详解集合

python之详解集合

一种无序且不重复的数据容器&#xff0c;集合用大括号{}表示。 1、集合的查找访问 集合是不能通过 集合名[index] 这种方式访问的&#xff0c;其作用在于快速读取&#xff0c;而不是针对某个元素。 但&#xff0c;可将集合转为列表&#xff0c;再由列表访问元素。不过&#…
阅读更多...
Spring Boot 进阶-实战Spring Boot整合Swagger3.0

Spring Boot 进阶-实战Spring Boot整合Swagger3.0

说到Swagger有人会问Swagger到底是什么？作为一个后端开发人员来讲，为什么要使用Swagger呢？因为我们现在完成的项目大多数情况下都是前后端分离的项目，而对于前端开发人员来讲，他们需要调用接口，才能获取到对应的数据。那么这个接口如何获取，总不能是后端开发人员弄好之后…
阅读更多...
xianshan分支预测单元基础与top层介绍

xianshan分支预测单元基础与top层介绍

xianshan分支预测单元基础与top层接口介绍 2 xianshan BPU分支预测器总体架构2.1 分支预测器块思想2.2 多预测器2.3 多流水线2.4 取值目标队列--FTQ2.4.1 BPU预测结果内部重定向2.4.2 FTQ2BPU 重定向请求2.4.4 BPU的update请求 2.5 总结 在这里重点介绍xianshan分支预测单元BPU…
阅读更多...
数学建模算法与应用 第8章 时间序列分析

数学建模算法与应用 第8章 时间序列分析

目录 8.1 确定性时间序列分析方法 Matlab代码示例&#xff1a;移动平均法提取趋势 8.2 平稳时间序列模型 Matlab代码示例&#xff1a;差分法与ADF检验 8.3 时间序列的Matlab相关工具箱及命令 Matlab代码示例&#xff1a;ARIMA模型的建立 8.4 ARIMA序列与季节性序列 Matl…
阅读更多...
开发环境搭建之NVM管理NODE安装

开发环境搭建之NVM管理NODE安装

由于项目繁多前端node环境代码不统一、所以安装切换不同版本node、所以在此记录一下安装过程&#xff1a; 下载NVM工具 nvm zip github下载安装包 简单粗暴一看就会、直接从官网下载zip安装包、然后执行命令安装所需node版本即可 下载之后直接安装&#xff1a; 安装完成之…
阅读更多...
linux执行脚本的时候为什么要写成 ./脚本名 而不是用脚本名直接执行

linux执行脚本的时候为什么要写成 ./脚本名 而不是用脚本名直接执行

原因&#xff1a; 一定要写成 ./test.sh&#xff0c;而不是 test.sh&#xff0c;运行其它二进制的程序也一样&#xff0c;直接写 test.sh&#xff0c;linux 系统会去 PATH 里寻找有没有叫 test.sh 的&#xff0c;而只有 /bin, /sbin, /usr/bin&#xff0c;/usr/sbin 等在 PATH…
阅读更多...
查询v$asm_disk等待enq: DD - contention

查询v$asm_disk等待enq: DD - contention

1.两个节点查询v$asm_disk均卡住&#xff0c;等待enq: DD - contention&#xff0c;阻塞源头为rbal进程&#xff0c;rbal进程未发生阻塞&#xff0c;未在异常等待事件上。 2.阻塞源头RBAL&#xff0c;在CPU上运行。没有在做rebalance磁盘平衡。 3.diag诊断日志中&#xff0c;阻…
阅读更多...
python实现3D立柱图demo

python实现3D立柱图demo

import matplotlib.pyplot as plt import numpy as np plt.rcParams["font.sans-serif"] ["SimHei"] # 设置字体 plt.rcParams["axes.unicode_minus"] False # 该语句解决图像中的“-”负号的乱码问题# 数据 regions [东北, 中南, 华东, 华…
阅读更多...
飞腾CPU技术发展分析

飞腾CPU技术发展分析

飞腾CPU剖析 CPU&#xff1a;信创根基&#xff0c;国之重器 国产CPU市场呈现三大领军阵营&#xff1a;x86、ARM以及其他创新架构。鲲鹏与飞腾在ARM阵营中引领风潮&#xff0c;依托ARM技术授权研发高性能处理器&#xff1b;海光与兆芯则以x86架构为基石&#xff0c;深入挖掘其潜…
阅读更多...
数学建模算法与应用 第7章 数理统计与方法

数学建模算法与应用 第7章 数理统计与方法

目录 7.1 参数估计与假设检验 Matlab代码示例&#xff1a;均值的假设检验 7.2 Bootstrap方法 Matlab代码示例&#xff1a;Bootstrap估计均值的置信区间 7.3 方差分析 Matlab代码示例&#xff1a;单因素方差分析 7.4 回归分析 Matlab代码示例&#xff1a;线性回归 7.5 基…
阅读更多...
Registry私有仓库可视化

Registry私有仓库可视化

Docker Registry 是一个用于存储和分发 Docker 镜像的服务&#xff0c;它支持构建私有仓库来管理组织内部的应用程序和镜像。然而&#xff0c;默认的 Docker Registry 并没有提供图形界面&#xff0c;这使得管理镜像变得不太直观。为了方便管理和查看私有仓库中的镜像&#xff…
阅读更多...
显卡 3090 vs v100

显卡 3090 vs v100

1.3090 Date: 2020 AmperePielines/ Cuda cores: 10496 2.V100 Date: 2018 VoltaPielines/ Cuda cores: 5129 3.结构 & Core比较: v100优点: v100功耗小v100较快的双精度(fp64)和混合精度(fp16fp32)pcie版的NVLink与2080ti完全一致 v100缺点: 不支持整数格式计算&…
阅读更多...
最新文章

Copyright @ 2022~2023