当前位置: 首页 > news >正文

不容易解的题10.10

5.最长回文子串

5. 最长回文子串 - 力扣(LeetCode)icon-default.png?t=N7T8https://leetcode.cn/problems/longest-palindromic-substring/?envType=list&envId=ZCa7r67M给一个字符串,让我们找最长回文子串

这题不用说,回文子串那一定是连续的,第一眼看可能想到滑窗,想法是好想法,但是你如何确定窗口大小?又如何确定窗口什么情况下左窗口怎么运动,又是什么情况右窗口运动呢?为了找全子串不落下答案,那我们应该从第一个位置开始左窗口,那么什么时候左窗口右移动呢?

这实际上就只能使用双for循环来确定此时子串开始终止位置了,然后判断该字串是否回文,如果回文看长度更新答案。没错最开始我就是这样想的,也是这样实现的,但是需要右剪枝,不然容易超时。

class Solution {
public:
bool fun(string&s,int left,int right){while(left<right){if(s[left++]!=s[right--])return false;}return true;
}string longestPalindrome(string s) {if(s.size()==0)return "";string res;res+=s[0];for(int i=0;i<s.size();i++){for(int j=i+1;j<s.size();j++){bool t=fun(s,i,j);if(t){string tmp=s.substr(i,j-i+1);res=tmp.size()>res.size()?tmp:res;}if(j+1==s.size()&&res.size()==j-i+1)return res;}}return res;}
};

剪枝就是如果当前右窗口已经遍历到整个s最后一个位置且res也等于该窗口大小
则直接return因为后面不可能存在更长的回文子串了

怎么样是不是还算有一点技巧,时间消耗非常多,大概200+,而且我也是超时后才想到这个剪枝的,更好的算法我在这里介绍两个,一个是中心探测,一个是马拉车(竞赛算法)。

中心探测是马拉车算法的雏形(基础),也就是说你不会中心探测写不出来马拉车算法,但我个人觉得中心探测就十分的好用了,它可以使时间消耗变得很小了,如果不是在特殊要求时间或性能的前提下,使用中心探测可以更好的更快速的不出错的书写代码。

思路:中心探测法要求以字符串的每个字符作为中心探测的中心点,开始向两边进行试探,判断两边的元素是否对应相等,这里有一个不太容易察觉的问题

一个字符串的长度奇偶性会影响判断的结果,如果长度为奇数那非常好办,以中点左右探测不会出现问题,但如果为偶数不容易确定取拿一个为中心点,我们使用填充字符串的技术,无论给定字符串长度奇偶性如何,都用字符填充使它变成奇数长度。

然后再去比较,代码如下

class Solution {
public:
int fun(const string& s,int left,int right){while(left>=0&&right<s.size()&&s[left]==s[right]){left--,++right;}return (right-left-2)/2;
}string longestPalindrome(string s) {string ss="#";int n=0;int start=0,maxn=0;for(char i:s){ss+=i;ss+='#';}for(int i=0;i<ss.size();++i){int n=fun(ss,i,i);if(maxn<n){maxn=n;start=(i-maxn)/2;}}return s.substr(start,maxn);}
};

这里我们使用#号填充,实际你用一个字符串里肯定不会出现的字符填充就可以不一定非要#。

判断回文和更新答案这里我说一下,直接看可能看不懂。

我们由于扩大了字符串用井号,而且是相当于每个原本字符的左右两边各含有一个#(注:原版是在最后一个字符填写完之后,还要有一个#填充,这里我发现少写一个也能通过),这相当于原本的字符下标扩大1倍,我们使用函数fun来返回当前以该字符为中心回文子串长度,返回结果时候需要-2这是因为left--,right++后我们发现的不回文,返回答案,所以实际应该取的答案比这小2,再就是/2,为什么除2,因为我们的得到的长度是扩大1倍下标的长度/2才是源字符串回文长度

