当前位置: 首页 > 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;又或者从…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

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

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

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...