当前位置: 首页 > news >正文

516 最长回文子序列(区间DP)(灵神笔记)

题目

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

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

示例 1:

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

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

提示:

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

题解

记忆化搜索

class Solution {private char[] str;private int[][] cache;public int longestPalindromeSubseq(String s) {this.str = s.toCharArray();int n = str.length;cache = new int[n][n];for (int i = 0; i < n; i++) {Arrays.fill(cache[i], -1);}return dfs(0, n - 1);}private int dfs(int i, int j) {if (i > j) {return 0;}if (i == j) {return 1;}if (cache[i][j] != -1) {return cache[i][j];}if (str[i] == str[j]) {return cache[i][j] = dfs(i + 1, j - 1) + 2; //都选}//选或不选return cache[i][j] = Math.max(dfs(i + 1, j), dfs(i, j - 1));}
}

时间复杂度:O(n^2) 一共有n*n个状态
空间复杂度:O(n^2)

递推

class Solution {public int longestPalindromeSubseq(String s) {char[] str = s.toCharArray();int n = str.length;int[][] f = new int[n][n];for (int i = n - 1; i >= 0; i--) {f[i][i] = 1; // i==jfor (int j = i + 1; j < n; j++) {f[i][j] = str[i] == str[j] ? f[i + 1][j - 1] + 2 :Math.max(f[i + 1][j], f[i][j - 1]);}}return f[0][n - 1];}
}

时间复杂度:O(n^2) 一共有n*n个状态
空间复杂度:O(n^2)

空间优化

class Solution {public int longestPalindromeSubseq(String s) {char[] str = s.toCharArray();int n = str.length;int[] f = new int[n];for (int i = n - 1; i >= 0; i--) {f[i] = 1; // i==jint pre = 0; // f[i+1][i]for (int j = i + 1; j < n; j++) {int tmp = f[j];f[j] = str[i] == str[j] ? pre + 2 : Math.max(f[j], f[j - 1]);pre = tmp;}}return f[n - 1];}
}

时间复杂度:O(n^2) 一共有n*n个状态
空间复杂度:O(n)

相关文章:

516 最长回文子序列(区间DP)(灵神笔记)

题目 最长回文子序列 给你一个字符串 s &#xff0c;找出其中最长的回文子序列&#xff0c;并返回该序列的长度。 子序列定义为&#xff1a;不改变剩余字符顺序的情况下&#xff0c;删除某些字符或者不删除任何字符形成的一个序列。 示例 1&#xff1a; 输入&#xff1a;s …...

Kafka - 异步/同步发送API

文章目录 异步发送普通异步发送异步发送流程Code 带回调函数的异步发送带回调函数的异步发送流程Code 同步发送API 异步发送 普通异步发送 需求&#xff1a;创建Kafka生产者&#xff0c;采用异步的方式发送到Kafka broker 异步发送流程 Code <!-- https://mvnrepository…...

嵌套for循环在外层循环和内层循环中使用两个Executors.newCachedThreadPool缓存线程池执行操作

1. 首先&#xff0c;我们需要创建两个ExecutorService对象&#xff0c;这两个对象将作为我们的缓存线程池。 2. 然后&#xff0c;我们使用嵌套的for循环来执行我们的操作。在每个外层循环中&#xff0c;我们将创建一个新的任务并提交给外层线程池。在这个任务中&#xff0c;我…...

【uniapp+云函数调用】人脸识别,实人认证,适用于app,具体思路解析,已实现

2023.10.8 需求: uniapp开发的app项目中使用人脸识别 app项目都是第一次搞,更别提人脸识别了。目前已有的就是Dcloud账号已申请,实现需求的时间没那么紧迫 此篇会详细记录从0到1的过程 2023.10.24 今天开始探究实现的过程 可能会记录的有些冗余 效果图如下: uniapp开发指南…...

系列十六、bean有哪些生命周期的回调方法?有哪几种实现方式?

一、概述 bean的生命周期的回调方法主要分两种&#xff0c;一种是初始化时进行调用&#xff0c;另外一种是销毁时进行调用。但是不管是初始化还是销毁&#xff0c;都对应着三种方式。 二、实现方式 2.1、注解方式 PostConstruct PreDestroy Component public class UserSe…...

2023平台工程崭露头角,AI 带来新机遇与挑战

在今年&#xff0c;平台工程正在迅速在 IT 企业中崭露头角&#xff0c;成为软件开发团队的必要实践。根据 CloudBees 发布的最新报告《2023年平台工程&#xff1a;快速采纳和影响》&#xff0c;83%的受访者已经完全实施了平台工程&#xff0c;或正处于某种实施阶段。 平台工…...

如何使用python快速修改Excel表单中的大量数据

python修改Excel中的内容进阶加速版 前面有一篇文章讲到了使用python处理Excel中的数据文件&#xff0c;即修改Excel中的数据&#xff0c;但是那个版本的代码跑点小规模、小数据量的excel还行&#xff0c;一旦数据量达到万条级别&#xff0c;代码运行会非常慢&#xff01;因此&…...

✔ ★【备战实习(面经+项目+算法)】 10.27学习

✔ ★【备战实习&#xff08;面经项目算法&#xff09;】 坚持完成每天必做如何找到好工作1. 科学的学习方法&#xff08;专注&#xff01;效率&#xff01;记忆&#xff01;心流&#xff01;&#xff09;2. 每天认真完成必做项&#xff0c;踏实学习技术 认真完成每天必做&…...

视频分辨率/帧率/码率选择参考

1. 视频码率与分辨率的参考表 1080&#xff0a;720的分辨率&#xff0c;用5000K左右&#xff1b; 720&#xff0a;576的分辨率&#xff0c;用3500K左右&#xff1b; 640&#xff0a;480的分辨率&#xff0c;用1500K左右。 2. 计算公式 基本算法&#xff1a;码率&#xff08;kb…...

LeetCode75——Day18

文章目录 一、题目二、题解 一、题目 1732. Find the Highest Altitude There is a biker going on a road trip. The road trip consists of n 1 points at different altitudes. The biker starts his trip on point 0 with altitude equal 0. You are given an integer …...

Java NIO 高并发开发

Java NIO 高并发开发 前言 Java NIO&#xff08;New I/O&#xff09;相比于传统的Java I/O&#xff08;BIO&#xff09;在高并发开发方面具有以下优势&#xff1a; 非阻塞模式&#xff1a;Java NIO使用非阻塞的I/O操作&#xff0c;允许一个线程管理多个通道&#xff08;Channe…...

8.循环神经网络

#pic_center R 1 R_1 R1​ R 2 R^2 R2 目录 知识框架No.1 序列模型一、序列模型二、D2L代码注意点三、QA No.2 文本预处理一、D2L代码注意点二、QA No.3 语言模型一、语言模型二、D2L代码注意点三、QA No.4 循环神经网络 RNN一、RNN二、QA No.5 循环神经网络 RNN 的实现一、从零…...

[C++随想录] map和set的使用

map和set的使用 set初始化finderasecountlower_bound && upper_boundequal_ range mapinsert[ ]运算符 multiset && multimap set — — key模拟 map — — key_value模型 set 初始化 void set_test1() {set<int>s;s.insert(10);s.insert(12);s.insert(…...

公网IP怎么设置?公网ip有哪些优点和缺点?

随着互联网的普及&#xff0c;越来越多的人开始关注网络安全和隐私保护。其中&#xff0c;公网IP的设置成为了一个备受关注的话题。本文将详细介绍公网IP的设置方法以及公网IP的优点和缺点。 一、公网IP设置方法 1. 路由器设置 在家庭或企业网络中&#xff0c;路由器通常是最重…...

蓝桥杯第 2 场算法双周赛 第2题 铺地板【算法赛】c++ 数学思维

题目 铺地板https://www.lanqiao.cn/problems/5887/learning/?contest_id145 问题描述 小蓝家要装修了&#xff0c;小蓝爸爸买来了很多块&#xff08;你可以理解为数量无限&#xff09;2323 规格的地砖&#xff0c;小蓝家的地板是 nm 规格的&#xff0c;小蓝想问你&#xf…...

APScheduler-调度器 BackgroundScheduler

当你有主程序需要执行&#xff0c;让定时任务在后台执行时&#xff0c;可以用BackgroundScheduler from apscheduler.schedulers.background import BackgroundScheduler import time # 仅运行定时任务 scheduler BackgroundScheduler() # interval example, 间隔执行,…...

浅谈UI自动化测试

随着软件行业的不断发展&#xff0c;建立一个完善的自动化测试体系变得至关重要。目前&#xff0c;自动化测试主要涵盖接口自动化测试和UI自动化测试两个主要领域。就目前而言&#xff0c;企业在UI自动化测试方面的覆盖率仍然相对较低。 接口自动化测试可以模拟和执行应用程序…...

golang 工程组件 grpc-gateway—yaml定义http规则,和自定义实现网关路由

yaml定义http规则&#xff0c;和自定义实现网关路由 proto定义http规则总归是麻烦的&#xff0c;因为proto文件还是定义消息&#xff0c;grpc接口好一些。配置http规则有更好的方式。我们可以使用yaml文件定义接口的http规则。 同时有些接口不是只是让网关转发这么简单 有时需…...

在NLP中一下常见的任务,可以用作baseline;MRPC,CoLA,STS-B,RTE

1.MRPC&#xff08;Microsoft Research Paraphrase Corpus&#xff09;任务 是一个用于文本匹配和相似度判断的任务。在MRPC任务中&#xff0c;给定一对句子&#xff0c;模型需要判断它们是否是语义上等价的。MRPC任务的训练集和测试集由约5700对英语句子组成。每个句子对都有…...

【计算机网络笔记】Cookie技术

系列文章目录 什么是计算机网络&#xff1f; 什么是网络协议&#xff1f; 计算机网络的结构 数据交换之电路交换 数据交换之报文交换和分组交换 分组交换 vs 电路交换 计算机网络性能&#xff08;1&#xff09;——速率、带宽、延迟 计算机网络性能&#xff08;2&#xff09;…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

蓝桥杯3498 01串的熵

问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798&#xff0c; 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

宇树科技,改名了!

提到国内具身智能和机器人领域的代表企业&#xff0c;那宇树科技&#xff08;Unitree&#xff09;必须名列其榜。 最近&#xff0c;宇树科技的一项新变动消息在业界引发了不少关注和讨论&#xff0c;即&#xff1a; 宇树向其合作伙伴发布了一封公司名称变更函称&#xff0c;因…...

jmeter聚合报告中参数详解

sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample&#xff08;样本数&#xff09; 表示测试中发送的请求数量&#xff0c;即测试执行了多少次请求。 单位&#xff0c;以个或者次数表示。 示例&#xff1a;…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...

LOOI机器人的技术实现解析:从手势识别到边缘检测

LOOI机器人作为一款创新的AI硬件产品&#xff0c;通过将智能手机转变为具有情感交互能力的桌面机器人&#xff0c;展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家&#xff0c;我将全面解析LOOI的技术实现架构&#xff0c;特别是其手势识别、物体识别和环境…...

认识CMake并使用CMake构建自己的第一个项目

1.CMake的作用和优势 跨平台支持&#xff1a;CMake支持多种操作系统和编译器&#xff0c;使用同一份构建配置可以在不同的环境中使用 简化配置&#xff1a;通过CMakeLists.txt文件&#xff0c;用户可以定义项目结构、依赖项、编译选项等&#xff0c;无需手动编写复杂的构建脚本…...

Python学习(8) ----- Python的类与对象

Python 中的类&#xff08;Class&#xff09;与对象&#xff08;Object&#xff09;是面向对象编程&#xff08;OOP&#xff09;的核心。我们可以通过“类是模板&#xff0c;对象是实例”来理解它们的关系。 &#x1f9f1; 一句话理解&#xff1a; 类就像“图纸”&#xff0c;对…...

Mac flutter环境搭建

一、下载flutter sdk 制作 Android 应用 | Flutter 中文文档 - Flutter 中文开发者网站 - Flutter 1、查看mac电脑处理器选择sdk 2、解压 unzip ~/Downloads/flutter_macos_arm64_3.32.2-stable.zip \ -d ~/development/ 3、添加环境变量 命令行打开配置环境变量文件 ope…...