【动态规划刷题 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.状态转移方程
对于回⽂串,我们⼀般分析⼀个「区间两头」的元素:
- 当 s[i] != s[j] 的时候:不可能是回⽂串, dp[i][j] = 0 ;
- 当 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 ,请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。 具有不同开始位置或结束位置的子串,即使是由…...
mysql 每日自动备份数据库
在 MySQL 中,你可以使用定时任务来每日自动备份数据库。通常,最常用的方法是使用操作系统的定时任务工具(如cron)来调度备份操作。以下是一些步骤来设置每日定时备份MySQL数据库: 创建备份脚本:首先&#x…...
【计算机网络】图解路由器(二)
本系列包含: 图解路由器(一)图解路由器(二) 图解路由器(二) 21、什么是静态路由?22、什么是动态路由?23、动态路由有哪些类型?24、什么是 RIP ?2…...
流媒体及直播相关知识
文章目录 前言一、流媒体1、基本概念2、流式传输3、流媒体技术原理4、流媒体传输模式5、H.264 流媒体传输系统框架 二、直播1、直播中使用的流媒体协议2、直播的模块划分3、视频直播流程①、推流到服务器②、服务器流分发 前言 本文主要讲解流媒体及其直播相关知识,…...
数据治理-数据资产估值
数据生命周期大多数阶段涉及成本。数据只有使用时才有价值,使用时数据还产生与风险相关的成本。因此,当使用数据的经济效益超过了上述成本时,就会显现其价值。 其他的度量价值的方式包括: 替换成本。数据替换或恢复的成本。包括组…...
点云从入门到精通技术详解100篇-机载 LiDAR 点云滤波及分类
目录 前言 国内外研究现状 点云滤波研究现状 点云分类研究现状...
【SLAM】 前端-视觉里程计之相对位姿估计
【SLAM】 前端-视觉里程计之相对位姿估计 1.相对位姿估计 在前端视觉里程计中,相对位姿估计是指通过视觉传感器(例如相机)捕捉的图像信息,来估计相机相对于先前位置的位姿(位置和姿态)变化。这种估计通常…...
git format-patch打补丁
git format-patch HEAD^ 这个命令会产生从倒数第二个提交 HEAD^ 到最后提交 HEAD 之间所有提交的差异,并生成一个包含这些差异的补丁文件。这是一个包含详细步骤的例子: 第一步,创建一个新的 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++】搜索二叉树底层实现
目录 一,概念 二,实现分析 1. 插入 (1.)非递归版本 (2.)递归版本 2. 打印搜索二叉树 3.查找函数 (1.)非递归版本 (2.)递归版本 4. 删除函数&#x…...
C8051F020 SMBus一直处于busy状态解决办法
当SMBus总线处于busy状态切且无法自动释放时,SMB0CN寄存器的第7位一直为 1,总线没有释放。 SMBus总线释放超时的一个纠错机制,它允许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)中各元素分布在存储器的不同存储块,成为结点,通过地址或指针建立元素之间的联系。 结点的 data 域存放数据元素 ai ,而 next 域是一个指针,指向 ai 的直接后继 ai1 …...
Android 12 Bluetooth源码分析蓝牙配对
本文主要是列出一些蓝牙配对重要的类和方法/函数,遇到相关问题时方便查找添加log排查。 蓝牙扫描列表页面:packages/apps/Settings/src/com/android/settings/bluetooth/DeviceListPreferenceFragment.java点击其中一个设备会调用:onPrefere…...
Python异步编程并发执行爬虫任务,用回调函数解析响应
一、问题:当发送API请求,读写数据库任务较重时,程序运行效率急剧下降。 异步技术是Python编程中对提升性能非常重要的一项技术。在实际应用,经常面临对外发送网络请求,调用外部接口,或者不断更新数据库或文…...
React组件化开发
1.组件的定义方式 函数组件Functional Component类组件Class Component 2.类组件 export class Profile extends Component {render() {console.log(this.context);return (<div>Profile</div>)} } 组件的名称是大写字符开头(无论类组件还是函数组件…...
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…...
自动化测试的定位及一些思考
大家对自动化的理解,首先是想到Web UI自动化,这就为什么我一说自动化,公司一般就会有很多人反对,因为自动化的成本实在太高了,其实自动化是分为三个层面的(UI层自动化、接口自动化、单元测试)&a…...
展会动态 | 迪捷软件邀您参加2023世界智能网联汽车大会
*9月18日之前注册的观众免收门票费* 由北京市人民政府、工业和信息化部、公安部、交通运输部和中国科学技术协会联合主办的2023世界智能网联汽车大会将于9月21日-24日在北京中国国际展览中心(顺义馆)举行。 论坛背景 本届展会以“聚智成势 协同向新——…...
《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》
引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...
CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
深度学习习题2
1.如果增加神经网络的宽度,精确度会增加到一个特定阈值后,便开始降低。造成这一现象的可能原因是什么? A、即使增加卷积核的数量,只有少部分的核会被用作预测 B、当卷积核数量增加时,神经网络的预测能力会降低 C、当卷…...
代码规范和架构【立芯理论一】(2025.06.08)
1、代码规范的目标 代码简洁精炼、美观,可持续性好高效率高复用,可移植性好高内聚,低耦合没有冗余规范性,代码有规可循,可以看出自己当时的思考过程特殊排版,特殊语法,特殊指令,必须…...
android13 app的触摸问题定位分析流程
一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...
Qemu arm操作系统开发环境
使用qemu虚拟arm硬件比较合适。 步骤如下: 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载,下载地址:https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...
Docker拉取MySQL后数据库连接失败的解决方案
在使用Docker部署MySQL时,拉取并启动容器后,有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致,包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因,并提供解决方案。 一、确认MySQL容器的运行状态 …...
渗透实战PortSwigger靶场:lab13存储型DOM XSS详解
进来是需要留言的,先用做简单的 html 标签测试 发现面的</h1>不见了 数据包中找到了一个loadCommentsWithVulnerableEscapeHtml.js 他是把用户输入的<>进行 html 编码,输入的<>当成字符串处理回显到页面中,看来只是把用户输…...
