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

牛客热题:最长回文子串

📟作者主页:慢热的陕西人

🌴专栏链接:力扣刷题日记

📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言

在这里插入图片描述

文章目录

  • 牛客热题:最长回文子串
    • 题目链接
    • 方法一:动态规划
      • 思路
      • 代码
      • 复杂度

牛客热题:最长回文子串

题目链接

最长回文子串_牛客题霸_牛客网 (nowcoder.com)

方法一:动态规划

思路

①状态表示:

d p [ i ] [ j ] dp[i][j] dp[i][j]表示以A[i],A[j]为头尾的字符串是否是回文字符串的状态

②状态转移方程:

当A[i] 和 A[j] 相等的情况下:

d p [ i ] [ j ] = d p [ i + 1 ] [ j − 1 ] dp[i][j] = dp[i + 1][j - 1] dp[i][j]=dp[i+1][j1]

③初始化:

循环内部会直接对长度为1的区间直接修改为状态为true

④填表顺序:

最外层:字符串的长度从短到长

内部:i,也就是起始位置从左到右即可

⑤返回值:

在循环的过程中, d p [ i ] [ j ] dp[i][j] dp[i][j]为真的话就更新当前的 r e s = l e n + 1 res = len + 1 res=len+1;

最后返回res即可

代码

int getLongestPalindrome(string A) {int n = A.size();int res = 0;vector<vector<bool>> dp(n, vector<bool>(n, false));for(int len = 0; len < n; ++len){for(int i = 0; i < n - len; ++i){int j = i + len;if(A[i] == A[j]){if(len <= 1){dp[i][j] = true;}else {dp[i][j] = dp[i + 1][j - 1];}if(dp[i][j]){res = len + 1;}}}}return res;}

复杂度

时间复杂度: O ( N 2 ) O(N ^ 2) O(N2),首先枚举从0到n - 1 的长度的字符串

空间复杂度: O ( N 2 ) O(N^2) O(N2),利用了额外的dp数组,来存储对应的状态

相关文章:

牛客热题:最长回文子串

&#x1f4df;作者主页&#xff1a;慢热的陕西人 &#x1f334;专栏链接&#xff1a;力扣刷题日记 &#x1f4e3;欢迎各位大佬&#x1f44d;点赞&#x1f525;关注&#x1f693;收藏&#xff0c;&#x1f349;留言 文章目录 牛客热题&#xff1a;最长回文子串题目链接方法一&am…...

如何访问寄存器

标题 方式一&#xff1a;对地址进行宏定义方式二&#xff1a;用结构体封装寄存器 访问寄存器是CPU执行程序的基础&#xff0c;每种CPU架构都有其特定的寄存器集合和访问方式。 方式一&#xff1a;对地址进行宏定义 #define GPIOA_BASE ((unsigned int)0x48000000) #define GPI…...

苍穹外卖笔记-18-修改密码、bug记录

文章目录 1 修改密码1.1 需求分析和设计1.2 代码实现1.2.1 admin/EmployeeController1.2.2 EmployeeService1.2.3 EmployeeServiceImpl 1.3 功能测试 2 bug记录 1 修改密码 完结的时候发现还有一个接口未实现。这里补充 1.1 需求分析和设计 产品原型&#xff1a; 业务规则&am…...

java如何截取字符串

如果想在一个字符串中截取一段字符&#xff0c;形成新的字符&#xff0c;那么在java中途需要用到substring语句 substring的语法格式是 str.substring(beginindex,endindex) 其中str是字符串 beginindex是起始索引&#xff0c;endindex是结束索引 截取的字符串包含起始索引…...

虚拟淘宝-Virtual-Taobao论文解读(AAAI2019)

目录 1 论文简介 2 文章的主要贡献 3 文章技术的简要说明 4 技术的详细说明 4.1 GAN-SD&#xff1a;生成客户特征 4.2 MAIL&#xff1a;生成交互过程 4.3 ANC&#xff1a;动规范约束 5 实验设定及结果 6 结论 7 参考 1 论文简介 南京大学LAMDA团队的侍竞成、俞扬等…...

低代码组件扩展方案在复杂业务场景下的设计与实践

组件是爱速搭的前端页面可视化模块的核心能力之一&#xff0c;它将前端研发人员从无休止的页面样式微调和分辨率兼容工作中解放了出来。 目前&#xff0c;爱速搭通过内置的上百种功能组件&#xff08;120&#xff09;&#xff0c;基本可以覆盖大部分中后台页面的可视化设计场景…...

震撼科技界的GPT-4o发布首日即遭“越狱破防”

前言 本文主要解读分析OpenAI最新推出的大型模型GPT-4o可能存在的越狱风险。 5 月14 日凌晨的科技圈再一次被OpenAI轰动&#xff0c;其发布的最新大模型GPT-4o&#xff0c;能力横跨语音、文本和视觉&#xff0c;这一成果无疑再次巩固了OpenAI在人工智能领域的领先地位。 然而…...

保护密码安全,探讨密码加盐及其在Go语言中的实现

