【算法day4】最长回文子串——动态规划方法
最长回文子串
给你一个字符串 s,找到 s 中最长的 回文 子串。
https://leetcode.cn/problems/longest-palindromic-substring/submissions/607962358/

动态规划:
-
回文串即是
从前面开始读和从后面开始读,读出来的字符串均相同的字符串,可以理解字符串正中间是一面镜子,镜子的两侧字符串必然对称。

-
实际上回文串如果只含一个字符,必然是回文串;如果含2个字符,若两个字符相等,则必然是回文串,否则不是回文串,例如
ab,这就不是回文串,‘bb’就是; -
如果含多个字符,那么如果第一位和最后一位字符不相同,那肯定不是回文串(
按照上图所示,回文串必然是对称的,如果第一位和最后一位字符不同,那么就必然存在不对称的情况了) -
如果含多个字符且第一位和最后一位字符相同,那么,如果它去除掉第一位和最后一位字符后,依然是回文串,那它肯定是回文串;否则,如果它去除掉第一位和最后一位字符后,不是回文串,那说明这个子串肯定不对称,不对称的话肯定就不是回文串了。所以问S[i,j]是不是字串,就要看它的子串S[i+1,j-1]是不是回文串。显然应该用动态规划。
-
动态规划访问数组的时候一定要按照图里面的。1斜线,2斜线,3斜线……5斜线这个顺序去访问,

否则例如下面图示的这个访问顺序,会出现访问dp[0,3]时,dp[1,2] 没赋值就访问的问题

