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

算法训练营第六十天(延长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 回文子串 思路很简单&#xff0c;每一个dp[i]等于dp[i-1]加上当前字符向前直到0各个长度字符串回文串个数即可 代码如下&#xff1a; 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的新手小白来说&#xff0c;都会有一个同样的疑问&#xff0c;那就是&#xff1a;TikTok到底需不需要养号&#xff1f;这里明确告诉大家是需要养号的&#xff0c;今天就把我自己实操过的养号经验和策略总结出来&#xff0c;分享给大家。 一、什么是Ti…...

C++初学者指南第一步---6.枚举和枚举类

C初学者指南第一步—6.枚举和枚举类 文章目录 C初学者指南第一步---6.枚举和枚举类1.作用域的枚举(enum class类型&#xff09;&#xff08;C11&#xff09;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) 上面这个不行的话&#xff0c;再试下这个 var isiPad (navigator.userAg…...

google chrome浏览器安装crx插件Jam

先上一张图&#xff1a; Jam是bug报告生成插件 1、在地址栏中输入chrome://extensions/&#xff0c;然后回车。 2、将下载好的crx插件&#xff0c;直接拖到里面就可以完成安装工作了。 3、测试了一下jam插件&#xff0c;发现直接没有响应。 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字节码后&#xf…...

【Python教程】压缩PDF文件大小

压缩 PDF 文件能有效减小文件大小并提高文件传输的效率&#xff0c;同时还能节省计算机存储空间。除了使用一些专业工具对PDF文件进行压缩&#xff0c;我们还可以通过 Python 来执行该操作&#xff0c;实现自动化、批量处理PDF文件。 本文将分享一个简单有效的使用 Python 压缩…...

UE4中性能优化和检测工具

UE4中性能优化和检测工具合集 简述CPUUnreal InsightUnreal ProfilerSimpleperfAndroid StudioPerfettoXCode TimeprofilerBest Practice GPUAdreno GPUMali GPUAndroid GPU Inspector (AGI) 内存堆内存分析Android StudioLoliProfilerUE5 Memory InsightsUnity Mono 内存Memre…...

大型ERP设计-业务与功能指引:外币折算与辅助账套

外币折算与辅助账套 前言&#xff1a;在对ORACLE和SAP的核心模块功能全面解读的基础上&#xff0c;给出大型ERP设计的建议-业务与功能指引&#xff0c;企业选型、开发大型ERP软件的公司和ERP顾问可以参考。模块包括财务、计划与制造、供应链、项目及设备(MRO)&#xff0c;初步预…...

重学java 73.设计模式

本想送你一本沉思录&#xff0c;可该迷途知返的人是我 —— 24.6.18 设计模式 设计模式(Design pattern)&#xff0c;是一套被反复使用、经过分类编目的、代码设计经验的总结&#xff0c;使用设计模式是为了可重用代码、保证代码可靠性、程序的重用性,稳定性。 1995 年&#x…...

线代的学习(矩阵)

1.矩阵的乘法 矩阵实现满足&#xff1a;内标相等 矩阵相乘之后的结果&#xff1a;前行后列 需要注意&#xff1a;1.矩阵的乘法不具有交换律&#xff1a;AB!BA 2.矩阵的乘法满足分配律&#xff1a;A(BC) AB AC 抽象逆矩阵求逆矩阵 方法1.凑定义法、 方法2.长除法 数字型矩阵…...

【Java基础5】JDK、JRE和JVM的区别与联系

JDK、JRE和JVM的区别与联系 Java是一种广泛使用的编程语言&#xff0c;它的跨平台特性得益于Java虚拟机&#xff08;JVM&#xff09;。然而&#xff0c;在Java的世界里&#xff0c;JDK、JRE和JVM这三个术语常常让人感到困惑。本文将阐述它们各自的功能&#xff0c;以及它们是如…...

2024年先进机械电子、电气工程与自动化国际学术会议(ICAMEEA 2024)

2024年先进机械电子、电气工程与自动化国际学术会议(ICAMEEA 2024) 2024 International Conference on Advanced Mechatronic, Electrical Engineering and Automation 会议地点&#xff1a;杭州&#xff0c;中国 网址&#xff1a;www.icameea.com 邮箱: icameeasub-conf.c…...

WPF 深入理解四、样式

样式 WPF中的各类控件元素,都可以自由的设置其样式。 诸如: 字体(FontFamily) 字体大小(FontSize) 背景颜色(Background) 字体颜色(Foreground) 边距(Margin) 水平位置(HorizontalAlignment) 垂直位置(VerticalAlignment)等等。 而样式则是组织和重用以上的重要工具。不是使…...

TCP相关细节

1. 常用TCP参数 1.1 ReceiveBufferSize ReceiveBuffersize指定了操作系统读缓冲区的大小&#xff0c; 默认值是8192(如图5-10 所示)。在第4章的例子中,会有"假设操作系统缓冲区的长度是8" 这样的描述,可通过socket.ReceiveBufferSize 8 实现。当接收端缓冲区满了的时…...

flutter实现UDP发送魔法包唤醒主机

魔法包 魔法包是用16进制表示的数据包&#xff0c;它是由固定的前缀数据(FFFFFFFFFFFF)以及固定重复次数(16次)的目标主机MAC地址组成。 假设目标主机的MAC地址是&#xff1a;"50:eb:f6:27:ae:a8" 那么魔法包就是[FFFFFFFFFFFF50EBF627AEA850EBF627AEA850EBF627AEA8…...

回溯算法练习题(2024/6/18)

1全排列 II 给定一个可包含重复数字的序列 nums &#xff0c;按任意顺序 返回所有不重复的全排列。 示例 1&#xff1a; 输入&#xff1a;nums [1,1,2] 输出&#xff1a; [[1,1,2],[1,2,1],[2,1,1]]示例 2&#xff1a; 输入&#xff1a;nums [1,2,3] 输出&#xff1a;[[1,…...

DSP——从入门到放弃系列2——PLL锁相环(持续更新)

1、概述 锁相环&#xff08;Phase Locked Loop,PLL&#xff09;是处理器的时钟源&#xff0c;控制着C6678处理器中C66x内核、各外围设备的时钟的时钟比、对准和选通功能。 2、功能描述 上图显示了PLL和PLL控制器的逻辑实现。PLL控制器提供通过软件可配置的分频器&#xff0…...

Altair 人工智能技术助力MABE预测消费者行为,实现设备性能优化

主要看点 行业&#xff1a; 家电行业 挑战&#xff1a; 企业面临的挑战是如何利用已收集的大量数据&#xff0c;深入了解消费者在产品使用过程中对某些保鲜程序的影响。 Altair 解决方案&#xff1a; Altair采用了Altair RapidMiner人工智能平台来解决问题&#xff0c;特别是…...

解决Spring Boot项目中数据源URL属性的问题

今天测试Springboot项目的时候&#xff0c;报错&#xff1a; . ____ _ __ _ _/\\ / ____ __ _ _(_)_ __ __ _ \ \ \ \ ( ( )\___ | _ | _| | _ \/ _ | \ \ \ \\\/ ___)| |_)| | | | | || (_| | ) ) ) ) |____| .__|_| |_|_| |_\__, | / / / /|_||___…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.

ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #&#xff1a…...

二维FDTD算法仿真

二维FDTD算法仿真&#xff0c;并带完全匹配层&#xff0c;输入波形为高斯波、平面波 FDTD_二维/FDTD.zip , 6075 FDTD_二维/FDTD_31.m , 1029 FDTD_二维/FDTD_32.m , 2806 FDTD_二维/FDTD_33.m , 3782 FDTD_二维/FDTD_34.m , 4182 FDTD_二维/FDTD_35.m , 4793...

STM32标准库-ADC数模转换器

文章目录 一、ADC1.1简介1. 2逐次逼近型ADC1.3ADC框图1.4ADC基本结构1.4.1 信号 “上车点”&#xff1a;输入模块&#xff08;GPIO、温度、V_REFINT&#xff09;1.4.2 信号 “调度站”&#xff1a;多路开关1.4.3 信号 “加工厂”&#xff1a;ADC 转换器&#xff08;规则组 注入…...