代码随想录算法训练营第五十七天| 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
独享带宽 独享带宽针对对带宽有较高的要求,其业务的内容和性质决定只有使用独立的带宽资源才能满足品质的需求,而这种只给单独客户使用的带宽资源称为独享带宽. 使用独享带宽,整个带宽资源归属于一个客户 独享带宽的优点是可自由使用带宽量…...
Unity Il2CppDumper原理与实战:解析元数据与二进制对齐
1. 这不是“破解工具”,而是Unity开发者该懂的二进制真相课 你刚在Unity Asset Store下载了一个功能惊艳的插件,却在打包iOS后发现部分逻辑失效;或者接手一个没有源码的旧项目,只有一堆 .dll 和 .so 文件,连主入口…...
如何用deberta-v3-base-zeroshot-v2.0构建企业级NLP应用?完整教程来了
如何用deberta-v3-base-zeroshot-v2.0构建企业级NLP应用?完整教程来了 【免费下载链接】deberta-v3-base-zeroshot-v2.0 项目地址: https://ai.gitcode.com/hf_mirrors/NingBo_Ascend/deberta-v3-base-zeroshot-v2.0 deberta-v3-base-zeroshot-v2.0是一款基…...
IPD的势、道、法、术、器
目录 简介 一、势:为什么 IPD 是必然选择? 二、道:IPD 的底层哲学 三、法与术:从战略到执行的具体路径 四、器:让流程真正落地的工具与组织 不是每家公司都需要全套 IPD,但每家公司都需要 IPD 思维 简…...
用数字逻辑门复刻柏林钟:从二进制编码到硬件实现
1. 项目概述:用数字电路复刻“柏林钟”作为一个在柏林长大的孩子,我从小就对库达姆大街上的那座“柏林钟”着迷。它不像传统时钟那样用指针或数字告诉你时间,而是通过几排不同颜色的发光方块,以一种近乎艺术的方式呈现时间。这种独…...
WPF虚拟桌宠组件:可嵌入、高性能、工程化UI生命体
1. 这不是“桌面宠物”,而是一个可嵌入的WPF UI组件化生命体你可能在Windows XP时代见过那只晃着尾巴、偶尔打哈欠的3D小猫,也可能在Win10系统托盘里点开过一个会眨眼的像素狐狸——但那些是独立进程、是系统级小工具、是“看一眼就关掉”的轻量娱乐。而…...
从“DOC/PDF”到“WPS”:细看GJB438C-2021文档格式要求背后的国产化信号与落地指南
从“DOC/PDF”到“WPS”:GJB438C-2021文档格式变革的深度解读与实施策略 当一份国家军用标准在文档格式描述中刻意删除"DOC/PDF"字样,转而明确标注"(WPS)文档处理器"时,这绝非简单的技术参数调整。…...
基于Jetson Nano与JNEEG Shield的脑电信号采集与边缘AI处理实战
1. 项目概述:低成本脑机接口的硬件基石 如果你对脑机接口、生物信号处理或者边缘AI应用感兴趣,但又苦于专业设备动辄数万甚至数十万的高昂门槛,那么JNEEG Shield的出现,可能会为你打开一扇新的大门。这是一个专为NVIDIA Jetson Na…...
智能烹饪助手:基于传感器融合与AI的厨房自动化实践
1. 项目概述:一个让厨房小白也能自信下厨的智能伙伴每次站在灶台前,你是不是也经历过这样的场景:一边手忙脚乱地翻着菜谱,一边担心锅里的菜是不是快糊了,还要分心去计算各种调料该放多少?对于很多刚接触烹饪…...
从Figma设计到Python GUI:Tkinter-Designer如何重塑可视化开发范式
从Figma设计到Python GUI:Tkinter-Designer如何重塑可视化开发范式 【免费下载链接】Tkinter-Designer An easy and fast way to create a Python GUI 🐍 项目地址: https://gitcode.com/gh_mirrors/tk/Tkinter-Designer 在Python GUI开发领域&am…...
监控摄像头小众场景爆发,融合类产品成新蓝海
随着户外运动热潮的持续和物联网技术的全面落地,打猎相机市场在2025年迎来了真正的爆发期,并在2026年继续向智能化、网联化深度演进。根据最新的行业监测数据,2025年全球消费类IPC(网络摄像机)出货量突破1.92亿台&…...