-
vector最好用int,
vector<vector<int>>,别用布尔bool,否则难以察觉到自己的算法是否有数组越界的问题。
class Solution {
public:string longestPalindrome(string s) {int s_len = s.size();if (s_len <= 1) {return s;}int max_len = 1, begin = 0; // 最大回文长度和起始位置vector<vector<int>> dp(s_len, vector<int>(s_len));// S[i][i]也就是串的i号位字符,由于所有长度为1的串都是回文,所以是truefor (int i = 0; i < s_len; i++) {dp[i][i] = true;}// 由于s[i][j]回文取决于S[i+1][j-1]是否是回文,所以优先填充斜线// 当前检测的子串长度为Lfor (int L = 2; L <= s_len; L++) {for (int i = 0; i < s_len; i++) {int j = L + i - 1;if (j >= s_len)//子串终点标记j不能大于父串break;if (s[i] == s[j]) {//看看字串是否是回文串if (j - i + 1 <= 2) {//长度2,又有s[i] == s[j],必然是回文串dp[i][j] = true;} else {dp[i][j] = dp[i + 1][j - 1];}} else {// s[i] != s[j],出现了不对称的情况,不可能是回文串了dp[i][j] = false;}if (dp[i][j] && max_len < j - i + 1) {// 此次迭代检测到回文串,更新最大值begin = i;max_len = j - i + 1;}}}return s.substr(begin, max_len);}
};
相关文章:
【算法day4】最长回文子串——动态规划方法
最长回文子串 给你一个字符串 s,找到 s 中最长的 回文 子串。 https://leetcode.cn/problems/longest-palindromic-substring/submissions/607962358/ 动态规划: 回文串即是从前面开始读和从后面开始读,读出来的字符串均相同的字符串&#…...
C++之“string”类的模拟实现
🌹个人主页🌹:喜欢草莓熊的bear 🌹专栏🌹:C入门 前言 hello ,大家又来跟着bear学习了。一起奔向更好的自己,上篇博客已经讲清楚了string的一些功能的使用。我们就实现一些主要的功…...
请谈谈 HTTP 中的安全策略,如何防范常见的Web攻击(如XSS、CSRF)?
一、Web安全核心防御机制 (一)XSS攻击防御(跨站脚本攻击) 1. 原理与分类 存储型XSS:恶意脚本被持久化存储在服务端(如数据库)反射型XSS:脚本通过URL参数或表单提交触发执行…...
Python Flask 渲染静态程动态页面
Python Flask 渲染静态程动态页面 Python Flask 渲染静态程动态页面 Python Flask 渲染静态程动态页面 对网页应用程序来说,静态内容是重要的,因为它们包括 CSS 和 JavaScript 文件。静态文件可以直接由网页服务器提供。如果我们在我们的项目中创建一个…...
Unity大型游戏开发全流程指南
一、开发流程与核心步骤 1. 项目规划与设计阶段 需求分析 明确游戏类型(MMORPG/开放世界/竞技等)、核心玩法(战斗/建造/社交)、目标平台(PC/移动/主机)示例:MMORPG需规划角色成长树、副本Boss…...
Unity场景制作
一、关于后处理效果 然后可在后处理组件中添加各种效果 ACES : 电影感的强对比效果 添加了ACES后场景明显变暗,所以可以提高曝光度 Post-exposure 二、添加雾效 在Window的项目栏中选择Render中的Lighting 在环境属性中的其他设置中可勾选雾效,为场景中添…...
PCIE接口
PCIE接口 PIC接口介绍PIC总线结构PCI总线特点PCI总线的主要性能PIC的历程 PCIE接口介绍PCIe接口总线位宽PCIE速率GT/s和Gbps区别PCIE带宽计算 PCIE架构PCIe体系结构端到端的差分数据传递PCIe总线的层次结构事务层数据链路层物理层PCIe层级结构及功能框图 PCIe链路初始化PCIe链路…...
Leetcode 3479. Fruits Into Baskets III
Leetcode 3479. Fruits Into Baskets III 1. 解题思路2. 代码实现 题目链接:3479. Fruits Into Baskets III 1. 解题思路 这一题思路本质上就是考察每一个水果被考察时找到第一个满足条件且未被使用的basket。 因此,我们只需要将basket按照其capacit…...
小程序 -- uni-app开发微信小程序环境搭建(HBuilder X+微信开发者工具)
目录 前言 一 软件部分 1. 微信开发者工具 2. HBuilder X 开发工具 二 配置部分 1. 关于 HBuilder X 配置 2. 关于 微信开发工具 配置 三 运行项目 1. 新建项目 2. 代码编写 3. 内置浏览器 编译 4. 配置小程序 AppID获取 注意 四 实现效果 前言 uni-app开发小程…...
深度学习PyTorch之13种模型精度评估公式及调用方法
深度学习pytorch之22种损失函数数学公式和代码定义 深度学习pytorch之19种优化算法(optimizer)解析 深度学习pytorch之4种归一化方法(Normalization)原理公式解析和参数使用 深度学习pytorch之简单方法自定义9类卷积即插即用 实时…...
《云原生监控体系构建实录:从Prometheus到Grafana的观测革命》
PrometheusGrafana部署配置 Prometheus安装 下载Prometheus服务端 Download | PrometheusAn open-source monitoring system with a dimensional data model, flexible query language, efficient time series database and modern alerting approach.https://prometheus.io/…...
GHCTF2025--Web
upload?SSTI! import os import refrom flask import Flask, request, jsonify,render_template_string,send_from_directory, abort,redirect from werkzeug.utils import secure_filename import os from werkzeug.utils import secure_filenameapp Flask(__name__)# 配置…...
NO.32十六届蓝桥杯备战|函数|库函数|自定义函数|实参|形参|传参(C++)
函数是什么 数学中我们其实就⻅过函数的概念,⽐如:⼀次函数 y kx b ,k和b都是常数,给⼀个任意的x ,就得到⼀个 y 值。其实在C/C语⾔中就引⼊了函数(function)的概念,有些翻译为&a…...
计算机视觉算法实战——老虎个体识别(主页有源码)
✨个人主页欢迎您的访问 ✨期待您的三连 ✨ ✨个人主页欢迎您的访问 ✨期待您的三连 ✨ ✨个人主页欢迎您的访问 ✨期待您的三连✨ 1. 领域介绍 老虎个体识别是计算机视觉中的一个重要应用领域,旨在通过分析老虎的独特条纹图案,自动识别和区…...
【移动WEB开发】rem适配布局
目录 1. rem基础 2.媒体查询 2.1 语法规范 2.2 媒体查询rem 2.3 引入资源(理解) 3. less基础 3.1 维护css的弊端 3.2 less介绍 3.3 less变量 3.4 less编译 3.5 less嵌套 3.6 less运算 4. rem适配方案 4.1 rem实际开发 4.2 技术使用 4.3 …...
25年携程校招社招求职能力北森测评材料计算部分:备考要点与误区解析
在求职过程中,能力测评是筛选候选人的重要环节之一。对于携程这样的知名企业,其能力测评中的材料计算部分尤为关键。许多求职者在备考时容易陷入误区,导致在考试中表现不佳。本文将深入解析材料计算部分的实际考察方向,并提供针对…...
【Elasticsearch入门到落地】9、hotel数据结构分析
接上篇《8、RestClient操作索引库-基础介绍及导入demo》 上一篇我们介绍了RestClient的基础,并导入了使用Java语言编写的RestClient程序Demo以及将要分析的数据库。本篇我们就要分析导入的宾馆数据库tb_hotel表结构的具体含义,并分析如何建立其索引库。 …...
现代互联网网络安全与操作系统安全防御概要
现阶段国与国之间不用对方路由器,其实是有道理的,路由器破了,内网非常好攻击,内网共享开放端口也非常多,更容易攻击。还有些内存系统与pe系统自带浏览器都没有javascript脚本功能,也是有道理的,…...
轻量级TCC框架的实现
现有seata、tcc-transaction等tcc框架实现都较为重量级,今天主要带来一种轻量级的实现,大概只用了1200行代码实现。不依赖具体框架grpc、http、dubbo等,只需要业务系统按照标准化实现Try、Commit、Cancel实现接口即可。 已解决悬挂、幂等、空…...
共绘智慧升级,看永洪科技助力由由集团起航智慧征途
在数字化洪流汹涌澎湃的当下,企业如何乘风破浪,把握转型升级的黄金机遇,已成为所有企业必须直面的时代命题。由由集团,作为房地产的领航者,始终以前瞻视野引领变革,坚决拥抱数字化浪潮,携手数字…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
三维GIS开发cesium智慧地铁教程(5)Cesium相机控制
一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点: 路径验证:确保相对路径.…...
JavaScript 中的 ES|QL:利用 Apache Arrow 工具
作者:来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗?了解下一期 Elasticsearch Engineer 培训的时间吧! Elasticsearch 拥有众多新功能,助你为自己…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...
如何在看板中体现优先级变化
在看板中有效体现优先级变化的关键措施包括:采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中,设置任务排序规则尤其重要,因为它让看板视觉上直观地体…...
基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...
