牛客热题:最长回文子串
📟作者主页:慢热的陕西人
🌴专栏链接:力扣刷题日记
📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言

文章目录
- 牛客热题:最长回文子串
- 题目链接
- 方法一:动态规划
- 思路
- 代码
- 复杂度
牛客热题:最长回文子串
题目链接
最长回文子串_牛客题霸_牛客网 (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][j−1]
③初始化:
循环内部会直接对长度为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数组,来存储对应的状态
相关文章:
牛客热题:最长回文子串
📟作者主页:慢热的陕西人 🌴专栏链接:力扣刷题日记 📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言 文章目录 牛客热题:最长回文子串题目链接方法一&am…...
如何访问寄存器
标题 方式一:对地址进行宏定义方式二:用结构体封装寄存器 访问寄存器是CPU执行程序的基础,每种CPU架构都有其特定的寄存器集合和访问方式。 方式一:对地址进行宏定义 #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 需求分析和设计 产品原型: 业务规则&am…...
java如何截取字符串
如果想在一个字符串中截取一段字符,形成新的字符,那么在java中途需要用到substring语句 substring的语法格式是 str.substring(beginindex,endindex) 其中str是字符串 beginindex是起始索引,endindex是结束索引 截取的字符串包含起始索引…...
虚拟淘宝-Virtual-Taobao论文解读(AAAI2019)
目录 1 论文简介 2 文章的主要贡献 3 文章技术的简要说明 4 技术的详细说明 4.1 GAN-SD:生成客户特征 4.2 MAIL:生成交互过程 4.3 ANC:动规范约束 5 实验设定及结果 6 结论 7 参考 1 论文简介 南京大学LAMDA团队的侍竞成、俞扬等…...
低代码组件扩展方案在复杂业务场景下的设计与实践
组件是爱速搭的前端页面可视化模块的核心能力之一,它将前端研发人员从无休止的页面样式微调和分辨率兼容工作中解放了出来。 目前,爱速搭通过内置的上百种功能组件(120),基本可以覆盖大部分中后台页面的可视化设计场景…...
震撼科技界的GPT-4o发布首日即遭“越狱破防”
前言 本文主要解读分析OpenAI最新推出的大型模型GPT-4o可能存在的越狱风险。 5 月14 日凌晨的科技圈再一次被OpenAI轰动,其发布的最新大模型GPT-4o,能力横跨语音、文本和视觉,这一成果无疑再次巩固了OpenAI在人工智能领域的领先地位。 然而…...
保护密码安全,探讨密码加盐及其在Go语言中的实现
介绍 在当今数字化时代,个人隐私和数据安全成为了人们关注的焦点之一。随着网络犯罪的不断增加,用户的密码安全性变得尤为重要。密码加盐作为一种常见的安全措施,被广泛应用于密码存储和认证系统中。本文将深入探讨密码加盐的概念、重要性以…...
Sqoop学习详细介绍!!
一、Sqoop介绍 Sqoop是一款开源的工具,主要用于在Hadoop(HDFS/Hive/HBase)与传统的数据库(mysql、postgresql...)间进行数据的传递,可以将一个关系型数据库(例如 : MySQL ,Oracle ,Postgres等)中的数据导进到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(…...
天锐绿盾加密软件,它的适用范围是什么?
天锐绿盾数据防泄密软件的适用范围广泛,主要可以归纳为以下几点: 行业适用性: 适用于各个行业,包括但不限于制造业、设计行业、软件开发、金融服务等,特别是对数据安全性要求较高的行业。企业规模与类型: 适…...
mysql面试题 Day2
1 长文本如何存储? 可以使用Text存储 TINYTEXT(255长度) TEXT(65535) MEDIUMTEXT(int最大值16M) LONGTEXT(long最大值4G) 2 大段文本存储如何设计表结构? 分表存储 分表后多段存储 3 大段文本查找时如何建立索引࿱…...
Excel加密怎么设置?这5个方法不容错过!(2024总结)
Excel加密怎么设置?如何不让别人未经允许查看我的excel文件?如果您也有这些疑问,那么千万不要错过本篇文章了。今天小编将向大家分享excel加密的5个简单方法,保证任何人都可以轻松掌握!毫无疑问的是,为Exce…...
2024年下一个风口是什么?萤领优选 轻资产创业项目全国诚招合伙人
2024年,全球经济与科技发展的步伐不断加快,各行各业都在探寻新的增长点与风口。在这样的时代背景下,萤领优选作为一个轻资产创业项目,正以其独特的商业模式和前瞻的市场洞察力,吸引着众多创业者的目光。(领取ÿ…...
Redis 网络模型
一、用户空间和内核空间 1.1 linux 简介 服务器大多采用 Linux 系统,这里我们以 Linux 为例来讲解,下面有两个不同的 linux 发行版,分别位 ubuntu 和 centos,其实发行版就是在 Linux 系统上包了一层壳。 任何 Linux 发行版&#…...
【设计模式之组合模式 -- C++】
组合模式 – 树状结构,递归遍历 组合模式(Composite Pattern)是一种结构型设计模式,它可以让你将对象组合成树形结构,并且能像使用独立对象一样使用它们。这种模式定义了包含人和组的类,每个类都有可以在树形结构中显示的方法。这…...
C# 通过Win32API设置客户端系统时间
在日常工作中,有时可能会需要获取或修改客户端电脑的系统时间,比如软件设置了Licence有效期,预计2024-06-01 00:00:00到期,如果客户手动修改了客户端电脑时间,往前调整了一年,则软件就可以继续使用一年&…...
VirtualHere 允许通过网络远程使用 USB 设备,就像本地连接一样!
传统上,USB 设备需要直接插入计算机才能使用。有了 VirtualHere,就不再需要这样做,网络本身就变成了传输 USB 信号的电缆(也称为 USB over IP、USB/IP、USB over WiFi、USB over Ethernet、USB 设备服务器)。 此 USB …...
【Kubernetes】k8s 自动伸缩机制—— HPA 部署
一、在K8s中扩缩容分为两种: ●Node层面:对K8s物理节点扩容和缩容,根据业务规模实现物理节点自动扩缩容 ●Pod层面:我们一般会使用Deployment中的Replicas参数,设置多个副本集来保证服务的高可用,但是这是…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...
深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖
在前面的练习中,每个页面需要使用ref,onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入,需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...
iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版分享
平时用 iPhone 的时候,难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵,或者买了二手 iPhone 却被原来的 iCloud 账号锁住,这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...
江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...
