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

代码随想录训练营第五十七天|647. 回文子串、516.最长回文子序列

 647. 回文子串

题目链接/文章讲解/视频讲解:代码随想录

1.代码展示

//647.回文子串
int countSubstrings(string s) {//step1 构建dp数组,明确dp数组的含义,dp[i][j]的含义是在下标为i和j区间内的字串是否为回文串vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));//step2 构建状态转移方程//当s[i] != s[j]时,此时必定不为回文子串//当s[i] == s[j]时,有三种情况//情况一:i = j,此时就是本身,因此必定为回文子串//情况二:i + 1 = j,此时就如aa的形式,因此也是回文子串//情况三:j > i + 1,此时当dp[i + 1][j - 1]为回文字串时,dp[i][j]才是回文子串//step3 初始化dp数组,都为false//step4 开始遍历int nResult = 0;for (int i = s.size() - 1; i >= 0; i++) {for (int j = i; j < s.size(); j++) {if (s[i] == s[j]) {if (j - i <= 1) {nResult++;dp[i][j] = true;}else if (dp[i + 1][j - 1]){nResult++;dp[i][j] = true;}}}}return nResult;
}

 2.本题小节

        思考:本题的重点在于对于dp[i][j]的理解,dp[i][j]的含义是在下标为i和j区间内的字串是否为回文串。构建状态转移方程,当s[i] != s[j]时,此时必定不为回文子串;当s[i] == s[j]时,有三种情况
 ,情况一,i = j,此时就是本身,因此必定为回文子串, 情况二,i + 1 = j,此时就如aa的形式,因此也是回文子串,情况三:j > i + 1,此时当dp[i + 1][j - 1]为回文字串时,dp[i][j]才是回文子串;初始化都为false,最后注意遍历顺序,先下后上,先左后右。

        基本思路:注意理解dp[i][j]的含义,按照代码的思路来即可。

516.最长回文子序列

题目链接/文章讲解/视频讲解:代码随想录

1.代码展示

//516.最长回文子序列
int longestPalindromeSubseq(string s) {//step1 构建dp数组,dp[i][j]的含义是在[i,j]下标的范围内s的最长回文子序列vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));//step2 状态转移方程//当s[i] == s[j],dp[i][j] = dp[i + 1][j - 1] + 2,//不等时,有两种情况,说明同时加入s[i],s[j]不能满足情况,分别加入s[i]和s[j]试试//则dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])//step3 初始化for (int i = 0; i < s.size(); i++) {dp[i][i] = 1;}//step4 开始遍历for (int i = s.size() - 1; i >= 0; i++) {for (int j = i + 1; j < s.size(); j++) {if (s[i] == s[j]) {dp[i][j] = dp[i + 1][j - 1] + 2;}else {dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);}}}return dp[0][s.size() - 1];
}

 2.本题小节

        思考:明确dp数组的含义。dp[i][j]的含义是在[i,j]下标的范围内s的最长回文子序列。状态转移方程,当s[i] == s[j],dp[i][j] = dp[i + 1][j - 1] + 2,不等时,有两种情况,说明同时加入s[i],s[j]不能满足情况,分别加入s[i]和s[j]试试,则dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]),初始化时对角线都为1,根据dp数组可以得。遍历时先下后上,先左后右。

        基本思路:注意dp数组的含义,按照动态规划步骤来。

动态规划总结:代码随想录

相关文章:

代码随想录训练营第五十七天|647. 回文子串、516.最长回文子序列

647. 回文子串 题目链接/文章讲解/视频讲解&#xff1a;代码随想录 1.代码展示 //647.回文子串 int countSubstrings(string s) {//step1 构建dp数组&#xff0c;明确dp数组的含义&#xff0c;dp[i][j]的含义是在下标为i和j区间内的字串是否为回文串vector<vector<bool&…...

对线程池设置做压测

