day57回文子串_最长回文子序列
力扣647.回文子串
题目链接:https://leetcode.cn/problems/palindromic-substrings/
思路
dp数组含义
dp[i][j]:以s[i]为开头,s[j]为结尾的子串是否是回文子串
递推公式
子串范围为[i,j],当s[i]==s[j]时,有三种情况:
(1)i==j,如[a],dp[i][j]=true,同时计数器res++;
(2)j=i+1,如[a,a],dp[i][j]=true,同时计数器res++;
(3)j-i>1,那么就需要判断子串内部,即[i+1,j-1]范围内是否是回文子串,如果是,则dp[i][j]=true;否则为false。
初始化
初始化为false
遍历顺序
由递推公式可知,dp[i][j]由dp[i+1][j-1]推导而来,所以要从底往上,从左到右遍历。
打印数组
返回计数器res。
完整代码
class Solution {public int countSubstrings(String s) {boolean[][] dp = new boolean[s.length()][s.length()];int res = 0;for (int i = s.length()-1; i >= 0; i--) {for (int j = i; j < s.length(); j++) {if(s.charAt(i) == s.charAt(j)){if(j - i <= 1) {dp[i][j] = true;res++;}else if (dp[i+1][j-1] == true){dp[i][j] = true;res++;}}}}return res;}
}
力扣516.最长回文子序列
题目链接:https://leetcode.cn/problems/longest-palindromic-subsequence/
思路
本题和回文子串的区别是:子序列是不要求连续的,可以删除字符!
dp数组含义
dp[i][j]:在[i,j]范围内的最长回文子序列的长度
递推公式
(1)s[i]==s[j]时,dp[i][j] = dp[i+1][j-1]+2,这个很好理解,+2是加上两端的字符
(2)s[i]!=s[j]时,说明两端字符同时加进去时不能构成回文字符串,所以考虑两种情况:1.放左边的,不放边的:dp[i][j]=dp[i][j-1];2.放右边的,不放左边的:dp[i][j]=dp[i+1][j]。取二者最大值
初始化
由递推公式dp[i][j] = dp[i+1][j-1]+2可知,i和j不能相等。所以初始化时,i=j即一个字符串的回文长度为1.其余为0
遍历顺序
和回文子串同理
打印数组
根据dp数组的含义,返回dp[0][s.length()-1]
完整代码
class Solution {public int longestPalindromeSubseq(String s) {int[][] dp = new int[s.length()][s.length()];for (int i = 0; i < s.length(); i++) {dp[i][i] = 1;}for (int i = s.length()-1; i >= 0; i--) {for (int j = i+1; j < s.length(); j++) {if (s.charAt(i) == s.charAt(j)){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][s.length()-1];}
}
相关文章:
day57回文子串_最长回文子序列
力扣647.回文子串 题目链接:https://leetcode.cn/problems/palindromic-substrings/ 思路 dp数组含义 dp[i][j]:以s[i]为开头,s[j]为结尾的子串是否是回文子串 递推公式 子串范围为[i,j],当s[i]s[j]时,有三种情况࿱…...

Element UI框架学习篇(二)
Element UI框架学习篇(二) 1 整体布局 1.1 前提说明 el-container标签里面的标签默认是从左往右排列,若想要从上往下排列,只需要写el-header或者el-footer就行了 <el-container>:外层容器 <el-header>:顶栏容器。 <el-aside>&#…...

【C++】类与对象(上)
文章目录一、面向过程和面向对象初步认识二、类的引入三、类的定义四、类的访问限定符及封装①访问限定符②封装五、类的作用域六、类的实例化七、类对象模型①如何计算类对象大小②类对象的存储方式③结构体中内存对齐规则八、this指针①this指针的引出②this指针的特性一、面…...

Leetcode.1797 设计一个验证系统
题目链接 Leetcode.1797 设计一个验证系统 Rating : 1534 题目描述 你需要设计一个包含验证码的验证系统。每一次验证中,用户会收到一个新的验证码,这个验证码在 currentTime时刻之后 timeToLive秒过期。如果验证码被更新了,那么它会在 curr…...
Kaldi - 数据文件准备
文章目录数据文件准备wav.scputt2spkspk2utttext相关代码根据文件生成 utt2spk 和 wav.scputt2spk -- spk2utt 转换数据文件准备 在训练/解码中: 有三个文件是必要的: wav.scp 语音编号 – 路径信息utt2spk 语音编号 – 说话人编号spk2utt 说话人编号 …...

91.【SpringBoot-03】
SpringBoot-03(十四)、任务1.异步任务2.邮件任务(1).简单邮箱发送(2).复杂邮箱发送3.定时任务(1).cron表达式(2).特殊表达式(3).定时任务测试(4).常用cron表达式(十五)、Dubbo和Zookeeper集成1.分布式原理(1).Dubbo文档2.什么是RPC?3.Dubbo的概念和介绍(1).Dubbo是什么(2). Du…...

【本地项目】上传到【GitLab】流程详解
文章目录1、安装Git2、创建GitLab项目文件夹3、创建密钥4、向GitLab上传项目注意:本篇文章中提到的上传流程所需要的命令,几乎在GitLab的Command line instructions中都有所记载 1、安装Git 具体安装流程这里不做过多说明,安装流程可以参考…...
初阶指针C
🚀🚀🚀大家觉不错的话,就恳求大家点点关注,点点小爱心,指点指点🚀🚀🚀 目录 🐰指针是什么 🐰指针和指针类型 🌸指针-整数 &#x…...

云原生安全2.X 进化论系列|揭秘云原生安全2.X的五大特征
随着云计算技术的蓬勃发展,传统上云实践中的应用升级缓慢、架构臃肿、无法快速迭代等“痛点”日益明显。能够有效解决这些“痛点”的云原生技术正蓬勃发展,成为赋能业务创新的重要推动力,并已经应用到企业核心业务。然而,云原生技…...

json文件在faster_rcnn中从测试到训练 可行性
1.确认任务 经过mydataset文件处理后 - > 在train_res50_fpn文件内应用 # load train data set # VOCdevkit -> VOC2012 -> ImageSets -> Main -> train.txt train_dataset VOCDataSet(VOC_root, "2012", data_transform["train"], &…...
golang 1.20正式发布,更好更易更强
预期中的Go 2不会有了,1.20也算是一个小gap,从中可以一窥Go未来的发展之路。对于Go来说,未来保持1.x持续演进和兼容性之外,重点就是让Go性能更优,同时保持大道至简原则,使用尽可能容易,从这两个…...
图片显示一半怎么回事?
不知道小伙伴是否遇到过,刚刚上传的一个文件夹,有一多半的图片突然就变成了无法显示该图片或者是图片显示一半,而另外一半就显示灰色蓝色粉色条状。而且还把原文件删除了。面对这种情况,有什么解决方法呢?下面让我们一起来来看看…...

102-并发编程详解(中篇)
这里续写上一章博客 Phaser新特性 : 特性1:动态调整线程个数 CyclicBarrier 所要同步的线程个数是在构造方法中指定的,之后不能更改,而 Phaser 可以在运行期间动态地 调整要同步的线程个数,Phaser 提供了下面这些方…...

jsp羽毛球场馆管理系统Myeclipse开发mysql数据库web结构java编程计算机网页项目
一、源码特点 jsp 羽毛球场馆管理系统 是一套完善的web设计系统,对理解JSP java编程开发语言有帮助,系统具有完整的源代码和数据库,系统主要采用B/S模式开发。开发环境为 TOMCAT7.0,Myeclipse8.5开发,数据库为Mysql,…...

CacheLib 原理说明
CacheLib 介绍 CacheLib 是 facebook 开源的一个用于访问和管理缓存数据的 C 库。它是一个线程安全的 API,使开发人员能够构建和自定义可扩展的并发缓存。 主要功能: 实现了针对 DRAM 和 NVM 的混合缓存,可以将从 DRAM 驱逐的缓存数据持久…...

【dapr】服务调用(Service Invokation) - app id的解析
逻辑图解 上图来自Dapr官网教程,其中Checkout是一个服务,负责生成订单号, Order Processor是另一个服务,负责处理订单。Checkout服务需要调用Order Processor的API, 让Order Processor获取到其生成的订单号并进行处理。…...

Odoo丨5步轻松实现在Odoo中打开企微会话框
Odoo丨5步轻松实现在Odoo中打开企微会话框 在Odoo中开启企微会话框 企业微信作为一个很好的企业级应用发布平台,尤其是提供的数据和接口,极大地为很多企业级应用提供便利,在日常中应用广泛! 最近在项目中就遇到一个与企业微信相…...

python读取.stl文件
目录 .1 文本方式读取 1.2 stl解析 1.3 stl创建 .2 把点转换为.stl .1 文本方式读取 代码如下 stl_path/home/pxing/codes/point_improve/data/003_cracker_box/0.stlpoints[] f open(stl_path) lines f.readlines() prefixvertex num3 for line in lines:#print (l…...

vue2.0项目第一部分
论坛项目后端管理系统服务器地址:http://172.16.11.18:9090swagger地址:http://172.16.11.18:9090/doc.html前端h5地址:http://172.16.11.18:9099/h5/#/前端管理系统地址:http://172.16.11.18:9099/admin/#/搭建项目vue create . …...

锁与原子操作
锁与原子操作 锁 以自增操作为例子: void *func(void *arg) {int *pcount (int *)arg;int i 0;//while (i < 100000) {(*pcount) ; // 并不会到达100000usleep(1);} }int main(){int i 0;for (i 0;i < THREAD_COUNT;i ) {pthread_create(&thid…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以? 在 Golang 的面试中,map 类型的使用是一个常见的考点,其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练
前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1):从基础到实战的深度解析-CSDN博客,但实际面试中,企业更关注候选人对复杂场景的应对能力(如多设备并发扫描、低功耗与高发现率的平衡)和前沿技术的…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

深度学习水论文:mamba+图像增强
🧀当前视觉领域对高效长序列建模需求激增,对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模,以及动态计算优势,在图像质量提升和细节恢复方面有难以替代的作用。 🧀因此短时间内,就有不…...

aardio 自动识别验证码输入
技术尝试 上周在发学习日志时有网友提议“在网页上识别验证码”,于是尝试整合图像识别与网页自动化技术,完成了这套模拟登录流程。核心思路是:截图验证码→OCR识别→自动填充表单→提交并验证结果。 代码在这里 import soImage; import we…...
__VUE_PROD_HYDRATION_MISMATCH_DETAILS__ is not explicitly defined.
这个警告表明您在使用Vue的esm-bundler构建版本时,未明确定义编译时特性标志。以下是详细解释和解决方案: 问题原因: 该标志是Vue 3.4引入的编译时特性标志,用于控制生产环境下SSR水合不匹配错误的详细报告1使用esm-bundler…...