动态规划-回文串问题——5.最长回文子串
1.题目解析
题目来源:5.最长回文子串——力扣

测试用例

2.算法原理
1.状态表示
判断回文子串需要知道该回文子串的首尾下标,所以需要一个二维数组且数据类型为bool类型来存储每个子字符串是否为回文子串,
即dp[i][j]:以第i个位置为起始,第j个位置为结尾的子字符串是否为回文子串

2.状态转移方程
当需要判断的子字符串长度小于3可以直接判断是否相等,相等则直接为true,反之则为false
当长度大于3时则需要向中间判断,也就是将长字符串拆分为单个字符穿与两个字符串的情况即可

3.初始化
无需初始化,因为dp表存储的值为bool类型,因此在填表的过程中就动态的将每个位置赋了值
4.填表顺序
因为需要可能用到dp[i+1][j-1]也就是二维表的左下位置,因此需要从下向上填表
5.返回值
这里的dp表每个位置存储的都是该子字符串是否为回文子串,因此需要逐个判断找出最长的回文子串并求出其起始位置与长度,然后返回该子字符串即可
3.实战代码
代码分析

class Solution {
public:string longestPalindrome(string s) {int n = s.size();vector<vector<bool>> dp(n,vector<bool>(n));int len = 1,begin = 0;for(int i = n - 1;i >= 0;i--){for(int j = i;j < n;j++){if(s[i] == s[j]){dp[i][j] = i + 1 < j ? dp[i+1][j-1] : true;}if(dp[i][j] && j - i + 1 > len){len = j - i + 1;begin = i;}}} return s.substr(begin,len);}
};
相关文章:
动态规划-回文串问题——5.最长回文子串
1.题目解析 题目来源:5.最长回文子串——力扣 测试用例 2.算法原理 1.状态表示 判断回文子串需要知道该回文子串的首尾下标,所以需要一个二维数组且数据类型为bool类型来存储每个子字符串是否为回文子串, 即dp[i][j]:以第i个位置为起始&a…...
rtp协议:rtcp包发送和接收规则和报告!
RTCP Packet Send and Receive Rules: 发送和接收 RTCP 包的规则在此列出。允许在多播环境或多点单播环境中运行的实现必须满足第 6.2 节中的要求。这样的实现可以使用本节定义的算法来满足这些要求,或者可以使用其他算法,只要其性能等同或更…...
label数据(或自定义数据集)转imagenet(用于mmclassification)
理论上用于分类的图像一般都不需要用labelme来标注的,笔者是因为刚好手上有这么一组数据,所以就顺带处理了。labelme标注完的数据每张还包含了一个json文件,这个在分类任务中用不上。具体的mmclassification使用方法在我的另一篇文章里有&…...
WebMvcConfigurer
WebMvcConfigurer是Spring MVC框架中的一个核心接口,它允许开发者自定义Spring MVC的配置,以满足应用程序的特定需求。通过实现这个接口,开发者可以注册拦截器、添加视图控制器、配置视图解析器等,而无需使用XML配置。以下是对Web…...
Sigrity Power SI VR noise Metrics check模式如何进行电源噪声耦合分析操作指导
SSigrity Power SI VR noise Metrics check模式如何进行电源噪声耦合分析操作指导 Sigrity Power SI的VR noise Metrics check模式本质上是用来评估和观测器件的电源网络的耦合对于信号的影响,输出S参数以及列出具体的贡献值。 以下图为例...
Python+Appium+Pytest+Allure自动化测试框架-安装篇
文章目录 安装安装ADT安装NodeJs安装python安装appium安装Appium Server(可选)安装Appium-Inspector(可选)安装allure安装pytest PythonAppiumPytestAllure框架的安装 Appium是一个开源工具,是跨平台的,用于…...
Python的socket使用
在 Python 中,可以使用 socket 模块编写一个支持多个客户端连接的服务端。常见的实现方式包括使用多线程、多进程或异步 I/O。下面以多线程为例展示如何编写一个服务端,来同时接收和处理多个客户端的连接。 多线程服务端代码示例 这个示例服务端代码中…...
如何快速搭建一个3D虚拟展厅?
随着元宇宙概念的兴起,一个全新的虚拟、立体数字空间正逐步成为我们生活的一部分。在这个空间里,用户可以沉浸其中,进行丰富的交互操作,体验前所未有的无限可能。而如何快速搭建一个属于自己的元宇宙3D虚拟展厅,正成为…...
Android webview 打开本地H5项目(Cocos游戏以及Unity游戏)
webview打开本地Html文件 1.在路径前面加上file:// String filePath"file://"path;webView.loadUrl( filePath);2.打开权限 <uses-permission android:name"android.permission.READ_EXTERNAL_STORAGE" />3.启用JavaScript 设置本地访问权限 webVi…...
解决项目中图片出不来的bug
在页面端图片呈现割裂状: 查看代码: 将代码改成: 即可正常显示图片。...
手机实时提取SIM卡打电话的信令声音-新的篇章(三、Android虚拟声卡探索)
手机实时提取SIM卡打电话的信令声音-新的篇章(三、Android虚拟声卡探索) 前言 前面的篇章中,我们从理论方向和实际市面上出现的音频线传输声音的方式,讨论绕开手机对SIM卡电话通话声音的封锁场景的可行性,并实际选购几款数字和模拟的USB转接…...
REST APIs与微服务:关键差异
在构建基于微服务的应用程序时RESYful API和微服务这两个术语经常相伴出现。然而,它们指的是截然不同的东西。 了解 RESTful API 和微服务之间差异的最简单方式是这样: 微服务:它们是构成更大规模基于微服务的应用程序的单个服务和功能&…...
【网安案例学习】反向蛮力攻击Reverse Brute Force Attack
【故事一】 在一个温暖的秋日下午,Jack坐在旧金山一家宁静的咖啡馆里,准备开始他的最新写作项目:追溯反向蛮力攻击的起源和发展。这是一个他一直想深入挖掘的主题,因为它揭示了网络安全世界中一个鲜为人知却极具影响力的故事。 …...
TCP/IP网络编程:理解网络编程和套接字
TCP/IP网络编程:理解网络编程和套接字 网络编程又叫做套接字编程,是因为在网络编程中依赖使用套接字(socket),网络编程一般是C/S架构,即客户端/服务器模式,在服务器端依赖套接字绑定自身接口,并开启监听客户端连接&am…...
CSS实现回到顶部且平滑过渡
背景 最近同学在项目开发的时候问了我一个问题:小白,回到顶部该怎么做呀?我当时就愣住了,心想这不是很基础的一个功能吗,然后想到该同学没有系统学过网页三剑客,我就给他讲了该怎么实现这个虽然基础但在很多…...
10 go语言(golang) - 数据类型:哈希表(map)及原理(二)
扩容 在 Go 语言中,当 map 的元素数量达到一定阈值时,会触发扩容操作以保持性能。这个过程称为 rehashing,即重新散列所有的键值对到一个更大的哈希表中。 扩容的条件 源码: func mapassign(t *maptype, h *hmap, key unsafe.…...
【论文解读】Med-BERT: 用于疾病预测的大规模结构化电子健康记录的预训练情境化嵌入
【论文解读】Med-BERT: 用于疾病预测的大规模结构化电子健康记录的预训练情境化嵌入 Med-BERT:pretrained contextualized embeddings on large-scale structured electronic health records for disease prediction 摘要:基于电子健康记录(EHR)的深度学习(DL)预…...
[POI2014] PTA-Little Bird(单调队列优化 DP)
luogu 传送门https://www.luogu.com.cn/problem/P3572 解题思路 先设 表示到 的最小劳累值。 很容易得出转移: 其中 由 和 的大小关系决定,并且 。 很显然,直接暴力是 的,会超时。 于是,考虑优化。 我们发现…...
【含开题报告+文档+PPT+源码】基于SpringBoot的体育馆管理系统的设计与实现
开题报告 近年来,随着人们生活水平的提高和健康意识的增强,体育馆作为提供体育锻和休闲娱乐的重要场所,其使用频率和管理难度也在不断增加。传统的体育馆管理模式通常依赖于人工记录和手动操作,不仅效率低下,而且容易…...
Vue3学习:vue组件中的图片路径问题
今天在做一个案例的时候,图片放在assets/images文件夹下,如下路径,其中的图片不能正常显示。 list: [{ id: 1, name: 欧拉公式啤酒杯, price: 30.00, src: ./assets/images/Euler.png},{ id: 2, name: 高斯分布马克杯, price: 40.00, src: ./…...
《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》
引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...
解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...
剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...
NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...
【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统
目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...
MySQL 知识小结(一)
一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库,分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷,但是文件存放起来数据比较冗余,用二进制能够更好管理咱们M…...
Mysql8 忘记密码重置,以及问题解决
1.使用免密登录 找到配置MySQL文件,我的文件路径是/etc/mysql/my.cnf,有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...
