牛客热题:最长回文子串

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

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

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

在这里插入图片描述

文章目录

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

牛客热题:最长回文子串

题目链接

最长回文子串_牛客题霸_牛客网 (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数组,来存储对应的状态

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/352188.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

大模型Claude 3产品调研

一、公司与产品介绍 Anthropic公司&#xff0c;由前OpenAI高级成员达里奥阿莫代&#xff08;Dario Amodei&#xff09;和丹妮拉阿莫代&#xff08;Daniela Amodei&#xff09;兄妹于2021年创立&#xff0c;致力于开发先进的人工智能技术。作为公司的旗舰产品&#xff0c;Claud…

JavaEE进阶----SpringBoot快速入门

文章目录 前言一、了解Maven1.1 Maven功能- 项⽬构建- 管理依赖 1.2Maven仓库 二、第一个SpringBoot项目总结 前言 Spring Boot是一个用于构建快速、简单和可扩展的生产级应用程序的框架。它基于Spring框架&#xff0c;提供了开发微服务和独立的应用程序所需的一切。 一、了解…

学生党打工人救星,GPT一句话生成精美PPT

学生党打工人救星&#xff0c;GPT一句话生成精美PPT 介绍 在这个快节奏的现代社会&#xff0c;效率是关键。无论是工作会议、学术报告&#xff0c;还是产品展示&#xff0c;一个精美而结构合理的 PPT 都是成功的关键。然而&#xff0c;制作一个高质量的 PPT 往往需要耗费大量…

气体传感器的工作原理探究

气体传感器的工作原理主要基于其内部的感应元件与目标气体之间的相互作用。不同的气体传感器可能采用不同的工作原理&#xff0c;但其核心目的都是将气体的浓度或成分转化为可测量和处理的电信号。 PID气体传感器 以常见的电化学式气体传感器为例&#xff0c;其工作原理涉及气体…

Euro Efficiency(POJ, Open judge)

题目链接: 1252 -- Euro Efficiency 题目描述: 思路: 题面的大概意思就是给你一组基本面值的钱币&#xff0c;问你要凑出指定的面值最少需要多少个钱币的参与&#xff0c;钱币的参与可以是加法也可以是减法。 分析一下&#xff0c;由于答案与钱币参与的顺序无关&#xff0c;…

【C++入门(3)】函数重载、引用

一、函数重载 1、函数重载概念 函数重载是指在同一作用域中&#xff0c;具有不同形参列表&#xff08;参数的 个数 或 类型 或类型顺序 不同&#xff09;的同名函数。 C语言中不允许同名函数的存在&#xff0c;如果一个程序中有两个函数的函数名完全相同&#xff0c;就会报错…

轻松4步!格式工厂怎么转换mp3教会你

在数字化时代&#xff0c;音频文件格式转换变得越发重要&#xff0c;而格式工厂作为一款强大而多功能的工具&#xff0c;为我们提供了便捷的音频转换解决方案。特别是在将音频文件转换为MP3的需求上&#xff0c;格式工厂以其简便易用的特点备受欢迎。格式工厂怎么转换mp3&#…

坚持刷题|合并有序链表

文章目录 题目思考代码实现迭代递归 扩展实现k个有序链表合并方法一方法二 PriorityQueue基本操作Java示例注意事项 Hello&#xff0c;大家好&#xff0c;我是阿月。坚持刷题&#xff0c;老年痴呆追不上我&#xff0c;消失了一段时间&#xff0c;我又回来刷题啦&#xff0c;今天…

CMake从安装到精通

目录 引言 1. CMake的安装 2. CMake的原理 3. CMake入门 3.1 CMakeLists.txt与注释 3.2 版本指定与工程描述 3.3 生成可执行程序 3.4 定义变量与指定输出路径 3.5 指定C标准 3.6 搜索文件 3.7 包含头文件 4. CMake进阶 4.1 生成动静态库 4.2 链接动静态库 4.…

垃圾回收管理系统设计

一、引言 随着城市化进程的加快&#xff0c;垃圾处理问题日益凸显。为了有效管理垃圾回收&#xff0c;提高资源利用效率&#xff0c;降低环境污染&#xff0c;本文设计了一套垃圾回收管理系统。该系统涵盖了数据收集与分析、智能监测与识别、资源调配与协调、用户参与与反馈、…

Golang | Leetcode Golang题解之第149题直线上最多的点数

题目&#xff1a; 题解&#xff1a; func maxPoints(points [][]int) (ans int) {n : len(points)if n < 2 {return n}for i, p : range points {if ans > n-i || ans > n/2 {break}cnt : map[int]int{}for _, q : range points[i1:] {x, y : p[0]-q[0], p[1]-q[1]if…

探索AI绘画工具的前沿:创新科技与艺术的无缝融合

在科技和艺术交织的时代&#xff0c;AI绘画工具以其独特的魅力引领着创作的新潮流。本文将带您深入了解AI绘画工具的前沿技术&#xff0c;并通过最新例子展示其实际应用和潜力。 AI绘画工具概述 AI绘画工具通过集成深度学习、自然语言处理等技术&#xff0c;实现了从文字描述…

关于从大平台跳转各个应用,更新应用前端包后,显示的仍是旧的内容,刷新应用页面后方才显示新的内容的问题的排查和解决

我们从绿洲物联平台跳转智能锁应用&#xff0c; 如下&#xff0c;我们可以看到&#xff0c;我们是通过a标签去跳转应用的。但是我们打开控制台的话&#xff0c;因为a标签是另外新开一个页面&#xff0c;我们看不到新页面的html文档的加载情况。 我们可以临时把_blank改成_sel…

Perl 语言入门学习

一、介绍 Perl 是一种高级的、动态的、解释型的通用编程语言&#xff0c;由Larry Wall于1987年开发。它是一种非常灵活和强大的语言&#xff0c;广泛用于文本处理、系统管理、网络编程、图形编程等领域。 Perl 语言的设计理念是“用一种简单的语法&#xff0c;去解决复杂的编…

Elixir学习笔记——Erlang 库

Elixir 提供了与 Erlang 库的出色互操作性。事实上&#xff0c;Elixir 不鼓励简单地包装 Erlang 库&#xff0c;而是直接与 Erlang 代码交互。在本节中&#xff0c;我们将介绍一些 Elixir 中没有的最常见和最有用的 Erlang 功能。 Erlang 模块的命名约定与 Elixir 不同&#x…

【C++高阶】掌握C++多态:探索代码的动态之美

&#x1f4dd;个人主页&#x1f339;&#xff1a;Eternity._ ⏩收录专栏⏪&#xff1a;C “ 登神长阶 ” &#x1f921;往期回顾&#x1f921;&#xff1a;C继承 &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; ❀继承 &#x1f4d2;1. 多态的定义及实现&…

你好,Jetpack Compose

文章目录 为什么选 Jetpack Compose先决条件新建项目新建虚拟设备运行项目 为什么选 Jetpack Compose Jetpack Compose 是 Android 开发最新的、现代化的 UI 框架开发者几乎只需要使用 Kotlin 一门语言即可完成 App 开发&#xff08;Java 是基础&#xff0c;有些源码是 Java 写…

六西格玛助力便携式产品功耗大降:打造绿色节能新标杆!

随着功能的日益强大&#xff0c;便携式电子产品的功耗问题也日益凸显&#xff0c;成为制约产品性能提升和用户体验改善的关键因素。为了应对这一挑战&#xff0c;越来越多的企业开始探索应用六西格玛方法来降低便携式产品的功耗&#xff0c;实现绿色节能的目标。 六西格玛是一…

Allegro光绘Gerber文件、IPC网表、坐标文件、装配PDF文件导出打包

Allegro光绘Gerber文件、IPC网表、坐标文件、装配PDF文件导出打包 一、Gerber文件层叠与参数设置二、装配图文件设置导出三、光绘参数设置四、Gerber孔符图、钻孔表及钻孔文件输出五、输出Gerber文件六、输出IPC网表七、导出坐标文件八、文件打包 一、Gerber文件层叠与参数设置…

12. Django 第三方功能应用

12. 第三方功能应用 因为Django具有很强的可扩展性, 所以延伸了第三方功能应用. 通过本章的学习, 读者能够在网站开发过程中快速实现API接口开发, 验证码生成与使用, 站内搜索引擎, 第三方网站实现用户注册, 异步任务和定时任务, 即时通信等功能.12.1 Django Rest Framework框…