算法训练营第六十天(延长12天添加图论) | LeetCode 647 回文子串、LeetCode 516 最长回文子序列
LeetCode 67 回文子串
思路很简单,每一个dp[i]等于dp[i-1]加上当前字符向前直到0各个长度字符串回文串个数即可
代码如下:
class Solution {public boolean isValid(String s) {int l = 0, r = s.length() - 1;while (l < r) {if (s.charAt(l) != s.charAt(r)) return false;l++; r--;}return true;}public int countSubstrings(String s) {int[] dp = new int[s.length()];dp[0] = 1;for (int i = 1; i < s.length(); i++) {dp[i] = dp[i-1];for (int j = i; j >= 0; j--) {String ss = s.substring(j, i+1);if (isValid(ss)) dp[i]++; }}return dp[s.length() - 1];}
}
LeetCode 516 最长回文子序列
这题要在上一题基础上稍微转换下思路。
原本是从前往后循环内从后往前统计回文字符串数目,这题是从中间往两边,看两边分别接触到的第一个字符是否相等。
如果相等就都放入,并且dp[i][j]等于dp[i+1][j-1]+2,否则dp[i][j]取dp[i+1][j]、dp[i][j-1]、dp[i][j]中最大值即可。这就是这道题的递推逻辑了。
初始化方式是在i==j时要初始化为1。或者将dp[i][i]初始化为1也行
从递归公式中,可以看出,dp[i][j] 依赖于 dp[i + 1][j - 1] ,dp[i + 1][j] 和 dp[i][j - 1],如图:

