leetcode 516. 最长回文子序列(JAVA)题解

题目链接https://leetcode.cn/problems/longest-palindromic-subsequence/description/?utm_source=LCUS&utm_medium=ip_redirect&utm_campaign=transfer2china

目录

题目描述:

暴力递归:

动态规划:


题目描述:

给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。

示例 1:

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

示例 2:

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

提示:

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

这道题的知识点是动态规划,可是如果直接从动态规划讲可能有点不容易理解。

所以本篇文章就是从暴力递归到动态规划

从题目中我们可以得出:本题找的是可以不连续的回文子串然后返回其最大序列的长度。

也就是说:

a2b42a

的最长回文子序列为:a2b2a或a242a 这两个都可以因为它们返回的都是5

暴力递归:

我们先写一个可以返回最长的回文子序列长度的函数:

//主函数
public int longestPalindromeSubseq(String s) {
        char[] str = s.toCharArray();
        return maxString(str, 0, str.length-1);
}

//假设该函数可以返回最长回文子序列的长度
public static int maxString(char[] str, int l, int r) {}

我们写的 maxString() 方法可以返回 str 字符串[l, r]区间的最长回文子序列的长度 。

通过分析可以得出以下结论:

两种特殊情况:

  • 首先我们可以得到当 l 和 r 相等就证明此时只有一个字符那么它的返回值就是 1
  • 如果传入的数组只有两个字符即 l + 1 == r 那么此时如果这两个字符相等就返回 2 ,如果不相等就返回 1

普遍情况:

  • 两边的字符不存在于最长的回文子序列中。例:a1221b    ->   1221;
  • 右边的字符不存在在于最长的回文子序列中。例:1221b    ->   1221;
  • 左边的字符不存在在于最长的回文子序列中。例:a1221    ->   1221;
  • 两边的字符存在于最长的回文子序列中。例:1w221    ->   1221。

 此时代码就可以这样写:

//主函数
public int longestPalindromeSubseq(String s) {
        char[] str = s.toCharArray();
        return maxString(str, 0, str.length-1);
}

//假设该函数可以返回最长回文子序列的长度
public static int maxString(char[] str, int l, int r) {
        //先判断两种特殊情况
        if (l == r){
            return 1;
        }
        if (l + 1 == r){
            return str[l] == str[r] ? 2 : 1;
        }
        //余下的四种情况
        int a1 = maxString(str, l + 1, r - 1);
        int a2 = maxString(str, l, r - 1);
        int a3 = maxString(str, l + 1, r);
        int a4 = str[l] == str[r] ? 2 + maxString(str, l + 1, r - 1) : 0;
        
        //因为题目要求返回最长序列长度  所以需要返回这四个的最大值
        return Math.max(Math.max(a1, a2), Math.max(a3, a4));
}

 此时我们可以提交以下:

 虽然没通过但是从它的报错信息可以看出,我们的思路是没问题的。

动态规划:

我们有了递归版本后就可以根据它来写出动态规划版本了。

 因为在maxString() 方法中只有 l 和 r 是变量,而它们两个的取值范围都是 [0,str.length - 1] 

此时我们就可以通过创建一个二维数组将 l 和 r 所有情况都列举出来然后返回数组[0,str.length - 1] 下标的值就可以得出答案了。

我们先假设长度只有 5 ,那么我们就可以创建如下的二维数组 l 行,r 列

public static int maxString(char[] str, int l, int r) {

        int[][] arr = new int[str.length][str.length];
        
}

 

接下来的填表阶段就可以根据递归函数直接填(以“a1221”为例子): 

 

 

此时 [0, 4] 位置的值就是最终答案。 

 根据每个位置的关系就将递归优化成:

public static int maxString(char[] str, int l, int r) {

        int[][] arr = new int[str.length][str.length];
        //因为不存在l < r的情况所以下三角的空间不用
        for (int i = 0; i < str.length; i++) {
            if (i == 0){//填第一条对角线
                int j = 0;
                while(j < str.length) {
                    arr[j][j] = 1;
                    j++;
                }
            }else if (i == 1) {//填第二条斜线
                int j = 1;
                while(j < str.length) {
                    arr[j - 1][j] = (str[j - 1] == str[j]) ? 2 : 1;
                    j++;
                }
            }else {//其他
                int j = i;
                int k = 0;
                while(j < str.length){
                    int a1 = arr[k + 1][j - 1];
                    int a2 = arr[k][j - 1];
                    int a3 = arr[k + 1][j];
                    int a4 = str[k] == str[j] ? 2 + arr[k + 1][j - 1] : 0;
                    arr[k][j] = Math.max(Math.max(a1, a2), Math.max(a3, a4));
                    j++;
                    k++;
                }
            }

        }
        return arr[0][str.length-1];
}

