「优选算法刷题」:最长回文子串
一、题目
给你一个字符串 s,找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。
示例 1:
输入:s = "babad" 输出:"bab" 解释:"aba" 同样是符合题意的答案。
示例 2:
输入:s = "cbbd" 输出:"bb"
二、思路解析
这道题我看到一位大佬的题解很是巧妙,利用的是回文串的一个性质。
对于⼀个⼦串⽽⾔,如果它是回⽂串,并且⻓度⼤于 2,那么将它⾸尾的两个字⺟去除之后,它仍然是个回⽂串。如此这样去除,⼀直除到⻓度⼩于等于 2 时呢?⻓度为 1 的,⾃⾝与⾃⾝就构成回⽂;
⽽⻓度为 2 的,就要判断这两个字符是否相等了。
从这个性质可以反推出来,从回⽂串的中⼼开始,往左读和往右读也是⼀样的。那么,是否可以枚举回⽂串的中⼼呢?
从中⼼向两边扩展,如果两边的字⺟相同,我们就可以继续扩展;如果不同,我们就停⽌扩展。这样,只需要⼀层 for 循环,我们就可以完成先前两层 for 循环的⼯作量。
三、完整代码
class Solution {public String longestPalindrome(String s) {int begin = 0;int n = s.length();int len = 0;for(int i = 0;i < n; i++){int left = i;int right = i;while(left >= 0 && right < n && s.charAt(left) == s.charAt(right)){left--;right++;}if(right - left - 1 > len){begin = left + 1;len = right - left - 1;}left = i;right = i + 1;while(left >= 0 && right < n && s.charAt(left) == s.charAt(right)){left--;right++;}if(right - left - 1 > len){begin = left + 1;len = right - left - 1;} }return s.substring(begin, begin + len);}
}
以上就是本篇博客的全部内容啦,如有不足之处,还请各位指出,期待能和各位一起进步!
相关文章:
「优选算法刷题」:最长回文子串
一、题目 给你一个字符串 s,找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。 示例 1: 输入:s "babad" 输出:"bab" 解释:"aba"…...
Java项目:41 springboot大学生入学审核系统的设计与实现010
作者主页:舒克日记 简介:Java领域优质创作者、Java项目、学习资料、技术互助 文中获取源码 项目介绍 本大学生入学审核系统管理员和学生。 管理员功能有个人中心,学生管理,学籍信息管理,入学办理管理等。 学生功能有…...
【数据结构与算法】常见排序算法(Sorting Algorithm)
文章目录 相关概念1. 冒泡排序(Bubble Sort)2. 直接插入排序(Insertion Sort)3. 希尔排序(Shell Sort)4. 直接选择排序(Selection Sort)5. 堆排序(Heap Sort)…...
Unity3D学习之XLua实践——背包系统
文章目录 1 前言2 新建工程导入必要资源2.1 AB包设置2.2 C# 脚本2.3 VSCode 的环境搭建 3 面板拼凑3.1 主面板拼凑3.2 背包面板拼凑3.3 格子复合组件拼凑3.4 常用类别名准备3.5 数据准备3.5.1 图集准备3.5.2 json3.5.3 打AB包 4 Lua读取json表及准备玩家数据5 主面板逻辑6 背包…...
前端技术研究越深入,越觉得技术不是决定录用唯一条件。
一、拒绝抬杠 我说技能不是唯一条件,不是说技能不重要,招聘前端条件是1X,其中1是技能,X是其他条件。 如果X条件很优秀,1这个条件可以降格为0.8、0.5,甚至更低。 有人就抬杠,那为啥不招聘清洁工来干前端&…...
vue组件的重新渲染的问题
目录 1.方式1 2.方式2 1.方式1 修改组件上的key属性 Vue是通过diffing算法比较虚拟DOM和真实DOM,来判断新旧 DOM 的变化。key是虚拟DOM对象的标识,在更新显示时key表示着DOM的唯一性。 DOM是否变化的核心是通过判断新旧DOM的key值是否变化,…...
opengl 学习(二)-----你好,三角形
你好,三角形 分类demo效果解析 分类 opengl c demo #include "glad/glad.h" #include "glfw3.h" #include <iostream> #include <cmath> #include <vector>using namespace std;/** * 在学习此节之前,建议将这…...
mongodb4.2升级到5.0版本,升级到6.0版本, 升级到7.0版本案例
今天一客户想把自己当前使用的mongodb数据库4.2版本升级到7.0版本。难道mongodb能直接跳跃升级吗? 经过几经查找资料,貌似真不行呀。确定升级流程如下: 还得从mongo4.2升级到5.0。其次再从5.0升级到6.0。最后再从6.0升级到7.0。 开始升级之前将数据进行备份 这一步…...
CPU处理器模式与异常
ARM架构中的Exception Level(EL) 在ARM架构中,Exception Level(EL)是一个关键概念,它表示了处理器当前处理异常或中断的层次。ARMv8-A架构定义了四个Exception Levels:EL0、EL1、EL2和EL3&…...
Day 53 |● 1143.最长公共子序列 ● 1035.不相交的线 ● 53. 最大子序和
1143.最长公共子序列 class Solution { public:int longestCommonSubsequence(string text1, string text2) {vector<vector<int>> dp(text1.size()1,vector<int>(text2.size()1,0));int res 0;for(int i 1; i < text1.size(); i){for(int j 1; j <…...
ant-desgin charts双轴图DualAxes,柱状图无法立即显示,并且只有在调整页面大小(放大或缩小)后才开始显示
摘要 双轴图表中,柱状图无法立即显示,并且只有在调整页面大小(放大或缩小)后才开始显示 官方示例代码 在直接复制,替换为个人数据时,出现柱状图无法显示问题 const config {data: [data, data],xFiel…...
获取别人店铺的所有商品API接口
使用淘宝淘口令接口的步骤通常包括: 注册成为淘宝开放平台的开发者:在淘宝开放平台网站上注册账号并完成认证。 创建应用以获取API密钥:在您的开发者控制台中创建一个应用,并获取用于API调用的密钥,如Client ID和Clie…...
成都正信:亲戚借了钱一直不还怎么委婉的说
在中国传统文化中,亲情关系往往被视为最为重要和敏感的部分。当亲戚间发生借贷时,若出现拖欠不还的情形,处理起来尤为棘手。面对这样的尴尬局面,采取委婉而有效的沟通方式至关重要。 张华最近就遇到了这样的困扰。他的表弟去年因急…...
Truenas入门级教程
Truenas入门教程 前言:系统相关配置 采用I3 4160,采用了2块500G的硬盘,内存为8G,两个网卡只用了其中一个,系统安装的是core版本 硬件采用DELL3020MT机箱,自带3个SATA网口,后期网口不够&#…...
窗口函数dense() over(条件)
力扣题目连接 https://leetcode.cn/problems/rank-scores/ 在 SQL 中,DENSE_RANK() 是一个窗口函数,用于计算结果集中每行的稠密排名(dense rank)。DENSE_RANK() 函数会为具有相同排序字段值的行分配相同的排名,但不会…...
蓝牙APP开发实现汽车遥控钥匙解锁汽车智能时代
在现代社会,随着科技的不断发展,汽车已经不再是简单的交通工具,而是与智能科技紧密相连的载体。其中,通过开发APP蓝牙程序实现汽车遥控钥匙成为了一种趋势,为车主带来了便捷与安全的体验。虎克技术公司作为行业领先者&…...
第三天 Kubernetes进阶实践
第三天 Kubernetes进阶实践 本章介绍Kubernetes的进阶内容,包含Kubernetes集群调度、CNI插件、认证授权安全体系、分布式存储的对接、Helm的使用等,让学员可以更加深入的学习Kubernetes的核心内容。 ETCD数据的访问 kube-scheduler调度策略实践 预选与…...
redis小结
1.mysql是数据库,redis是数据库,那么什么时候使用应该使用哪种数据库? redis做缓存是为了缓解mysql的压力,在数据库表数据量上千万,并且访问频繁时,mysql压力增大,在有索引的情况下依旧效果不佳,需要使用…...
PHP伪协议详解
PHP伪协议详解 一、前言1.什么是PHP伪协议?2.什么时候用PHP伪协议? 二、常见的php伪协议php://inputphp://filterzip://与bzip2://与zlib://协议data://phar:// 一、前言 1.什么是PHP伪协议? PHP伪协议是PHP自己支持的一种协议与封装协议,…...
进程:守护进程
一、守护进程的概念 守护进程是脱离于终端控制,且运行在后端的进程。(孤儿进程)守护进程不会将信息显示在任何终端上影响前端的操作,也不会被终端产生的任何信息打断,例如(ctrlc).守护进程独立…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解
JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用,结合SQLite数据库实现联系人管理功能,并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能,同时可以最小化到系统…...
STM32---外部32.768K晶振(LSE)无法起振问题
晶振是否起振主要就检查两个1、晶振与MCU是否兼容;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容(CL)与匹配电容(CL1、CL2)的关系 2. 如何选择 CL1 和 CL…...
spring Security对RBAC及其ABAC的支持使用
RBAC (基于角色的访问控制) RBAC (Role-Based Access Control) 是 Spring Security 中最常用的权限模型,它将权限分配给角色,再将角色分配给用户。 RBAC 核心实现 1. 数据库设计 users roles permissions ------- ------…...
Visual Studio Code 扩展
Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后,命令 changeCase.commands 可预览转换效果 EmmyLua…...
工厂方法模式和抽象工厂方法模式的battle
1.案例直接上手 在这个案例里面,我们会实现这个普通的工厂方法,并且对比这个普通工厂方法和我们直接创建对象的差别在哪里,为什么需要一个工厂: 下面的这个是我们的这个案例里面涉及到的接口和对应的实现类: 两个发…...
职坐标物联网全栈开发全流程解析
物联网全栈开发涵盖从物理设备到上层应用的完整技术链路,其核心流程可归纳为四大模块:感知层数据采集、网络层协议交互、平台层资源管理及应用层功能实现。每个模块的技术选型与实现方式直接影响系统性能与扩展性,例如传感器选型需平衡精度与…...
PLC入门【4】基本指令2(SET RST)
04 基本指令2 PLC编程第四课基本指令(2) 1、运用上接课所学的基本指令完成个简单的实例编程。 2、学习SET--置位指令 3、RST--复位指令 打开软件(FX-TRN-BEG-C),从 文件 - 主画面,“B: 让我们学习基本的”- “B-3.控制优先程序”。 点击“梯形图编辑”…...
Qt/C++学习系列之列表使用记录
Qt/C学习系列之列表使用记录 前言列表的初始化界面初始化设置名称获取简单设置 单元格存储总结 前言 列表的使用主要基于QTableWidget控件,同步使用QTableWidgetItem进行单元格的设置,最后可以使用QAxObject进行单元格的数据读出将数据进行存储。接下来…...
可视化预警系统:如何实现生产风险的实时监控?
在生产环境中,风险无处不在,而传统的监控方式往往只能事后补救,难以做到提前预警。但如今,可视化预警系统正在改变这一切!它能够实时收集和分析生产数据,通过直观的图表和警报,让管理者第一时间…...
