牛客热题:最长回文子串
📟作者主页:慢热的陕西人
🌴专栏链接:力扣刷题日记
📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言
文章目录
- 牛客热题:最长回文子串
- 题目链接
- 方法一:动态规划
- 思路
- 代码
- 复杂度
牛客热题:最长回文子串
题目链接
最长回文子串_牛客题霸_牛客网 (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参数,设置多个副本集来保证服务的高可用,但是这是…...
MT1415 大小相同
题目 给定一个由N(<10)个正整数组成的数组A,生成一些最小元素和最大元素相同的子数组数(可以仅包含1个元素),统计这些子数组的数量并输出。 注:最大元素和最小元素相同就是数组中的元素全部为同一个值。如数组&am…...
使用python库moviepy完成视频剪辑
1.关于moviepy和原理 moviepy事github上面的一个开源项目,地址是:GitHub - Zulko/moviepy: Video editing with Python 官方文档地址: User Guide — MoviePy 1.0.2 documentation 中文版文档可参考: MoviePy中文手册 — mov…...
Java高手的30k之路|面试宝典|精通泛型
泛型 知识点 在Java高级开发中,掌握泛型(Generics)是非常重要的,它是Java语言中的一项重要特性,提供了编译时类型安全检查机制,使得代码更加灵活和可重用。以下是Java高级开发需要掌握的泛型知识点&#…...
清理Linux操作系统buff/cache缓存
清理Linux操作系统buff/cache缓存 清理页缓存 echo 1 > /proc/sys/vm/drop_caches 或者 sysctl -w vm.drop_caches1 清理目录项和inode缓存 echo 2 > /proc/sys/vm/drop_caches 或者 sysctl -w vm.drop_caches2 同时清理页缓存、目录项和inode缓存 echo 3 > /pr…...
接口测试的几种方法
其实无论用那种测试方法,接口测试的原理是通过测试程序模拟客户端向服务器发送请求报文,服务器接收请求报文后对相应的报文做出处理然后再把应答报文发送给客户端,客户端接收应答报文这一个过程。 方法一、用LoadRunner实现接口测试 大家都…...
OpenGL3.3_C++_Windows(3)
GLSL Shader基础 Shader(把输入转化为输出,运行在GPU上):首先要声明版本,有各自的入口点main()顶点数据上限:16个包含4分量:16 * 4 64个分量向量:容器vec。使用.x、.y、.z和.w&am…...
24执业药师报名时间汇总及报名流程!
24执业药师报名时间汇总!报名流程! 🕛️各省市报名时间汇总(共9地) 西藏:6月29日-7月8日 新疆:6月25日10:30-7月9日19:00 内蒙古:6月20日9:00-7月3日24:00 新疆兵团:6月2…...
成都跃享未来教育咨询解锁新篇章
在快节奏的现代社会中,每个人都在追求着属于自己的非凡人生。而成都跃享未来教育咨询,正是那个能够智慧引领你走向成功、成就非凡人生的灯塔。 跃享未来教育咨询,位于历史悠久的文化名城成都,这里不仅有丰富的文化底蕴,…...
怎么把网页上的接口信息导入postman
第一步 打开f12,右键选中需要的接口。选择copy-copy as cURL 第二步 打开postman,选择"Raw Text", 把刚才复制的curl粘贴到空白位置,点击Continue - 最后的效果。导入的接口自带cookie,不用再输入cookie&a…...
10KM无人机高清图传通信模组,低延迟、抗干扰,飞睿智能无线MESH组网模块
随着科技的飞速发展,无人机技术在各个领域的应用越来越广泛。尤其在海上监测、搜索救援、货物运输等场景中,无人机的应用显得尤为重要。然而,要实现无人机在复杂海域环境中的高效通信,高清图传通信模组的作用不可忽视。本文将深入…...
网站开发模式分为/长春seo网站排名
06-9-27在网吧里,任何时间都会有人在吃饭,有人在睡觉,有人在玩。不论是清晨,中午,还是深夜,都有一些人挺不住了,他们用疲惫无神的双眼仔细注视着屏幕,仿佛创作中的马克思。他们是铁人…...
郴州建设工程信息网站/免费发链接的网站
在本地部署 Web 应用时我有遇到过某网络端口已经被其他程序占用的情况,这时候就需要先退出占用该端口的进程,我们可以通过“终端”来实现结束占用某特定端口的进程 1、打开终端,使用如下命令: lsof -i:**** 以上命令中,…...
青州住房建设局网站/互动营销名词解释
MySQL下mysql.sock丢失丢失的原因一般是因为配置文件不一致的原因,mysqld 错误启动,mysqld_safe 会清除一次mysql.sock 。解决方法是: 判断一般人解决故障时没有切换到mysql用户,造成权限有问题,无法创建mysql授权表&a…...
学校网站建设重要性/seo学习网站
早晨起床时间:6:10 晚上休息时间:23:31 全天处理事件:1.收尾电子时钟软件程序版本2.0。 处事经验总结:暂无。 人生感悟:性格决定行为。 其它:这段时间还是感觉比较迷茫,在社会上经历一段时间后&…...
网站搜索排名靠前/1688网站
第一种 long activityId Long.valueOf((String) activity.get("activityId")); 第二种 long activityId (long) activity.get("activityId");...
大连网龙建站优化推广/网络舆情监测系统软件
更多代码请见:https://github.com/xubo245 基因数据处理系列 1.解释 重新运行,跟换了文件地址 后来终端,需要运行其他的2.代码: hadoopMaster:~/disk2/xubo/project/alignment/sparkBWA$ vi sparkBWA.sh for j in 10000 10000…...