当前位置: 首页 > 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;但是这是…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.

ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #&#xff1a…...