介绍 在当今数字化时代&#xff0c;个人隐私和数据安全成为了人们关注的焦点之一。随着网络犯罪的不断增加&#xff0c;用户的密码安全性变得尤为重要。密码加盐作为一种常见的安全措施&#xff0c;被广泛应用于密码存储和认证系统中。本文将深入探讨密码加盐的概念、重要性以…...

Sqoop学习详细介绍!!

一、Sqoop介绍 Sqoop是一款开源的工具&#xff0c;主要用于在Hadoop(HDFS/Hive/HBase)与传统的数据库(mysql、postgresql...)间进行数据的传递&#xff0c;可以将一个关系型数据库&#xff08;例如 &#xff1a; MySQL ,Oracle ,Postgres等&#xff09;中的数据导进到Hadoop的H…...

【2024最新华为OD-C/D卷试题汇总】[支持在线评测] 生成哈夫曼树(100分) - 三语言AC题解(Python/Java/Cpp)

🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解 💻 ACM银牌🥈| 多次AK大厂笔试 | 编程一对一辅导 👏 感谢大家的订阅➕ 和 喜欢💗 📎在线评测链接 生成哈夫曼树(100分) 🌍 评测功能需要订阅专栏后私信联系清…...

ctfshow web 单身杯

web签到 <?phperror_reporting(0); highlight_file(__FILE__);$file $_POST[file];if(isset($file)){if(strrev($file)$file){ //翻转函数include $file;}}要进行反转并且包含文件用data协议 自己写不好写可以用函数帮你翻转 <?php $adata:text/plain,<?eval(…...

天锐绿盾加密软件,它的适用范围是什么?

天锐绿盾数据防泄密软件的适用范围广泛&#xff0c;主要可以归纳为以下几点&#xff1a; 行业适用性&#xff1a; 适用于各个行业&#xff0c;包括但不限于制造业、设计行业、软件开发、金融服务等&#xff0c;特别是对数据安全性要求较高的行业。企业规模与类型&#xff1a; 适…...

mysql面试题 Day2

1 长文本如何存储&#xff1f; 可以使用Text存储 TINYTEXT(255长度) TEXT(65535) MEDIUMTEXT&#xff08;int最大值16M&#xff09; LONGTEXT(long最大值4G) 2 大段文本存储如何设计表结构&#xff1f; 分表存储 分表后多段存储 3 大段文本查找时如何建立索引&#xff1…...

Excel加密怎么设置?这5个方法不容错过!(2024总结)

Excel加密怎么设置&#xff1f;如何不让别人未经允许查看我的excel文件&#xff1f;如果您也有这些疑问&#xff0c;那么千万不要错过本篇文章了。今天小编将向大家分享excel加密的5个简单方法&#xff0c;保证任何人都可以轻松掌握&#xff01;毫无疑问的是&#xff0c;为Exce…...

2024年下一个风口是什么?萤领优选 轻资产创业项目全国诚招合伙人

2024年&#xff0c;全球经济与科技发展的步伐不断加快&#xff0c;各行各业都在探寻新的增长点与风口。在这样的时代背景下&#xff0c;萤领优选作为一个轻资产创业项目&#xff0c;正以其独特的商业模式和前瞻的市场洞察力&#xff0c;吸引着众多创业者的目光。(领取&#xff…...

Redis 网络模型

一、用户空间和内核空间 1.1 linux 简介 服务器大多采用 Linux 系统&#xff0c;这里我们以 Linux 为例来讲解&#xff0c;下面有两个不同的 linux 发行版&#xff0c;分别位 ubuntu 和 centos&#xff0c;其实发行版就是在 Linux 系统上包了一层壳。 任何 Linux 发行版&#…...

【设计模式之组合模式 -- C++】

组合模式 – 树状结构&#xff0c;递归遍历 组合模式(Composite Pattern)是一种结构型设计模式&#xff0c;它可以让你将对象组合成树形结构&#xff0c;并且能像使用独立对象一样使用它们。这种模式定义了包含人和组的类&#xff0c;每个类都有可以在树形结构中显示的方法。这…...

C# 通过Win32API设置客户端系统时间

在日常工作中&#xff0c;有时可能会需要获取或修改客户端电脑的系统时间&#xff0c;比如软件设置了Licence有效期&#xff0c;预计2024-06-01 00:00:00到期&#xff0c;如果客户手动修改了客户端电脑时间&#xff0c;往前调整了一年&#xff0c;则软件就可以继续使用一年&…...

VirtualHere 允许通过网络远程使用 USB 设备,就像本地连接一样!

传统上&#xff0c;USB 设备需要直接插入计算机才能使用。有了 VirtualHere&#xff0c;就不再需要这样做&#xff0c;网络本身就变成了传输 USB 信号的电缆&#xff08;也称为 USB over IP、USB/IP、USB over WiFi、USB over Ethernet、USB 设备服务器&#xff09;。 此 USB …...

【Kubernetes】k8s 自动伸缩机制—— HPA 部署

一、在K8s中扩缩容分为两种&#xff1a; ●Node层面&#xff1a;对K8s物理节点扩容和缩容&#xff0c;根据业务规模实现物理节点自动扩缩容 ●Pod层面&#xff1a;我们一般会使用Deployment中的Replicas参数&#xff0c;设置多个副本集来保证服务的高可用&#xff0c;但是这是…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...