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

【动态规划刷题 17】回文子串 最长回文子串

647. 回文子串

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

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

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

具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。

示例 1:

输入:s = “abc”
输出:3
解释:三个回文子串: “a”, “b”, “c”
示例 2:

输入:s = “aaa”
输出:6
解释:6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

解法(动态规划):
算法思路:
我们可以先「预处理」⼀下,将所有⼦串「是否回⽂」的信息统计在 dp 表⾥⾯,然后直接在表⾥⾯统计 true 的个数即可。

1.状态表示*
为了能表⽰出来所有的⼦串,我们可以创建⼀个 n * n 的⼆维 dp 表,只⽤到「上三⻆部分」
即可。
其中, dp[i][j] 表⽰: s 字符串 [i, j] 的⼦串,是否是回⽂串。

2.状态转移方程
对于回⽂串,我们⼀般分析⼀个「区间两头」的元素:

  1. 当 s[i] != s[j] 的时候:不可能是回⽂串, dp[i][j] = 0 ;
  2. 当 s[i] == s[j] 的时候:根据⻓度分三种情况讨论:
    • ⻓度为 1 ,也就是 i == j :此时⼀定是回⽂串,dp[i][j] = true ;
    • ⻓度为 2 ,也就是 i + 1 == j :此时也⼀定是回⽂串, dp[i][j] =true ;
    • ⻓度⼤于 2 ,此时要去看看 [i + 1, j - 1] 区间的⼦串是否回⽂: dp[i][j]= dp[i + 1][j - 1] 。

综上,状态转移⽅程分情况谈论即可。

3. 初始化
因为我们的状态转移⽅程分析的很细致,因此⽆需初始化。

4. 填表顺序
根据「状态转移⽅程」,我们需要「从下往上」填写每⼀⾏,每⼀⾏的顺序⽆所谓

5. 返回值
根据「状态表⽰和题⽬要求」,我们需要返回 dp 表中 true 的个数

代码:

 int countSubstrings(string s) {int n=s.size();vector<vector<int>> dp(n,vector<int>(n));dp[0][0]=1;int sum=1;for(int j=1;j<n;j++){for(int i=0;i<=j;i++){if(s[j]==s[i]){if(j==i||j==i+1) dp[i][j]=1;if(j-i>1){dp[i][j]=dp[i+1][j-1];}}if(dp[i][j]) sum++;}}return sum;}

在这里插入图片描述

5. 最长回文子串

链接: 5. 最长回文子串

给你一个字符串 s,找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。

示例 1:

输入:s = “babad”
输出:“bab”
解释:“aba” 同样是符合题意的答案。
示例 2:

输入:s = “cbbd”
输出:“bb”

解法思路:

  • a. 我们可以先⽤ dp 表统计出「所有⼦串是否回⽂」的信息
  • b. 然后根据 dp 表⽰ true 的位置,得到回⽂串的「起始位置」和「⻓度」。 那么我们就可以在表中找出最⻓回⽂串。

关于「预处理所有⼦串是否回⽂」,已经在上⼀道题⽬⾥已经讲解过了。

代码:

  string longestPalindrome(string s) {int n=s.size();vector<vector<int>> dp(n,vector<int>(n));dp[0][0]=1;int sum=1;string ret(1,s[0]);for(int j=1;j<n;j++){for(int i=0;i<=j;i++){if(s[j]==s[i]){if(j==i||j==i+1) dp[i][j]=1;if(j-i>1){dp[i][j]=dp[i+1][j-1];}}if(dp[i][j]){if(j-i+1>sum){sum=j-i+1;string tmp(s.begin()+i,s.begin()+j+1);ret=tmp;}}}}return ret;}

在这里插入图片描述

相关文章:

【动态规划刷题 17】回文子串 最长回文子串

647. 回文子串 链接: 647. 回文子串 给你一个字符串 s &#xff0c;请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。 具有不同开始位置或结束位置的子串&#xff0c;即使是由…...

mysql 每日自动备份数据库

在 MySQL 中&#xff0c;你可以使用定时任务来每日自动备份数据库。通常&#xff0c;最常用的方法是使用操作系统的定时任务工具&#xff08;如cron&#xff09;来调度备份操作。以下是一些步骤来设置每日定时备份MySQL数据库&#xff1a; 创建备份脚本&#xff1a;首先&#x…...

【计算机网络】图解路由器(二)

本系列包含&#xff1a; 图解路由器&#xff08;一&#xff09;图解路由器&#xff08;二&#xff09; 图解路由器&#xff08;二&#xff09; 21、什么是静态路由&#xff1f;22、什么是动态路由&#xff1f;23、动态路由有哪些类型&#xff1f;24、什么是 RIP &#xff1f;2…...

流媒体及直播相关知识

文章目录 前言一、流媒体1、基本概念2、流式传输3、流媒体技术原理4、流媒体传输模式5、H.264 流媒体传输系统框架 二、直播1、直播中使用的流媒体协议2、直播的模块划分3、视频直播流程①、推流到服务器②、服务器流分发 前言 本文主要讲解流媒体及其直播相关知识&#xff0c…...

数据治理-数据资产估值

数据生命周期大多数阶段涉及成本。数据只有使用时才有价值&#xff0c;使用时数据还产生与风险相关的成本。因此&#xff0c;当使用数据的经济效益超过了上述成本时&#xff0c;就会显现其价值。 其他的度量价值的方式包括&#xff1a; 替换成本。数据替换或恢复的成本。包括组…...