解释完了这个解释里面的更新数据,maxn更新一目了然,然后是start这个是代表源字符串从哪个字符起取回文子串,是当前下标减去回文半径,因为是中心探测法,寻找的回文串,所以当前下标代表的是回文串中心而不是起始位置,所以是减法,然后这里的/2是因为#填充下标扩大1倍,所以/2。然后最后以start为开始,截取长度为maxn。

manacher算法:

class Solution {
public:string longestPalindrome(string s) {string tmp="#";for(char c:s){tmp+=c;tmp+='#';}tmp+='#';vector<int>arr(tmp.size(),0);int start=0,max=0,right=0,center=0;for(int i=0;i<tmp.size();++i){if(i<=right){int minarmlen=min(right-i,arr[2*center-i]);arr[i]=fun(tmp,i-minarmlen,i+minarmlen);}else arr[i]=fun(tmp,i,i);if(arr[i]>max){max=arr[i];start=(i-max)/2;           }if(i+arr[i]>right){center=i;right=i+arr[i];}}return s.substr(start,max);}
private:int fun(string&s,int left,int right){while(left>=0&&right<s.size()&&s[left]==s[right]){--left,++right;}return (right-left-2)/2;}
};

根据代码看讲解:

优化思路:使用一个数组来记录每个位置的以该位置为中心回文子串的最大长度
由于回文串的对称性我们可以找到以center为中心对称的那个位置
而center是随着i不断增大,且只会出现在i的左侧或和i相等
所以当前i的对称位置一定存在,我们根据镜像的那个i位置去查表,即可得知它可以向外扩张几个字符(取决于镜像位置为中心的回文串有多长)
什么时候可以依赖于查表确定跳过几个字符什么时候不可以?
跳过字符的原因是对称位置由于记录了以它为中心最长字串长度,所以遍历到i时如果可以以center为中心找到对称位置,且此时i在以center为中心的最远半径内,即可完成跳转。
即i<=right,我们取i+镜像表最长回文长度与right-i长度取最小,来完成此时的跳跃

跳跃是什么意思?就是left往前越过right往后越过一些字符,这些字符必定回文,不需要再做判断
如果i>center则不能跳跃,因为此时已经不在可预测范围内,center为中心的最长可预测范围就到right,因为最长回文子串以center中心最长到right
center如何确定?
我们往后遍历i在某时出现最长回文子串长度大于当前存储的长度时,把center移到i位置,且以该长度确定right即,当前right最远达哪里。

该思路是我自己总结较为简短的主要注意点,如果不明白可以看看更为完全的解析,我这里只把我认为最重要的几点讲明理解。

 这种思路就是用到回文镜像对称,以已知范围去减少判断回文次数,其他的代码实现就是中心探测法,练多了就明白了。


本期文章只有一道题,因为我发现更新三四道详解的题目会使得篇幅过长,阅读量过低,我试试只更新一道题会不会有所改变。

都看到这里了如果对您有用的话别忘了一键三连哦,如果是互粉回访我也会做的!

大家有什么想看的题解,或者想看的算法专栏、数据结构专栏,可以去看看往期的文章,有想看的新题目或者专栏也可以评论区写出来,讨论一番,本账号将持续更新。
期待您的关注

相关文章:

不容易解的题10.10

5.最长回文子串 5. 最长回文子串 - 力扣&#xff08;LeetCode&#xff09;https://leetcode.cn/problems/longest-palindromic-substring/?envTypelist&envIdZCa7r67M给一个字符串&#xff0c;让我们找最长回文子串 这题不用说&#xff0c;回文子串那一定是连续的&#…...

淘宝天猫店铺所有商品数据接口,淘宝API接口

获取淘宝店铺所有商品数据接口的步骤如下&#xff1a; 获取授权&#xff1a;使用 OAuth 2.0 协议对应用进行授权&#xff0c;以便能够访问店铺的商品信息。获取店铺信息&#xff1a;使用淘宝 API 的 taobao.shop.get 接口&#xff0c;传入店铺的 user_id 参数&#xff0c;获取…...

