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

动态规划-回文串问题——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.题目解析 题目来源&#xff1a;5.最长回文子串——力扣 测试用例 2.算法原理 1.状态表示 判断回文子串需要知道该回文子串的首尾下标&#xff0c;所以需要一个二维数组且数据类型为bool类型来存储每个子字符串是否为回文子串&#xff0c; 即dp[i][j]:以第i个位置为起始&a…...

rtp协议:rtcp包发送和接收规则和报告!

RTCP Packet Send and Receive Rules&#xff1a; 发送和接收 RTCP 包的规则在此列出。允许在多播环境或多点单播环境中运行的实现必须满足第 6.2 节中的要求。这样的实现可以使用本节定义的算法来满足这些要求&#xff0c;或者可以使用其他算法&#xff0c;只要其性能等同或更…...

label数据(或自定义数据集)转imagenet(用于mmclassification)

理论上用于分类的图像一般都不需要用labelme来标注的&#xff0c;笔者是因为刚好手上有这么一组数据&#xff0c;所以就顺带处理了。labelme标注完的数据每张还包含了一个json文件&#xff0c;这个在分类任务中用不上。具体的mmclassification使用方法在我的另一篇文章里有&…...

WebMvcConfigurer

WebMvcConfigurer是Spring MVC框架中的一个核心接口&#xff0c;它允许开发者自定义Spring MVC的配置&#xff0c;以满足应用程序的特定需求。通过实现这个接口&#xff0c;开发者可以注册拦截器、添加视图控制器、配置视图解析器等&#xff0c;而无需使用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&#xff08;可选&#xff09;安装Appium-Inspector&#xff08;可选&#xff09;安装allure安装pytest PythonAppiumPytestAllure框架的安装 Appium是一个开源工具&#xff0c;是跨平台的&#xff0c;用于…...

Python的socket使用

在 Python 中&#xff0c;可以使用 socket 模块编写一个支持多个客户端连接的服务端。常见的实现方式包括使用多线程、多进程或异步 I/O。下面以多线程为例展示如何编写一个服务端&#xff0c;来同时接收和处理多个客户端的连接。 多线程服务端代码示例 这个示例服务端代码中…...

如何快速搭建一个3D虚拟展厅?

随着元宇宙概念的兴起&#xff0c;一个全新的虚拟、立体数字空间正逐步成为我们生活的一部分。在这个空间里&#xff0c;用户可以沉浸其中&#xff0c;进行丰富的交互操作&#xff0c;体验前所未有的无限可能。而如何快速搭建一个属于自己的元宇宙3D虚拟展厅&#xff0c;正成为…...

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

在页面端图片呈现割裂状&#xff1a; 查看代码&#xff1a; 将代码改成&#xff1a; 即可正常显示图片。...

手机实时提取SIM卡打电话的信令声音-新的篇章(三、Android虚拟声卡探索)

手机实时提取SIM卡打电话的信令声音-新的篇章(三、Android虚拟声卡探索) 前言 前面的篇章中&#xff0c;我们从理论方向和实际市面上出现的音频线传输声音的方式&#xff0c;讨论绕开手机对SIM卡电话通话声音的封锁场景的可行性&#xff0c;并实际选购几款数字和模拟的USB转接…...

REST APIs与微服务:关键差异

在构建基于微服务的应用程序时RESYful API和微服务这两个术语经常相伴出现。然而&#xff0c;它们指的是截然不同的东西。 了解 RESTful API 和微服务之间差异的最简单方式是这样&#xff1a; 微服务&#xff1a;它们是构成更大规模基于微服务的应用程序的单个服务和功能&…...

【网安案例学习】反向蛮力攻击Reverse Brute Force Attack

【故事一】 在一个温暖的秋日下午&#xff0c;Jack坐在旧金山一家宁静的咖啡馆里&#xff0c;准备开始他的最新写作项目&#xff1a;追溯反向蛮力攻击的起源和发展。这是一个他一直想深入挖掘的主题&#xff0c;因为它揭示了网络安全世界中一个鲜为人知却极具影响力的故事。 …...

TCP/IP网络编程:理解网络编程和套接字

TCP/IP网络编程&#xff1a;理解网络编程和套接字 网络编程又叫做套接字编程&#xff0c;是因为在网络编程中依赖使用套接字(socket),网络编程一般是C/S架构&#xff0c;即客户端/服务器模式&#xff0c;在服务器端依赖套接字绑定自身接口&#xff0c;并开启监听客户端连接&am…...

CSS实现回到顶部且平滑过渡

背景 最近同学在项目开发的时候问了我一个问题&#xff1a;小白&#xff0c;回到顶部该怎么做呀&#xff1f;我当时就愣住了&#xff0c;心想这不是很基础的一个功能吗&#xff0c;然后想到该同学没有系统学过网页三剑客&#xff0c;我就给他讲了该怎么实现这个虽然基础但在很多…...

10 go语言(golang) - 数据类型:哈希表(map)及原理(二)

扩容 在 Go 语言中&#xff0c;当 map 的元素数量达到一定阈值时&#xff0c;会触发扩容操作以保持性能。这个过程称为 rehashing&#xff0c;即重新散列所有的键值对到一个更大的哈希表中。 扩容的条件 源码&#xff1a; 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 解题思路 先设 表示到 的最小劳累值。 很容易得出转移&#xff1a; 其中 由 和 的大小关系决定&#xff0c;并且 。 很显然&#xff0c;直接暴力是 的&#xff0c;会超时。 于是&#xff0c;考虑优化。 我们发现…...

【含开题报告+文档+PPT+源码】基于SpringBoot的体育馆管理系统的设计与实现

开题报告 近年来&#xff0c;随着人们生活水平的提高和健康意识的增强&#xff0c;体育馆作为提供体育锻和休闲娱乐的重要场所&#xff0c;其使用频率和管理难度也在不断增加。传统的体育馆管理模式通常依赖于人工记录和手动操作&#xff0c;不仅效率低下&#xff0c;而且容易…...

Vue3学习:vue组件中的图片路径问题

今天在做一个案例的时候&#xff0c;图片放在assets/images文件夹下&#xff0c;如下路径&#xff0c;其中的图片不能正常显示。 list: [{ id: 1, name: 欧拉公式啤酒杯, price: 30.00, src: ./assets/images/Euler.png},{ id: 2, name: 高斯分布马克杯, price: 40.00, src: ./…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

AspectJ 在 Android 中的完整使用指南

一、环境配置&#xff08;Gradle 7.0 适配&#xff09; 1. 项目级 build.gradle // 注意&#xff1a;沪江插件已停更&#xff0c;推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...

Chrome 浏览器前端与客户端双向通信实战

Chrome 前端&#xff08;即页面 JS / Web UI&#xff09;与客户端&#xff08;C 后端&#xff09;的交互机制&#xff0c;是 Chromium 架构中非常核心的一环。下面我将按常见场景&#xff0c;从通道、流程、技术栈几个角度做一套完整的分析&#xff0c;特别适合你这种在分析和改…...