此时再提交就过了。 

 

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【JVM】类装载的执行过程

文章目录 类装载的执行过程1.加载2.验证3.准备4.解析5.初始化6.使用7.卸载 类装载的执行过程 类装载总共分为7个过程&#xff0c;分别是 加载&#xff0c;验证&#xff0c;准备、解析、初始化、使用、卸载 1.加载 将类的字节码文件加载到内存(元空间&#xff09;中。这一步会…

智头条|DFM-2大模型吹热智能家居,360安全云正式发布

行业动态 DFM-2大模型吹热智能家居 近期,思必驰行业语言计算大模型DFM-2正式发布,也带来了人机交互能力的提升和优秀的技术落地能力。DFM-2大模型与DUI平台结合推出DUI2.0,完成了对话式AI全链路技术的升级,推进深度产业应用。在智能家居领域,目前思必驰已与海信、长虹美菱、老…

为什么要分库分表?

不急于上手实战 ShardingSphere 框架&#xff0c;先来复习下分库分表的基础概念&#xff0c;技术名词大多晦涩难懂&#xff0c;不要死记硬背理解最重要&#xff0c;当你捅破那层窗户纸&#xff0c;发现其实它也就那么回事。 什么是分库分表 分库分表是在海量数据下&#xff0…

JAVA电商平台免费搭建 B2B2C商城系统 多用户商城系统 直播带货 新零售商城 o2o商城 电子商务 拼团商城 分销商城 bbc

​ 1. 涉及平台 平台管理、商家端&#xff08;PC端、手机端&#xff09;、买家平台&#xff08;H5/公众号、小程序、APP端&#xff08;IOS/Android&#xff09;、微服务平台&#xff08;业务服务&#xff09; 2. 核心架构 Spring Cloud、Spring Boot、Mybatis、Redis 3. 前…

第三章:前端UI框架介绍

文章目录 一、Bootstrap1.1 Bootstrap简介及版本1.2 Bootstrap使用 二、AntDesign2.1 简介2.2 基本使用2.3 antd pro 三、ElementUI3.1 简介3.2 基本使用 四、Vant4.1 简介4.2 基本使用 一、Bootstrap 1.1 Bootstrap简介及版本 1、 简介 Bootstrap&#xff0c;来白 Twitter&a…

metaRTC7 demo mac/ios编译指南

概要 metaRTC7.0开始全面支持mac/ios操作系统&#xff0c;新版本7.0.023 mac os demo 包含有srs/zlm的推拉流演示。发布版自带了x64版第三方类库&#xff0c;arm版第三方类库还需开发者自己编译。 源码下载 下载文件metartc7.023.7z https://github.com/metartc/metaRTC/re…

【JavaEE进阶】SpringBoot 日志

文章目录 一. 日志有什么用?二. 自定义日志打印1. 日志的使用与打印 三. 日志级别1. 日志级别有什么用?2. 日志级别的分类及使用 四. 日志持久化五. 更简单的日志输出---Lombok1. Lombok的使用2. lombok原理解释2.1 Lombok更多注解说明 一. 日志有什么用? 在Java中&#xf…

IDE的下载和使用

IDE 文章目录 IDEJETBRAIN JETBRAIN 官网下载对应的ide 激活方式 dxm的电脑已经把这个脚本下载下来了&#xff0c;脚本是macjihuo 以后就不用买了

PDB Database - RCSB PDB 数据集 (2023.8) 的多维度信息统计

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/132297736 RCSB PDB 数据集是一个收集了蛋白质的三维结构信息的数据库&#xff0c;是世界蛋白质数据库&#xff08;wwPDB&#xff09;的成员之一&…

Redis辅助功能

一、Redis队列 1.1、订阅 subscribe ch1 ch2 1.2 publish:发布消息 publish channel message 1.3 unsubscribe: 退订 channel 1.4 模式匹配 psubscribe ch* 模糊发布&#xff0c;订阅&#xff0c;退订&#xff0c; p* <channelName> 1.5 发布订阅原理 订阅某个频道或…