Prometheus和grafana安装配置手册

1.简介 本文档为prometheus和grafana安装配置手册&#xff0c;prometheus和grafana的内容、和操作过程&#xff0c;详细介绍了服务监控配置、dashboard配置、告警配置等操作。 2.部署说明 Prometheus基于Golang编写&#xff08;需要安装&#xff09;&#xff0c;编译后的软件…...

从零开始探索C语言(十一)----共用体和位域

文章目录 1. 共用体1.1 定义共用体1.2 访问共用体成员 2. 位域2.1 位域声明2.2 位域的定义和位域变量的说明2.3 位域的使用2.4 位域小结 1. 共用体 共用体是一种特殊的数据类型&#xff0c;允许您在相同的内存位置存储不同的数据类型。您可以定义一个带有多成员的共用体&#…...

【数据结构】算法的时间复杂度

&#x1f984;个人主页:修修修也 &#x1f38f;所属专栏:数据结构 ⚙️操作环境:Visual Studio 2022 目录 一.算法时间复杂度定义 二.大O阶渐近表示法 &#x1f38f;大O阶渐近表示法的定义 &#x1f38f;推导大O阶方法 三.常见的时间复杂度 &#x1f4cc;常数阶 &#x…...

Qt作业五

1、思维导图 https://www.zhixi.com/view/9e899ee0 2、作业 #include <iostream>using namespace std;class Animal { private:string name; public:Animal(){}Animal(string n):name(n){}virtual void perform()0; };class Lion:public Animal { public:void perform…...

【面试】pc寄存器题

目录 1.使用pc寄存器存储字节码指令地址有什么作用&#xff1f;&#xff08;为什么使用pc寄存器记录当前线程的执行地址&#xff1f;&#xff09;2.pc寄存器为什么被设定为线程私有的&#xff1f; 1.使用pc寄存器存储字节码指令地址有什么作用&#xff1f;&#xff08;为什么使…...

ARM按键中断实验

设置按键中断&#xff0c;按键1按下&#xff0c;LED亮&#xff0c;再按一次&#xff0c;灭 按键2按下&#xff0c;蜂鸣器响。再按一次&#xff0c;不响 按键3按下&#xff0c;风扇转&#xff0c;再按一次&#xff0c;风扇停 src/do_irq.c #include "key_it.h" ex…...

C#的值类型和引用类型

不得不说c#的类型系统设计有点意思&#xff0c;不同的编程语言对于类型的设计各有取舍。 值类型&#xff1a; 当我们将一个int类型的值赋值到另一个int类型的值时&#xff0c;它实际上是创建了一个完全不同的副本。换句话说&#xff0c;如果你改变了其中某一个的值&#xff0…...

YOLOv7改进:极简的神经网络模型 VanillaNet---VanillaBlock助力检测,实现暴力涨点 | 华为诺亚2023

💡💡💡本文属于原创独家改进:极简模块VanillaBlock,以极简主义的设计为理念,网络中仅仅包含最简单的卷积计算,去掉了残差和注意力模块,二次创新引入到YOLOv7中取得了不俗的效果。 极简模块VanillaBlock | 亲测在多个数据集实现涨点; 收录: YOLOv7高阶自研专…...

对验证码的识别爆破

声明&#xff1a;该系列文章首发于公众号&#xff1a;Y1X1n安全&#xff0c;转载请注明出处&#xff01;本公众号所分享内容仅用于每一个爱好者之间的技术讨论及教育目的&#xff0c;所有渗透及工具的使用都需获取授权&#xff0c;禁止用于违法途径&#xff0c;否则需自行承担&…...

LeetCode【15】三数之和