所以遍历i的时候一定要从下到上遍历,这样才能保证下一行的数据是经过计算的。
代码如下:
public class Solution {public int longestPalindromeSubseq(String s) {int len = s.length();int[][] dp = new int[len + 1][len + 1];for (int i = len - 1; i >= 0; i--) { // 从后往前遍历 保证情况不漏dp[i][i] = 1; // 初始化for (int j = i + 1; j < len; 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], Math.max(dp[i][j], dp[i][j - 1]));}}}return dp[0][len - 1];}
}
相关文章:
算法训练营第六十天(延长12天添加图论) | LeetCode 647 回文子串、LeetCode 516 最长回文子序列
LeetCode 67 回文子串 思路很简单,每一个dp[i]等于dp[i-1]加上当前字符向前直到0各个长度字符串回文串个数即可 代码如下: class Solution {public boolean isValid(String s) {int l 0, r s.length() - 1;while (l < r) {if (s.charAt(l) ! s.ch…...
TikTok账号养号的流程分享
对于很多刚开始运营TikTok的新手小白来说,都会有一个同样的疑问,那就是:TikTok到底需不需要养号?这里明确告诉大家是需要养号的,今天就把我自己实操过的养号经验和策略总结出来,分享给大家。 一、什么是Ti…...
C++初学者指南第一步---6.枚举和枚举类
C初学者指南第一步—6.枚举和枚举类 文章目录 C初学者指南第一步---6.枚举和枚举类1.作用域的枚举(enum class类型)(C11)2.无作用域的枚举(enum类型)3.枚举类的基础类型4.自定义枚举类映射5.和基础类型的互相转换 1.作用域的枚举(enum class类…...
【js判断机型】
var isIOS /(iPhone|iPad|iPod)/i.test(navigator.userAgent) var isiPad navigator.userAgent.match(/(iPad)/) || (navigator.platform ‘MacIntel’ && navigator.maxTouchPoints > 1) 上面这个不行的话,再试下这个 var isiPad (navigator.userAg…...
google chrome浏览器安装crx插件Jam
先上一张图: Jam是bug报告生成插件 1、在地址栏中输入chrome://extensions/,然后回车。 2、将下载好的crx插件,直接拖到里面就可以完成安装工作了。 3、测试了一下jam插件,发现直接没有响应。 4、点击【移除】直接可以删除插件…...
【Java面试】二十、JVM篇(上):JVM结构
文章目录 1、JVM2、程序计数器3、堆4、栈4.1 垃圾回收是否涉及栈内存4.2 栈内存分配越大越好吗4.3 方法内的局部变量是否线程安全吗4.4 栈内存溢出的情况4.5 堆和栈的区别是什么 5、方法区5.1 常量池5.2 运行时常量池 6、直接内存 1、JVM Java源码编译成class字节码后…...
【Python教程】压缩PDF文件大小
压缩 PDF 文件能有效减小文件大小并提高文件传输的效率,同时还能节省计算机存储空间。除了使用一些专业工具对PDF文件进行压缩,我们还可以通过 Python 来执行该操作,实现自动化、批量处理PDF文件。 本文将分享一个简单有效的使用 Python 压缩…...
UE4中性能优化和检测工具
UE4中性能优化和检测工具合集 简述CPUUnreal InsightUnreal ProfilerSimpleperfAndroid StudioPerfettoXCode TimeprofilerBest Practice GPUAdreno GPUMali GPUAndroid GPU Inspector (AGI) 内存堆内存分析Android StudioLoliProfilerUE5 Memory InsightsUnity Mono 内存Memre…...
大型ERP设计-业务与功能指引:外币折算与辅助账套
外币折算与辅助账套 前言:在对ORACLE和SAP的核心模块功能全面解读的基础上,给出大型ERP设计的建议-业务与功能指引,企业选型、开发大型ERP软件的公司和ERP顾问可以参考。模块包括财务、计划与制造、供应链、项目及设备(MRO),初步预…...
重学java 73.设计模式
本想送你一本沉思录,可该迷途知返的人是我 —— 24.6.18 设计模式 设计模式(Design pattern),是一套被反复使用、经过分类编目的、代码设计经验的总结,使用设计模式是为了可重用代码、保证代码可靠性、程序的重用性,稳定性。 1995 年&#x…...
线代的学习(矩阵)
1.矩阵的乘法 矩阵实现满足:内标相等 矩阵相乘之后的结果:前行后列 需要注意:1.矩阵的乘法不具有交换律:AB!BA 2.矩阵的乘法满足分配律:A(BC) AB AC 抽象逆矩阵求逆矩阵 方法1.凑定义法、 方法2.长除法 数字型矩阵…...
【Java基础5】JDK、JRE和JVM的区别与联系
JDK、JRE和JVM的区别与联系 Java是一种广泛使用的编程语言,它的跨平台特性得益于Java虚拟机(JVM)。然而,在Java的世界里,JDK、JRE和JVM这三个术语常常让人感到困惑。本文将阐述它们各自的功能,以及它们是如…...
2024年先进机械电子、电气工程与自动化国际学术会议(ICAMEEA 2024)
2024年先进机械电子、电气工程与自动化国际学术会议(ICAMEEA 2024) 2024 International Conference on Advanced Mechatronic, Electrical Engineering and Automation 会议地点:杭州,中国 网址:www.icameea.com 邮箱: icameeasub-conf.c…...
WPF 深入理解四、样式
样式 WPF中的各类控件元素,都可以自由的设置其样式。 诸如: 字体(FontFamily) 字体大小(FontSize) 背景颜色(Background) 字体颜色(Foreground) 边距(Margin) 水平位置(HorizontalAlignment) 垂直位置(VerticalAlignment)等等。 而样式则是组织和重用以上的重要工具。不是使…...
TCP相关细节
1. 常用TCP参数 1.1 ReceiveBufferSize ReceiveBuffersize指定了操作系统读缓冲区的大小, 默认值是8192(如图5-10 所示)。在第4章的例子中,会有"假设操作系统缓冲区的长度是8" 这样的描述,可通过socket.ReceiveBufferSize 8 实现。当接收端缓冲区满了的时…...
flutter实现UDP发送魔法包唤醒主机
魔法包 魔法包是用16进制表示的数据包,它是由固定的前缀数据(FFFFFFFFFFFF)以及固定重复次数(16次)的目标主机MAC地址组成。 假设目标主机的MAC地址是:"50:eb:f6:27:ae:a8" 那么魔法包就是[FFFFFFFFFFFF50EBF627AEA850EBF627AEA850EBF627AEA8…...
回溯算法练习题(2024/6/18)
1全排列 II 给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。 示例 1: 输入:nums [1,1,2] 输出: [[1,1,2],[1,2,1],[2,1,1]]示例 2: 输入:nums [1,2,3] 输出:[[1,…...
DSP——从入门到放弃系列2——PLL锁相环(持续更新)
1、概述 锁相环(Phase Locked Loop,PLL)是处理器的时钟源,控制着C6678处理器中C66x内核、各外围设备的时钟的时钟比、对准和选通功能。 2、功能描述 上图显示了PLL和PLL控制器的逻辑实现。PLL控制器提供通过软件可配置的分频器࿰…...
Altair 人工智能技术助力MABE预测消费者行为,实现设备性能优化
主要看点 行业: 家电行业 挑战: 企业面临的挑战是如何利用已收集的大量数据,深入了解消费者在产品使用过程中对某些保鲜程序的影响。 Altair 解决方案: Altair采用了Altair RapidMiner人工智能平台来解决问题,特别是…...
解决Spring Boot项目中数据源URL属性的问题
今天测试Springboot项目的时候,报错: . ____ _ __ _ _/\\ / ____ __ _ _(_)_ __ __ _ \ \ \ \ ( ( )\___ | _ | _| | _ \/ _ | \ \ \ \\\/ ___)| |_)| | | | | || (_| | ) ) ) ) |____| .__|_| |_|_| |_\__, | / / / /|_||___…...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...
python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
MySQL 知识小结(一)
一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库,分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷,但是文件存放起来数据比较冗余,用二进制能够更好管理咱们M…...
RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)
RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发,后来由Pivotal Software Inc.(现为VMware子公司)接管。RabbitMQ 是一个开源的消息代理和队列服务器,用 Erlang 语言编写。广泛应用于各种分布…...
【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看
文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...
第7篇:中间件全链路监控与 SQL 性能分析实践
7.1 章节导读 在构建数据库中间件的过程中,可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中,必须做到: 🔍 追踪每一条 SQL 的生命周期(从入口到数据库执行)&#…...
【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅
目录 前言 操作系统与驱动程序 是什么,为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中,我们在使用电子设备时,我们所输入执行的每一条指令最终大多都会作用到硬件上,比如下载一款软件最终会下载到硬盘上&am…...
