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

day51【代码随想录】动态规划之回文子串、最长回文子序列

文章目录

  • 前言
  • 一、回文子串(力扣647)
  • 二、最长回文子序列(力扣516)


前言

1、回文子串
2、最长回文子序列


一、回文子串(力扣647)

给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串
在这里插入图片描述
分析:
1、确定dp[]数组以及下标含义
在这里插入图片描述

布尔类型的dp[i][j]:表示区间范围[i,j] (注意是左闭右闭)的子串是否是回文子串,如果是dp[i][j]为true,否则为false。

2、递推公式
分析两种情况:
s[i]与s[j]相等,s[i]与s[j]不相等两种
当s[i]与s[j]不相等,那没啥好说的了,dp[i][j]一定是false。
当s[i]与s[j]相等时:

情况一:下标i 与 j相同,同一个字符例如a,当然是回文子串
情况二:i和j仅相差1,“aa” 这样子
情况三:i-j>1 “abccba” 或者 “abca”,此时我们需要判断i-1 和 j+1是不是回文子串,

3、初始化
都初始为false
4、遍历顺序
从下到上

class Solution {public int countSubstrings(String s) {int res = 0;char[] ss = s.toCharArray();if (s == null || (s.length() < 1)) return 0;boolean[][] dp = new boolean[ss.length][ss.length];for(int i=s.length()-1;i>=0;i--){for(int j=i;j<s.length();j++){if(ss[i]==ss[j]){if(Math.abs(i-j)<=1){dp[i][j] = true;res++;}else if(dp[i+1][j-1]==true){dp[i][j] = true;res++;}}else{dp[i][j] = false;}}}return res;}
}

在这里插入图片描述

二、最长回文子序列(力扣516)

给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。

子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。

在这里插入图片描述
分析:

回文子串是要连续的,回文子序列可不是连续的!
思路其实是差不多的,但本题要比求回文子串简单一点,因为情况少了一点。
1、确定dp数组以及下标含义
dp[i][j]:表示区间范围[i,j] (注意是左闭右闭)的子串,回文子串的长度最大为dp[i][j]

2、递推公式
分析两种情况:
如果s[i]与s[j]不相同,说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子序列的长度,那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。

加入s[j]的回文子序列长度为dp[i + 1][j]。
加入s[i]的回文子序列长度为dp[i][j - 1]。

那么dp[i][j]一定是取最大的,即:dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

当s[i]与s[j]相等时
dp[i][j] = dp[i+1][j-1] +2;

3、初始化
在对角线上的情况dp[i][j]应该是初始为1的。即:一个字符的回文子序列长度就是1。
其他情况dp[i][j]初始为0就行
4、遍历顺序
从下到上

