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

【算法day4】最长回文子串——动态规划方法

最长回文子串

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

https://leetcode.cn/problems/longest-palindromic-substring/submissions/607962358/

在这里插入图片描述

动态规划:

  1. 回文串即是从前面开始读和从后面开始读,读出来的字符串均相同的字符串,可以理解字符串正中间是一面镜子,镜子的两侧字符串必然对称。
    在这里插入图片描述

  2. 实际上回文串如果只含一个字符,必然是回文串;如果含2个字符,若两个字符相等,则必然是回文串,否则不是回文串,例如ab,这就不是回文串,‘bb’就是;

  3. 如果含多个字符,那么如果第一位和最后一位字符不相同,那肯定不是回文串(按照上图所示,回文串必然是对称的,如果第一位和最后一位字符不同,那么就必然存在不对称的情况了

  4. 如果含多个字符且第一位和最后一位字符相同,那么,如果它去除掉第一位和最后一位字符后,依然是回文串,那它肯定是回文串;否则,如果它去除掉第一位和最后一位字符后,不是回文串,那说明这个子串肯定不对称,不对称的话肯定就不是回文串了。所以问S[i,j]是不是字串,就要看它的子串S[i+1,j-1]是不是回文串。显然应该用动态规划

  5. 动态规划访问数组的时候一定要按照图里面的。1斜线,2斜线,3斜线……5斜线这个顺序去访问,
    在这里插入图片描述
    否则例如下面图示的这个访问顺序,会出现访问dp[0,3]时,dp[1,2] 没赋值就访问的问题

  6. 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&#xff0c;找到 s 中最长的 回文 子串。 https://leetcode.cn/problems/longest-palindromic-substring/submissions/607962358/ 动态规划&#xff1a; 回文串即是从前面开始读和从后面开始读&#xff0c;读出来的字符串均相同的字符串&#…...

C++之“string”类的模拟实现

​ &#x1f339;个人主页&#x1f339;&#xff1a;喜欢草莓熊的bear &#x1f339;专栏&#x1f339;&#xff1a;C入门 前言 hello &#xff0c;大家又来跟着bear学习了。一起奔向更好的自己&#xff0c;上篇博客已经讲清楚了string的一些功能的使用。我们就实现一些主要的功…...

请谈谈 HTTP 中的安全策略,如何防范常见的Web攻击(如XSS、CSRF)?

一、Web安全核心防御机制 &#xff08;一&#xff09;XSS攻击防御&#xff08;跨站脚本攻击&#xff09; 1. 原理与分类 ​存储型XSS&#xff1a;恶意脚本被持久化存储在服务端&#xff08;如数据库&#xff09;​反射型XSS&#xff1a;脚本通过URL参数或表单提交触发执行​…...

Python Flask 渲染静态程动态页面

Python Flask 渲染静态程动态页面 Python Flask 渲染静态程动态页面 Python Flask 渲染静态程动态页面 对网页应用程序来说&#xff0c;静态内容是重要的&#xff0c;因为它们包括 CSS 和 JavaScript 文件。静态文件可以直接由网页服务器提供。如果我们在我们的项目中创建一个…...

Unity大型游戏开发全流程指南

一、开发流程与核心步骤 1. 项目规划与设计阶段 需求分析 明确游戏类型&#xff08;MMORPG/开放世界/竞技等&#xff09;、核心玩法&#xff08;战斗/建造/社交&#xff09;、目标平台&#xff08;PC/移动/主机&#xff09;示例&#xff1a;MMORPG需规划角色成长树、副本Boss…...

Unity场景制作

一、关于后处理效果 然后可在后处理组件中添加各种效果 ACES : 电影感的强对比效果 添加了ACES后场景明显变暗&#xff0c;所以可以提高曝光度 Post-exposure 二、添加雾效 在Window的项目栏中选择Render中的Lighting 在环境属性中的其他设置中可勾选雾效&#xff0c;为场景中添…...

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. 代码实现 题目链接&#xff1a;3479. Fruits Into Baskets III 1. 解题思路 这一题思路本质上就是考察每一个水果被考察时找到第一个满足条件且未被使用的basket。 因此&#xff0c;我们只需要将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种优化算法&#xff08;optimizer&#xff09;解析 深度学习pytorch之4种归一化方法&#xff08;Normalization&#xff09;原理公式解析和参数使用 深度学习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++)

函数是什么 数学中我们其实就⻅过函数的概念&#xff0c;⽐如&#xff1a;⼀次函数 y kx b &#xff0c;k和b都是常数&#xff0c;给⼀个任意的x &#xff0c;就得到⼀个 y 值。其实在C/C语⾔中就引⼊了函数&#xff08;function&#xff09;的概念&#xff0c;有些翻译为&a…...

计算机视觉算法实战——老虎个体识别(主页有源码)

✨个人主页欢迎您的访问 ✨期待您的三连 ✨ ✨个人主页欢迎您的访问 ✨期待您的三连 ✨ ✨个人主页欢迎您的访问 ✨期待您的三连✨ ​ ​​​ 1. 领域介绍 老虎个体识别是计算机视觉中的一个重要应用领域&#xff0c;旨在通过分析老虎的独特条纹图案&#xff0c;自动识别和区…...

【移动WEB开发】rem适配布局

目录 1. rem基础 2.媒体查询 2.1 语法规范 2.2 媒体查询rem 2.3 引入资源&#xff08;理解&#xff09; 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年携程校招社招求职能力北森测评材料计算部分:备考要点与误区解析

在求职过程中&#xff0c;能力测评是筛选候选人的重要环节之一。对于携程这样的知名企业&#xff0c;其能力测评中的材料计算部分尤为关键。许多求职者在备考时容易陷入误区&#xff0c;导致在考试中表现不佳。本文将深入解析材料计算部分的实际考察方向&#xff0c;并提供针对…...

【Elasticsearch入门到落地】9、hotel数据结构分析

接上篇《8、RestClient操作索引库-基础介绍及导入demo》 上一篇我们介绍了RestClient的基础&#xff0c;并导入了使用Java语言编写的RestClient程序Demo以及将要分析的数据库。本篇我们就要分析导入的宾馆数据库tb_hotel表结构的具体含义&#xff0c;并分析如何建立其索引库。 …...

现代互联网网络安全与操作系统安全防御概要

现阶段国与国之间不用对方路由器&#xff0c;其实是有道理的&#xff0c;路由器破了&#xff0c;内网非常好攻击&#xff0c;内网共享开放端口也非常多&#xff0c;更容易攻击。还有些内存系统与pe系统自带浏览器都没有javascript脚本功能&#xff0c;也是有道理的&#xff0c;…...

轻量级TCC框架的实现

现有seata、tcc-transaction等tcc框架实现都较为重量级&#xff0c;今天主要带来一种轻量级的实现&#xff0c;大概只用了1200行代码实现。不依赖具体框架grpc、http、dubbo等&#xff0c;只需要业务系统按照标准化实现Try、Commit、Cancel实现接口即可。 已解决悬挂、幂等、空…...

共绘智慧升级,看永洪科技助力由由集团起航智慧征途

在数字化洪流汹涌澎湃的当下&#xff0c;企业如何乘风破浪&#xff0c;把握转型升级的黄金机遇&#xff0c;已成为所有企业必须直面的时代命题。由由集团&#xff0c;作为房地产的领航者&#xff0c;始终以前瞻视野引领变革&#xff0c;坚决拥抱数字化浪潮&#xff0c;携手数字…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

day36-多路IO复用

一、基本概念 &#xff08;服务器多客户端模型&#xff09; 定义&#xff1a;单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用&#xff1a;应用程序通常需要处理来自多条事件流中的事件&#xff0c;比如我现在用的电脑&#xff0c;需要同时处理键盘鼠标…...

毫米波雷达基础理论(3D+4D)

3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文&#xff1a; 一文入门汽车毫米波雷达基本原理 &#xff1a;https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...

保姆级【快数学会Android端“动画“】+ 实现补间动画和逐帧动画!!!

目录 补间动画 1.创建资源文件夹 2.设置文件夹类型 3.创建.xml文件 4.样式设计 5.动画设置 6.动画的实现 内容拓展 7.在原基础上继续添加.xml文件 8.xml代码编写 (1)rotate_anim (2)scale_anim (3)translate_anim 9.MainActivity.java代码汇总 10.效果展示 逐帧…...