题目&#xff1a; 解析&#xff1a; 参考&#xff1a;https://zhuanlan.zhihu.com/p/111715985 代码&#xff1a; public static List<List<Integer>> threeSum(int[] nums) {// 先排序Arrays.sort(nums);List<List<Integer>> result new ArrayLis…...

Gossip协议是什么

Gossip协议是什么 Gossip protocol 也叫 Epidemic Protocol (流行病协议), 是基于流行病传播方式的节点或者进程之间信息交换的协议, 也被叫做流言算法, 八卦算法、疫情传播算法等等. 说到 Gossip 协议, 就不得不提著名的六度分隔理论. 简单地说, 你和任何一个陌生人之间所间…...

【java学习】this关键字(27)

文章目录 1. this是什么&#xff1f;2. this的作用 1. this是什么&#xff1f; 在 java 中&#xff0c;this关键字比较难理解&#xff0c;它的作用和其词义很接近。 ①它在方法内部使用&#xff0c;即这个方法所属对象的引用&#xff1b; ②它在构造器内部使用&#xff0c;表示…...

27、元组

区分&#xff1a; 数组&#xff1a;纯粹 一个[]中的数据类型都是一致的 元组&#xff1a;不纯粹 一个[]中可能有不同类型的数据项 意义 当赋值或访问一个已知索引的元素时&#xff0c;可以得到正确的类型 let miao: [string, number] [cat, 18]; miao[0] cat miao[1] 18…...

1km分辨率逐月降雨量和最高温度数据集(1901-2022)--数据处理

1km分辨率逐月降雨量和最高温度数据集&#xff08;1901-2022&#xff09;的下载可以参考我的另外一篇博客&#xff1a; 这里的温度和降雨数据集都是NC格式的&#xff0c;需要将其处理为tif格式&#xff0c;我采用的处理软件是MATLAB。 本篇博客以处理温度数据为例&#xff0c…...

docker入门加实战—docker常见命令

docker入门加实战—docker常见命令 在介绍命令之前&#xff0c;先用一副图形象的展示一下docker的命令&#xff1a; 常见命令 docker的常见命令和文档地址如下表&#xff1a; 命令说明文档地址docker pull拉取镜像docker pulldocker push推送镜像到DockerRegistrydocker pus…...

【C/C++】使用 g++ 编译器编译 C++ 程序的完全指南

本文介绍了 g 编译器的使用方法和常见参数解释&#xff0c;帮助您编译和构建 C 程序。 引言 在 C 程序开发中&#xff0c;选择一个合适的编译器是至关重要的。g 是 GNU 编译器集合&#xff08;GCC&#xff09;中的 C 编译器&#xff0c;提供了丰富的功能和选项&#xff0c;帮…...

ARM中断实验

设置按键中断&#xff0c;按键1按下&#xff0c;LED亮&#xff0c;再按一次&#xff0c;灭 按键2按下&#xff0c;蜂鸣器响。再按一次&#xff0c;不响 按键3按下&#xff0c;风扇转&#xff0c;再按一次&#xff0c;风扇停 main.c #include "uart1.h" #include …...

Vue条件渲染

一、使用v-show条件渲染 语法格式&#xff1a; v-show"表达式" // true 或 false 当表达式的值为true的时候就显示&#xff0c;表达式值为false的时候隐藏。 下面是使用v-show实现的一个点击按钮切换显示和隐藏的小案例 &#xff1a; 值得注意的是&#xff0c;使…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...

为什么要创建 Vue 实例

核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...

Python 训练营打卡 Day 47

注意力热力图可视化 在day 46代码的基础上&#xff0c;对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...

es6+和css3新增的特性有哪些

一&#xff1a;ECMAScript 新特性&#xff08;ES6&#xff09; ES6 (2015) - 革命性更新 1&#xff0c;记住的方法&#xff0c;从一个方法里面用到了哪些技术 1&#xff0c;let /const块级作用域声明2&#xff0c;**默认参数**&#xff1a;函数参数可以设置默认值。3&#x…...