代码随想录算法训练营第五十七天| 647. 回文子串 516.最长回文子序列
代码随想录算法训练营第五十七天| 647. 回文子串 516.最长回文子序列
一、力扣647. 回文子串
题目链接
思路:对于字符串cabac,其中a,b,c,aba,cabac,都是回文子串,如果当前的字串是回文字串,那么它的字串中也会有回文字串,所以状态是有区间的,确定dp数组,dp[i][j]表示,区间[i,j]左闭右闭,表示该区间内的子串是否是回文子串。
当i=j时,一定是回文子串。
当s[i]=s[j],且i+1=j时,是回文子串,类似aa。
当s[i]=s[j],且i+2=j时,也就是类似于aba,i=0,j=2,只要中间的子串是回文子串,那么它也是,故只要dp[i+1][j-1]=true,即为回文子串。
遍历时要注意区间[i,j](i<j),且从下向上,从左向右。
class Solution {public int countSubstrings(String s) {int len = s.length(), result = 0;boolean[][] dp = new boolean[len][len];for (int i = len-1; i >= 0; i--) {for (int j = i; j < len; j++) {if (s.charAt(i) == s.charAt(j)) {if (j - i <= 1) {result++;dp[i][j] = true;}else if (dp[i+1][j-1]) {result++;dp[i][j] = true;}}}}return result;}
}
二、力扣 516.最长回文子序列
题目链接
思路:上面求回文子串数量,是连续的,这里求最长回文子串,是非连续的,依然是dp[i][j]区间[i,j]。
如果s[i]=s[j]那么,状态转移公式就出来了dp[i][j] = dp[i+1][j-1] + 2。
如果s[i]!=s[j]那么,就各取一个留最长的, dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])。
class Solution {public int longestPalindromeSubseq(String s) {int len = s.length();int[][] dp = new int[len][len];for (int i = 0; i < len; i++) {dp[i][i] = 1;}for (int i = len-1; i >= 0; i--) {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], dp[i][j-1]);}}}return dp[0][len-1];}
}
相关文章:
代码随想录算法训练营第五十七天| 647. 回文子串 516.最长回文子序列
代码随想录算法训练营第五十七天| 647. 回文子串 516.最长回文子序列 一、力扣647. 回文子串 题目链接 思路:对于字符串cabac,其中a,b,c,aba,cabac,都是回文子串,如果当前的字串是回文字串,那么它的字串中也会有回文…...
django 优化方式
前言 对于网站和Web APP来说,相同的类型的产品,响应速度越好,那么用户量就越高。不可否认的是,响应速度是用户黏粘性最好的方式之一,但往往不知道如何下手解决,希望这篇文章可以给予你一些思路 对于网站和…...
IDEA中怎么使用git下载项目到本地,通过URL克隆项目(giteegithub)
点击 新建>来自版本控制的项目 点击后会弹出这样一个窗口 通过URL拉取项目代码 打开你要下载的项目仓库 克隆>复制 gitee github也是一样的 返回IDEA 将刚刚复制的URL粘贴进去选择合适的位置点击克隆 下载完成...
09. Docker Compose
目录 1、前言 2、安装Docker Compose 2.1、Docker Compose版本 2.2、下载安装 3、初试Docker Compose 3.1、传统方案部署应用 3.2、使用编排部署应用 3.3、其他命令 3.3.1、ps 3.3.2、images 3.3.3、depends_on 3.3.4、scale 4、小结 1、前言 随着应用架构的不段…...
如何在shell脚本将node_modules里的文件复制一份到public文件里
项目背景:由于公司网络不连接公网,所以在绘制地图大屏项目时,需要我们将边界线数据包也部署起来,来获取边界线数据 解决方案: 1.让后端写个接口或者找个地方将数据包放到服务器即可 2.将数据包放到vue项目的public文…...
监控Redis的关键指标
Redis 也是一个对外服务,所以 Google 的四个黄金指标同样适用于 Redis。 1、延迟 在软件工程架构中,之所以选择 Redis 作为技术堆栈的一员,大概率是想要得到更快的响应速度和更高的吞吐量,所以延迟数据对使用 Redis 的应用程序至…...
Openlayers和leaflet如何选用?
在地图处理这块,Openlayers和Leaflet是非常有名的两个开源的JS框架,他们各有各的优势和劣势,对于刚刚步入此行业的开发者而言怎么选择框架呢? 作者做过一定的探索,在这里将成果分享给大家。 Openlayers 简介 Openlayers是一个基于Javacript开发,免费、开源的前端地图开…...
跟我学C++中级篇——三五法则
一、三五法则 三五法则,这个叫着有点上头,说实话,这个三五法则,未来会不会变成三六或者四七法则,没人知道,反正现在是三五法则。在《cPrimer》第四版中,叫三法则,在第五版第13.1.4章…...
aardio:用 WebView 模仿 mdict 界面
aardio:用 WebView 模仿 mdict 界面 import win.ui; /*DSG{{*/ mainForm win.form(text"aardio2";right889;bottom467) mainForm.add( button{cls"button";text"go";left335;top22;right399;bottom41;z2}; button2{cls"button…...
linq中的操作符
LINQ(Language Integrated Query)是一种用于.NET平台的查询语言,用于查询和操作各种数据源,如集合、数据库和XML。LINQ提供了一组标准查询操作符,用于执行各种查询操作。 LINQ(Language Integrated Query&…...
数据结构【哈夫曼树】
哈夫曼树 哈夫曼树的概念哈夫曼树的构造构造算法的实现哈夫曼树应用哈夫曼编码哈夫曼编码的算法实现 哈夫曼树的概念 最优二叉树也称哈夫曼 (Huffman) 树,是指对于一组带有确定权值的叶子结点,构造的具有最小带权路径长度的二叉树。权值是指一个与特定结…...
SpringMVC基于SpringBoot的最基础框架搭建——包含数据库连接
SpringMVC基于SpringBoot的最基础框架搭建——包含数据库连接 背景目标依赖配置文件如下项目结构如下相关配置如下启动代码如下Controller如下启动成功接口调用成功 背景 工作做了一段时间,回忆起之前有个公司有线下笔试,要求考生做一个什么功能&#x…...
deepspeed zero3
zero3。它是纵向切分权重(intra-layer,每一层的权重切成n块)。但是这样会增加通讯时间。你可以根据自己的模型,估算下切分后的通讯量和通讯时间。其次,pipeline并行一般指横向切分权重(inter-layer…...
代驾小程序怎么做
代驾小程序是一款专门为用户提供代驾服务的手机应用程序。它具有以下功能: 1. 预约代驾:代驾小程序允许用户在需要代驾服务时提前进行预约。用户可以选择出发地点、目的地以及预计用车时间,系统会自动匹配最合适的代驾司机,并确保…...
探索 AJAX 技术:实现动态数据交互的前端利器
简介: AJAX(Asynchronous JavaScript and XML)技术在 Web 前端开发中扮演着重要的角色,它通过异步通信和动态内容更新,为用户带来更好的交互体验。本篇笔记将详细探索 AJAX 技术,并通过生动的代码演示来展示…...
深度学习Redis(3):主从复制
前言 在前面的两篇文章中,分别介绍Redis内存模型和Redis持久化 在Redis的持久化中曾提到,Redis高可用的方案包括持久化、主从复制(及读写分离)、哨兵和集群。其中持久化侧重解决的是Redis数据的单机备份问题(从内存到…...
php笔记1
php环境 PHP作为一种服务器端脚本语言,可以在各种操作系统上运行。搭建PHP网站的环境,你需要以下几个要素: Web服务器:常见的选择有Apache、Nginx和IIS。你需要安装和配置其中一个服务器软件。PHP解释器:PHP是一种解…...
2023 ChinaJoy 圆满闭幕,FairGuard游戏加固亮相 BTOB 展区
提振行业 产业复苏 2023年7月28日至7月31日,第二十届中国国际数码互动娱乐展览会( ChinaJoy)于上海新国际博览中心圆满举办。本届ChinaJoy作为疫情结束后的第一个国际性数字娱乐领域的重要产业盛会,对于提振行业信心、加快产业复苏、增进国际间的交流与…...
数据规约策略
有很多概念平时一直在说,但是具体的应用场景却一直不明确,这会导致我们在实际应用过程中对应该使用的方法不够明确,在此对常用的几种数据挖掘方法使用场景进行分类和整合。 数据降维 为什么要降维 数据稀疏,维度高高维数据采用…...
服务器带宽独享跟共享有什么区别103.36.166.x
独享带宽 独享带宽针对对带宽有较高的要求,其业务的内容和性质决定只有使用独立的带宽资源才能满足品质的需求,而这种只给单独客户使用的带宽资源称为独享带宽. 使用独享带宽,整个带宽资源归属于一个客户 独享带宽的优点是可自由使用带宽量…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...
MFC内存泄露
1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...
跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
CMake控制VS2022项目文件分组
我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...
基于SpringBoot在线拍卖系统的设计和实现
摘 要 随着社会的发展,社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统,主要的模块包括管理员;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...
AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别
【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而,传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案,能够实现大范围覆盖并远程采集数据。尽管具备这些优势…...
