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 ,找出其中最长的回文子序列,并返回该序列的长度。 子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。 示例 1: 输入:s …...
Kafka - 异步/同步发送API
文章目录 异步发送普通异步发送异步发送流程Code 带回调函数的异步发送带回调函数的异步发送流程Code 同步发送API 异步发送 普通异步发送 需求:创建Kafka生产者,采用异步的方式发送到Kafka broker 异步发送流程 Code <!-- https://mvnrepository…...
嵌套for循环在外层循环和内层循环中使用两个Executors.newCachedThreadPool缓存线程池执行操作
1. 首先,我们需要创建两个ExecutorService对象,这两个对象将作为我们的缓存线程池。 2. 然后,我们使用嵌套的for循环来执行我们的操作。在每个外层循环中,我们将创建一个新的任务并提交给外层线程池。在这个任务中,我…...
【uniapp+云函数调用】人脸识别,实人认证,适用于app,具体思路解析,已实现
2023.10.8 需求: uniapp开发的app项目中使用人脸识别 app项目都是第一次搞,更别提人脸识别了。目前已有的就是Dcloud账号已申请,实现需求的时间没那么紧迫 此篇会详细记录从0到1的过程 2023.10.24 今天开始探究实现的过程 可能会记录的有些冗余 效果图如下: uniapp开发指南…...
系列十六、bean有哪些生命周期的回调方法?有哪几种实现方式?
一、概述 bean的生命周期的回调方法主要分两种,一种是初始化时进行调用,另外一种是销毁时进行调用。但是不管是初始化还是销毁,都对应着三种方式。 二、实现方式 2.1、注解方式 PostConstruct PreDestroy Component public class UserSe…...
2023平台工程崭露头角,AI 带来新机遇与挑战
在今年,平台工程正在迅速在 IT 企业中崭露头角,成为软件开发团队的必要实践。根据 CloudBees 发布的最新报告《2023年平台工程:快速采纳和影响》,83%的受访者已经完全实施了平台工程,或正处于某种实施阶段。 平台工…...
如何使用python快速修改Excel表单中的大量数据
python修改Excel中的内容进阶加速版 前面有一篇文章讲到了使用python处理Excel中的数据文件,即修改Excel中的数据,但是那个版本的代码跑点小规模、小数据量的excel还行,一旦数据量达到万条级别,代码运行会非常慢!因此&…...
✔ ★【备战实习(面经+项目+算法)】 10.27学习
✔ ★【备战实习(面经项目算法)】 坚持完成每天必做如何找到好工作1. 科学的学习方法(专注!效率!记忆!心流!)2. 每天认真完成必做项,踏实学习技术 认真完成每天必做&…...
视频分辨率/帧率/码率选择参考
1. 视频码率与分辨率的参考表 1080*720的分辨率,用5000K左右; 720*576的分辨率,用3500K左右; 640*480的分辨率,用1500K左右。 2. 计算公式 基本算法:码率(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(New I/O)相比于传统的Java I/O(BIO)在高并发开发方面具有以下优势: 非阻塞模式:Java NIO使用非阻塞的I/O操作,允许一个线程管理多个通道(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有哪些优点和缺点?
随着互联网的普及,越来越多的人开始关注网络安全和隐私保护。其中,公网IP的设置成为了一个备受关注的话题。本文将详细介绍公网IP的设置方法以及公网IP的优点和缺点。 一、公网IP设置方法 1. 路由器设置 在家庭或企业网络中,路由器通常是最重…...
蓝桥杯第 2 场算法双周赛 第2题 铺地板【算法赛】c++ 数学思维
题目 铺地板https://www.lanqiao.cn/problems/5887/learning/?contest_id145 问题描述 小蓝家要装修了,小蓝爸爸买来了很多块(你可以理解为数量无限)2323 规格的地砖,小蓝家的地板是 nm 规格的,小蓝想问你…...
APScheduler-调度器 BackgroundScheduler
当你有主程序需要执行,让定时任务在后台执行时,可以用BackgroundScheduler from apscheduler.schedulers.background import BackgroundScheduler import time # 仅运行定时任务 scheduler BackgroundScheduler() # interval example, 间隔执行,…...
浅谈UI自动化测试
随着软件行业的不断发展,建立一个完善的自动化测试体系变得至关重要。目前,自动化测试主要涵盖接口自动化测试和UI自动化测试两个主要领域。就目前而言,企业在UI自动化测试方面的覆盖率仍然相对较低。 接口自动化测试可以模拟和执行应用程序…...
golang 工程组件 grpc-gateway—yaml定义http规则,和自定义实现网关路由
yaml定义http规则,和自定义实现网关路由 proto定义http规则总归是麻烦的,因为proto文件还是定义消息,grpc接口好一些。配置http规则有更好的方式。我们可以使用yaml文件定义接口的http规则。 同时有些接口不是只是让网关转发这么简单 有时需…...
在NLP中一下常见的任务,可以用作baseline;MRPC,CoLA,STS-B,RTE
1.MRPC(Microsoft Research Paraphrase Corpus)任务 是一个用于文本匹配和相似度判断的任务。在MRPC任务中,给定一对句子,模型需要判断它们是否是语义上等价的。MRPC任务的训练集和测试集由约5700对英语句子组成。每个句子对都有…...
【计算机网络笔记】Cookie技术
系列文章目录 什么是计算机网络? 什么是网络协议? 计算机网络的结构 数据交换之电路交换 数据交换之报文交换和分组交换 分组交换 vs 电路交换 计算机网络性能(1)——速率、带宽、延迟 计算机网络性能(2)…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...
JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案
JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停 1. 安全点(Safepoint)阻塞 现象:JVM暂停但无GC日志,日志显示No GCs detected。原因:JVM等待所有线程进入安全点(如…...
tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...
AspectJ 在 Android 中的完整使用指南
一、环境配置(Gradle 7.0 适配) 1. 项目级 build.gradle // 注意:沪江插件已停更,推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...
HashMap中的put方法执行流程(流程图)
1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中,其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下: 初始判断与哈希计算: 首先,putVal 方法会检查当前的 table(也就…...