高性能跨平台网络通信框架 HP-Socket v5.9.3

项目主页 : http://www.oschina.net/p/hp-socket开发文档 : https://www.docin.com/p-4478351216.html下载地址 : https://github.com/ldcsaa/HP-SocketQQ Group: 44636872, 663903943 v5.9.3 更新 一、主要更新 问题修复&#xff1a;通过 POST/PUT 等带有请求内容的 HTTP 方…

SQL进阶--SQL的常用技巧

一、ORDER BY FIELD() 自定义排序逻辑 排序 ORDER BY 除了可以用 ASC 和 DESC&#xff0c;还可以通过**ORDER BY FIELD(str,str1,...)**自定义字符串/数字来实现排序。这里用 order_diy 表举例&#xff0c;结构以及表数据展示&#xff1a; 二、CASE 表达式 「case when then el…

SAP ME2L/ME2M/ME3M报表增强添加字段(包含:LMEREPI02、SE18:ES_BADI_ME_REPORTING)

ME2L、ME2M、ME3M这三个报表的字段增强&#xff0c;核心点都在同一个结构里 SE11:MEREP_OUTTAB_PURCHDOC 在这里加字段&#xff0c;如果要加的字段是EKKO、EKPO里的数据&#xff0c;直接加进去&#xff0c;啥都不用做&#xff0c;就完成了 如果要加的字段不在EKKO和EKPO这两个…

Salesforce 为什么能够在 CRM 市场获得成功?

Salesforce 为什么能够在 CRM 市场获得成功&#xff1f; 虽然salesforce有着水土不服&#xff0c;数据安全等问题&#xff0c;但依旧受到了国内CRM系统使用者的追捧。 但是近年来国内的一些CRM平台也做得很不错了&#xff0c;我认为没必要执着于非本土系统。 下面就以一个CR…

SpringBoot 3自带的 HTTP 客户端工具

原理 Spring的HTTP 服务接口是一个带有HttpExchange方法的 Java 接口&#xff0c;它支持的支持的注解类型有&#xff1a; HttpExchange&#xff1a;是用于指定 HTTP 端点的通用注释。在接口级别使用时&#xff0c;它适用于所有方法。GetExchange&#xff1a;为 HTTP GET请求指…

【深度学习】日常笔记16

可以将pd.DataFrame数据结构理解为类似于Excel中的表格。pd.DataFrame是pandas库提供的一个二维数据结构&#xff0c;用于存储和操作具有行和列的数据。它类似于Excel中的工作表&#xff0c;其中每一列可以是不同的数据类型&#xff08;例如整数、浮点数、字符串等&#xff09;…

UNIAPP中开发企业微信小程序

概述 需求为使用uni-app开发企业微信小程序。希望可以借助现成的uni-app框架&#xff0c;快速开发。遇到的问题是uni-app引入jweixin-1.2.0.js提示异常: Reason: TypeError: Cannot read properties of undefined (reading ‘title’)。本文中描述了如何解决该问题&#xff0c…

提升物流管理效率,快递批量查询高手软件助你一臂之力

物流管理中&#xff0c;准确跟踪和掌握快递的物流信息是非常重要的。而快递批量查询高手软件的出现&#xff0c;大大提高了物流管理的效率&#xff0c;为企业带来了诸多便利。 传统的快递查询方式往往需要手动逐个输入快递单号&#xff0c;费时费力且容易出错。而有了快递批量查…

代理模式【Proxy Pattern】

什么是代理模式呢&#xff1f;我很忙&#xff0c;忙的没空理你&#xff0c;那你要找我呢就先找我的代理人吧&#xff0c;那代理人总要知道 被代理人能做哪些事情不能做哪些事情吧&#xff0c;那就是两个人具备同一个接口&#xff0c;代理人虽然不能干活&#xff0c;但是被 代…

React 之 Suspense和lazy

一. Suspense 参考链接&#xff1a;https://react.docschina.org/reference/react/Suspense suspense&#xff1a;n. 焦虑、悬念 <Suspense> 允许你显示一个退路方案&#xff08;fallback&#xff09;直到它的所有子组件完成加载。 <Suspense fallback{<Loadin…