class Solution {public int longestPalindromeSubseq(String s) {int[][] dp = new int[s.length()][s.length()];if(s==null || s.length()==0) return 0;//初始化for(int i=0;i<s.length();i++){dp[i][i] = 1;}//遍历顺序for(int i=s.length()-2;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][j-1],dp[i+1][j]);}}}return dp[0][s.length()-1];}
}

在这里插入图片描述


相关文章:

day51【代码随想录】动态规划之回文子串、最长回文子序列

文章目录前言一、回文子串&#xff08;力扣647&#xff09;二、最长回文子序列&#xff08;力扣516&#xff09;前言 1、回文子串 2、最长回文子序列 一、回文子串&#xff08;力扣647&#xff09; 给你一个字符串 s &#xff0c;请你统计并返回这个字符串中 回文子串 的数目…...

拟凸函数,拟凹函数,单峰函数

拟凸&#xff08;quasi-convex&#xff09;函数很早就听说过&#xff0c;但是标准定义一直不太了解&#xff0c;现在总结一下。 一个定义在凸集上的实数函数 fff 是拟凸函数&#xff1a;若对于其定义域内的任意两个点 xxx 和 yyy&#xff0c;以及任意常数 λ∈[0,1]\lambda\in…...

数据处理(伪)代码:卡尔曼滤波 vs. 卡尔曼平滑

步骤一、导入csv或txt格式的试验数据 最简洁也是据说读取速度最快的方法是&#xff1a; pPath C:\data_org\9#-1.txt % 数据文件 data importdata(pPath); % 读取 pPath 的结果到 一个数据结构变量 data 中。 pData data.data; % 提取有效数据数组data 的数据结构如下&a…...

华为OD机试题,用 Java 解【比赛评分】问题

最近更新的博客 华为OD机试 - 猴子爬山 | 机试题算法思路 【2023】华为OD机试 - 分糖果(Java) | 机试题算法思路 【2023】华为OD机试 - 非严格递增连续数字序列 | 机试题算法思路 【2023】华为OD机试 - 消消乐游戏(Java) | 机试题算法思路 【2023】华为OD机试 - 组成最大数…...

【基础算法】哈希表(开放寻址法)

&#x1f339;作者:云小逸 &#x1f4dd;个人主页:云小逸的主页 &#x1f4dd;Github:云小逸的Github &#x1f91f;motto:要敢于一个人默默的面对自己&#xff0c;强大自己才是核心。不要等到什么都没有了&#xff0c;才下定决心去做。种一颗树&#xff0c;最好的时间是十年前…...

优化算法(寻优问题)

前言 群智能算法&#xff08;全局最优&#xff09;&#xff1a;模拟退火算法&#xff08;Simulated annealing&#xff0c;SA&#xff09;&#xff0c;遗传算法&#xff08;Genetic Algorithm, GA&#xff09;&#xff0c;粒子群算法&#xff08;Particle Swarm Optimization&…...

基于视频流⽔线的Opencv缺陷检测项⽬

代码链接见文末 1.数据与任务概述 输入为视频数据,我们需要从视频中检测出缺陷,并对缺陷进行分类。 2.整体流程 (1)视频数据读取和轮廓检测 首先,我们需要使用opencv读取视频数据,将彩色图转为灰度图后进行图像阈值处理。阈值处理是为了让前景和背景更明显的区分处理。…...

百万数据excel导出功能如何实现?

最近我做过一个MySQL百万级别数据的excel导出功能&#xff0c;已经正常上线使用了。 这个功能挺有意思的&#xff0c;里面需要注意的细节还真不少&#xff0c;现在拿出来跟大家分享一下&#xff0c;希望对你会有所帮助。 原始需求&#xff1a;用户在UI界面上点击全部导出按钮…...

华为OD机试题,用 Java 解【合规数组】问题

最近更新的博客 华为OD机试 - 猴子爬山 | 机试题算法思路 【2023】华为OD机试 - 分糖果(Java) | 机试题算法思路 【2023】华为OD机试 - 非严格递增连续数字序列 | 机试题算法思路 【2023】华为OD机试 - 消消乐游戏(Java) | 机试题算法思路 【2023】华为OD机试 - 组成最大数…...

SAP ABAP中的数据类型 Data Types

简单来说分两种&#xff1a; 数据字典里定义的在ABAP程序里定义的 文章目录1. ABAP数据字典里的1.1 数字型的1.2 字符型1.3 字节型1.4 特殊类型2. 预定义的ABAP数据类型2.1 预定义数字型2.2 预定义字符型2.3 预定义字节型1. ABAP数据字典里的 1.1 数字型的 用在数学计算里的…...

HashMap~

HashMap&#xff1a; HashMap是面试中经常被问到的一个内容&#xff0c;以下两个经常被问到的问题&#xff0c; Question1&#xff1a;底层数据结构&#xff0c;1.7和1.8有何不同&#xff1f; 答&#xff1a;1.7数组&#xff0b;链表&#xff0c;1.8数组&#xff0b;(链表|红…...

EasyNLP集成K-Global Pointer算法,支持中文信息抽取

作者&#xff1a;周纪咏、汪诚愚、严俊冰、黄俊 导读 信息抽取的三大任务是命名实体识别、关系抽取、事件抽取。命名实体识别是指识别文本中具有特定意义的实体&#xff0c;包括人名、地名、机构名、专有名词等&#xff1b;关系抽取是指识别文本中实体之间的关系&#xff1b;…...

mysql lesson3

DQL查找语句续集.............................. 分组函数&#xff08;也叫多行处理函数&#xff09; 1&#xff1a; select sum(sal) from emp;select min(sal)from emp;select max(sal)from emp;select avg(sal)from emp;select count(ename)from emp;2&#xff1a;分组函…...

python源码保护

文章目录代码混淆打包exe编译为字节码源码加密项目发布部署时&#xff0c;为防止python源码泄漏&#xff0c;可以通过几种方式进行处理代码混淆 修改函数、变量名 打包exe 通过pyinstaller 将项目打包为exe可执行程序&#xff0c;不过容易被反编译。 编译为字节码 py_comp…...

第51讲:SQL优化之COUNT查询的优化

文章目录 1.COUNT查询优化的概念2.COUNT函数的用法1.COUNT查询优化的概念 在很多的业务场景下可能需要统计一张表中的总数据量,当表的数据量很大时,使用COUNT统计表数据量时,也是非常耗时的。 MyISAM引擎会把一个表的总行记录在磁盘中,当执行count(*)的时候会直接从磁盘中…...

ArrayBlockingQueue

同步队列超出长度时&#xff0c;不同的返回形式可以分为以下四种。 会抛异常不会抛异常&#xff0c;有返回值死等&#xff0c;直到可以插入值或者取到值设置等待超时时间添加方法add()offfer()put()offer(E e,long timeout, TimeUnit unit)删除方法remove()poll()take()poll(l…...

DeepLabV3+:对预测处理的详解

相信大家对于这一部分才是最感兴趣的&#xff0c;能够实实在在的看到效果。这里我们就只需要两个.py文件&#xff08;deeplab.py、predict_img.py&#xff09;。 创建DeeplabV3类 deeplab.py的作用是为了创建一个DeeplabV3类&#xff0c;提供一个检测图片的方法&#xff0c;而…...

【Git】与“三年经验”就差个分支操作的距离

前言 Java之父于胜军说过&#xff0c;曾经一位“三年开发经验”的程序员粉丝朋友&#xff0c;刚入职因为不会解决分支问题而被开除&#xff0c;这是不是在警示我们什么呢&#xff1f; 针对一些Git的不常用操作&#xff0c;我们通过例子来演示一遍 1.版本回退 1.1已提交但未p…...

【经验】win10设置自启动

方法一&#xff1a;自启动文件夹 按下winr快捷键&#xff0c;弹出运行窗口&#xff0c;输入&#xff1a;shell:startup&#xff0c;弹出自启动文件夹窗口&#xff0c;将要开机自启的程序或快捷方式复制到此窗口中即可。 自启动文件夹路径&#xff1a;C:\Users\【用户名】\Ap…...

Linux SPI-NAND 驱动开发指南

文章目录Linux SPI-NAND 驱动开发指南1 概述1.1 编写目的1.2 适用范围1.3 相关人员3 流程设计3.1 体系结构3.2 源码结构3.3 关键数据定义3.3.1 flash 设备信息数据结构3.3.2 flash chip 数据结构3.3.3 aw_spinand_chip_request3.3.4 ubi_ec_hdr3.3.5 ubi_vid_hdr3.4 关键接口说…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...

Kafka入门-生产者

生产者 生产者发送流程&#xff1a; 延迟时间为0ms时&#xff0c;也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于&#xff1a;异步发送不需要等待结果&#xff0c;同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...

给网站添加live2d看板娘

给网站添加live2d看板娘 参考文献&#xff1a; stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下&#xff0c;文章也主…...

Elastic 获得 AWS 教育 ISV 合作伙伴资质,进一步增强教育解决方案产品组合

作者&#xff1a;来自 Elastic Udayasimha Theepireddy (Uday), Brian Bergholm, Marianna Jonsdottir 通过搜索 AI 和云创新推动教育领域的数字化转型。 我们非常高兴地宣布&#xff0c;Elastic 已获得 AWS 教育 ISV 合作伙伴资质。这一重要认证表明&#xff0c;Elastic 作为 …...