线程池代码 Configuration public class ThreadPoolConfig {// 核心线程池大小private int corePoolSize 24;// 最大可创建的线程数private int maxPoolSize 25;// 队列最大长度private int queueCapacity 100;// 线程池维护线程所允许的空闲时间private int keepAliveSeco…...

【网络通信 -- WebRTC】项目实战记录 -- mediasoup android 适配 webrtc m94

【网络通信 -- WebRTC】项目实战记录 -- mediasoup android 适配 webrtc m94 【1】下载并配置 depot_tools 下载 depot_tools git clone https://chromium.googlesource.com/chromium/tools/depot_tools.git编辑 ~/.bashrc 将 depot_tools 添加到路径中 vim ~/.bashrc export…...

【力扣周赛】第 357 场周赛(⭐反悔贪心)

文章目录 竞赛链接Q1&#xff1a;6925. 故障键盘解法1——直接模拟解法2——双端队列 Q2&#xff1a;6953. 判断是否能拆分数组&#xff08;贪心&#xff09;Q3&#xff1a;2812. 找出最安全路径⭐解法1——多源BFS瓶颈路模型&#xff1f;解法2——多源BFS 倒序枚举答案 并查…...

css重置

css 重置 CSS 重置的主要目标是确保浏览器之间的一致性&#xff0c;并撤消所有默认样式&#xff0c;创建一个空白板。 如今&#xff0c;主流浏览器都实现了css规范&#xff0c;在布局或间距方面没有太大差异。但是通过自定义 CSS 重置&#xff0c;也可以改善用户体验和提高开…...

tcpdump相关

Linux内核角度分析tcpdump原理&#xff08;一&#xff09;Linux内核角度分析tcpdump原理&#xff08;二&#xff09;...

MFC新建内部消息

提示&#xff1a;记录一下MFC新建内部消息的成功过程 文章目录 前言一、pandas是什么&#xff1f;二、使用步骤 1.引入库2.读入数据总结 前言 先说一下基本情况&#xff0c;因为要在mapview上增加一个显示加载时间的功能。然后发现是要等加载完再显示时间&#xff0c;显示在主…...

linux查找目录

要在Linux中查找目录&#xff0c;可以使用find命令。下面是查询目录的几个示例&#xff1a; 1,查找当前目录下所有子目录&#xff1a; find . -type d 2,在指定路径下查找目录&#xff1a; find /path/to/directory -type d 3,查找以特定名称开头的目录&#xff1a; find . -t…...

机器学习:可解释学习

文章目录 可解释学习为什么需要可解释机器学习可解释还是强模型可解释学习的目标可解释机器学习Local ExplanationGlobal Explanation 可解释学习 神马汉斯&#xff0c;只有在有人看的时候能够答对。 为什么需要可解释机器学习 贷款&#xff0c;医疗需要给出理由&#xff0c;让…...

UE5- c++ websocket里实现调用player里的方法

# UGameInstance里直接调用 获取到引用了&#xff0c;就可以自然的调用。忽略 # UGameInstance里间接调用&#xff0c;通过代理调用 前置已经添加了websocket,具体步骤参考&#xff0c;链接在UWebSocketGameInstance.h里新增代理&#xff0c;并在链接成功后进行绑定。 #pragma…...

线性代数的学习和整理18:什么是维度,什么是秩?秩的各种定理秩的计算 (计算部分未完成)

目录 0 问题引出&#xff1a;什么是秩&#xff1f; 概念备注&#xff1a; 1 先厘清&#xff1a;什么是维数&#xff1f; 1.1 真实世界的维度数 1.2 向量空间的维数 1.2.1 向量空间&#xff0c;就是一组最大线性无关的向量组/基张成的空间 1.3 向量α的维数 1.3.1 向量的…...

Centos 6.5 升级到Centos7指导手册

一、背景 某业务系统因建设较早&#xff0c;使用的OS比较过时&#xff0c;还是centos6.5的系统&#xff0c;因国产化需要&#xff0c;需将该系统升级到BClinux 8.6&#xff0c;但官方显示不支持centos 6.x升级到8&#xff0c;需先将centos6.5升级到centos7的最新版&#xff0c…...

详解python中的映射类型---字典

概述 映射类型是“键-值”数据项的组合&#xff0c;每个元素是一个键值对&#xff0c;即元素是&#xff08;key&#xff0c;value&#xff09;&#xff0c;元素之间是无序的。键值对&#xff08;key&#xff0c;value&#xff09;是一种二元关系&#xff0c;源于属性和值的映射…...

gdal求矢量图形的形心

gdal求矢量图形的形心 #include "gdal_priv.h" #include "ogrsf_frmts.h"int main() {OGRRegisterAll();OGRPolygon* square_1 new OGRPolygon();OGRLinearRing* ring_1 new OGRLinearRing();// 添加 square_1 的点ring_1->addPoint(0, 0);ring_1-&g…...

<深度学习基础> Batch Normalization

Batch Normalization批归一化 BN优点 减少了人为选择参数。在某些情况下可以取消dropout和L2正则项参数&#xff0c;或者采取更小的L2正则项约束参数&#xff1b;减少了对学习率的要求。现在我们可以使用初始很大的学习率或者选择了较小的学习率&#xff0c;算法也能够快速训…...

Ubuntu yolov5 环境配置

查看Ubuntu版本 $ cat /proc/version Linux version 5.4.0-150-generic (builddbos03-amd64-012) (gcc version 7.5.0 (Ubuntu 7.5.0-3ubuntu1~18.04)) #167~18.04.1-Ubuntu SMP Wed May 24 00:51:42 UTC 2023虚拟机磁盘扩容 因为在环境搭建过程中遇到了磁盘空间不足的问题&a…...

【自执行闭包JS逆向】某网站登录MD5加密分析

文章目录 一、写在前面二、抓包分析三、加密函数分析 一、写在前面 最近工作比较忙&#xff0c;不过还是在督促自己利用有限的时间学习更新一些技术文章。互联网这个行业大家目前也都知道是非常内卷的&#xff0c;所有大家在工作之余养成良好的自主学习习惯是非常好的&#xff…...

Stable Diffuse 之 安装文件夹、以及操作界面 UI 、Prompt相关说明

Stable Diffuse 之 安装文件夹、以及操作界面 UI 、Prompt相关说明 目录 Stable Diffuse 之 安装文件夹、以及操作界面 UI 、Prompt相关说明 一、简单介绍 二、安装文件相关说明 三、界面的简单说明 四、prompt 的一些语法简单说明 1、Prompt &#xff1a;正向提示词 &am…...

【Linux】- 一文秒懂shell编程

shell编程 1.1 Shell 是什么1.2 Shell 脚本的执行方式1.3 编写第一个 Shell 脚本2.1 Shell 的变量2.2 shell 变量的定义2.3 设置环境变量3.1 位置参数变量3.2 预定义变量4.1 运算符4.2 条件判断5.1 流程控制5.2 case 语句5.3 for 循环5.4 while 循环5.5 read基本语法6.1函数6.2…...

CentOS下多网卡绑定多IP段时导致只有一个会通的问题解决

CentOS下多网卡绑定多IP段时导致只有一个会通的问题解决 虚拟机配置多个网络地址&#xff0c;结果同时只能有一个ip是通的&#xff0c; 原因&#xff1a;Linux默认开启了反向路由检查导致的&#xff0c;比如说外面访问eth0的网卡&#xff0c;而网关在eth1上&#xff0c;又或者从…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...