点云从入门到精通技术详解100篇-机载 LiDAR 点云滤波及分类

目录 前言 国内外研究现状 点云滤波研究现状 点云分类研究现状...

【SLAM】 前端-视觉里程计之相对位姿估计

【SLAM】 前端-视觉里程计之相对位姿估计 1.相对位姿估计 在前端视觉里程计中&#xff0c;相对位姿估计是指通过视觉传感器&#xff08;例如相机&#xff09;捕捉的图像信息&#xff0c;来估计相机相对于先前位置的位姿&#xff08;位置和姿态&#xff09;变化。这种估计通常…...

git format-patch打补丁

git format-patch HEAD^ 这个命令会产生从倒数第二个提交 HEAD^ 到最后提交 HEAD 之间所有提交的差异&#xff0c;并生成一个包含这些差异的补丁文件。这是一个包含详细步骤的例子&#xff1a; 第一步&#xff0c;创建一个新的 git 仓库并进行一些提交。这些提交是我们稍后会生…...

大数据Flink(八十三):SQL语法的DML:With、SELECT WHERE、SELECT DISTINCT 子句

文章目录 SQL语法的DML:With、SELECT & WHERE、SELECT DISTINCT 子句 一、DML:With 子句...

C++:list

目录 List的模拟实现 List节点类 List链表结构 List迭代器类 结构 T& operator*(); T& operator->(); Self& operator(); Self operator(int); Self& operator--(); Self& operator--(int); bool operator!(const Self& l); bool oper…...

【C++】搜索二叉树底层实现

目录 一&#xff0c;概念 二&#xff0c;实现分析 1. 插入 &#xff08;1.&#xff09;非递归版本 &#xff08;2.&#xff09;递归版本 2. 打印搜索二叉树 3.查找函数 &#xff08;1.&#xff09;非递归版本 &#xff08;2.&#xff09;递归版本 4. 删除函数&#x…...

C8051F020 SMBus一直处于busy状态解决办法

当SMBus总线处于busy状态切且无法自动释放时&#xff0c;SMB0CN寄存器的第7位一直为 1&#xff0c;总线没有释放。 SMBus总线释放超时的一个纠错机制&#xff0c;它允许SMBus状态机在 SDA 和 SCL 信号线同为高电平超过 10个SMBus时钟源周期后判断总线为释放状态。 如果总线释放…...

Activiz 9.2 for Linux Crack

Activiz 9.2 在 C#、.Net 和 Unity 软件中为您的 3D 内容释放可视化工具包的强大功能。 ActiViz 允许您轻松地将 3D 可视化集成到您的应用程序中。 ActiViz 功能 用 C# 封装的 3D 可视化软件系统 允许在 .NET 环境中快速开发可投入生产的交互式3D 应用程序 支持窗口演示基础 (…...

数据结构 - 链表

线性表的链式存储结构 概念 将线性表 L (a0, a1, … , an-1)中各元素分布在存储器的不同存储块&#xff0c;成为结点&#xff0c;通过地址或指针建立元素之间的联系。 结点的 data 域存放数据元素 ai &#xff0c;而 next 域是一个指针&#xff0c;指向 ai 的直接后继 ai1 …...

Android 12 Bluetooth源码分析蓝牙配对

本文主要是列出一些蓝牙配对重要的类和方法/函数&#xff0c;遇到相关问题时方便查找添加log排查。 蓝牙扫描列表页面&#xff1a;packages/apps/Settings/src/com/android/settings/bluetooth/DeviceListPreferenceFragment.java点击其中一个设备会调用&#xff1a;onPrefere…...

Python异步编程并发执行爬虫任务,用回调函数解析响应

一、问题&#xff1a;当发送API请求&#xff0c;读写数据库任务较重时&#xff0c;程序运行效率急剧下降。 异步技术是Python编程中对提升性能非常重要的一项技术。在实际应用&#xff0c;经常面临对外发送网络请求&#xff0c;调用外部接口&#xff0c;或者不断更新数据库或文…...

React组件化开发

1.组件的定义方式 函数组件Functional Component类组件Class Component 2.类组件 export class Profile extends Component {render() {console.log(this.context);return (<div>Profile</div>)} } 组件的名称是大写字符开头&#xff08;无论类组件还是函数组件…...

LuatOS-SOC接口文档(air780E)--crypto - 加解密和hash函数

crypto.md5(str) 计算md5值 参数 传入值类型 解释 string 需要计算的字符串 返回值 返回值类型 解释 string 计算得出的md5值的hex字符串 例子 -- 计算字符串"abc"的md5 log.info("md5", crypto.md5("abc"))crypto.hmac_md5(str, k…...

自动化测试的定位及一些思考

大家对自动化的理解&#xff0c;首先是想到Web UI自动化&#xff0c;这就为什么我一说自动化&#xff0c;公司一般就会有很多人反对&#xff0c;因为自动化的成本实在太高了&#xff0c;其实自动化是分为三个层面的&#xff08;UI层自动化、接口自动化、单元测试&#xff09;&a…...

展会动态 | 迪捷软件邀您参加2023世界智能网联汽车大会

*9月18日之前注册的观众免收门票费* 由北京市人民政府、工业和信息化部、公安部、交通运输部和中国科学技术协会联合主办的2023世界智能网联汽车大会将于9月21日-24日在北京中国国际展览中心&#xff08;顺义馆&#xff09;举行。 论坛背景 本届展会以“聚智成势 协同向新——…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

[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…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...