热门标签 | HotTags
当前位置:  开发笔记 > 后端 > 正文

22.1.23Manacher算法、双端队列、单调栈

22.1.23Manacher算法、双端队列、单调栈1.Manacher算法1)用途:Manacher算法用于解决类似求某个字符串中最长的回文子串。(回文就是正着读和倒着读一样的结

22.1.23Manacher算法、双端队列、单调栈


1.Manacher算法


1)用途:


  • Manacher算法用于解决类似求某个字符串中最长的回文子串。(回文就是正着读和倒着读一样的结构)。




2)算法中的关键变量:


  • 回文半径 r:回文直径的一半;



  • 回文直径 d:整个回文的长度;



  • 之前扩大的所有位置中所到达的回文直径d的最右边界R;



  • 中心点c:取得R的那个点;



  • 回文半径数组:储存遍历字符串所得到的每个点的回文半径;




3)算法的流程:


  • 伪代码:



  •  

     





  • 这里的R与上述提到的概念不太相同,这里是回文最右边界的下一位。对字符串依次遍历,我们回遇到三种情况:



    • 当前遍历到的元素不在回文的有边界R内:此时没什么优化的方法,直接暴力扩大,判断扩大的是否为回文结构。



    • 当前遍历到的元素在右边界内:此时可以做出如下的位置关系:(L是R关于中心c的对称点,i'是i(当前遍历的点)的对称点),此时i的回文直径,回文半径都与他的对称点i'相同(根据对称的性质即可证明)。img



    • 当前遍历到的元素的对称点的回文直径的左边界在L的左边:如下图,此时i的回文半径就是i~R所表示的区域。下面给出证明:x,y分别为L,L'的前一个数和后一个数,k,z也同理。由c扩得的回文区域是L~R所表示的区域,那我们就知道x!=z的,根据i'的会问区域的左边界是超过了L的,我们能知道:至少是x,y也在i'的回文区域内,所以x=y的,y=k,因为x!=z的,所以k!=z。





    • img



     

     



    • 当前遍历到的元素的对称点的回文直径的左边界刚好与L重合:如下图:此时i的回文半径就是i'的回文半径。对称可证。





img



  • code:



public static char[] manacherString(String str) {
char[] charArr = str.toCharArray();
char[] res = new char[str.length() * 2 + 1];

int index = 0;
for (int i = 0; i != res.length; i++) {
res[i] = (i & 1) == 0 ? '#' : charArr[index++];
}
return res;
}

public static int maxLcpsLength(String str) {
if (str == null || str.length() == 0) {
return 0;
}
char[] charArr = manacherString(str);
int[] pArr = new int[charArr.length];
int C = -1;
int R = -1;
int max = Integer.MIN_VALUE;
for (int i = 0; i != charArr.length; i++) {
pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
//
while (i + pArr[i] <charArr.length && i - pArr[i] > -1) {
if (charArr[i + pArr[i]] == charArr[i - pArr[i]])
pArr[i]++;
else {
break;
}
}
if (i + pArr[i] > R) {
R = i + pArr[i];
C = i;
}
max = Math.max(max, pArr[i]);
}
return max - 1;
}

public static void main(String[] args) {
String str1 = "abc1234321ab";
System.out.println(maxLcpsLength(str1));
}

2.双端队列


1)问题:


  • 给定一个输入int[] arr, 窗口大小为w,输出长度为n-w+1得到数组res,res中包含每次窗口中的最大值。




2)思路(进阶:L,R自由移动的情况):


  • 设置一个双端队列,前后都可以进出,当R右移时,队列后面进入一个数组元素的下标(一直数组通过下标可以得到这个数),双端队列中始终要维持单调(如果是求窗口最大值则保持从大到小的结构,反之求最小值就保持从小到大的结构)。



    • 当L右移时,双端队列就从前边淘汰一个元素。L对应的队列中的元素始终是L~R范围上的最大值。



    • 在R移动时,如果遇到当前要进入队列的数大于已经进入队列的数,则弹出小于等于当前数的数,遇到大于当前数或队列为空时在让当前数进入;



    • 如果当前数小于队列中的最后一个属就直接进入。






3)code:

public static int[] getMaxWindow(int[] arr, int w) {
if (arr == null || w <1 || arr.length <w) {
return null;
}
LinkedList<Integer> qmax = new LinkedList<Integer>();
int[] res = new int[arr.length - w + 1];
int index = 0;
for (int i = 0; i <arr.length; i++) {
while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]) {
qmax.pollLast();
}
qmax.addLast(i);
if (qmax.peekFirst() == i - w) {
qmax.pollFirst();
}
if (i >= w - 1) {
res[index++] = arr[qmax.peekFirst()];
}
}
return res;
}

// for test
public static void printArray(int[] arr) {
for (int i = 0; i != arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}

public static void main(String[] args) {
int[] arr = { 4, 3, 5, 4, 3, 3, 6, 7 };
int w = 3;
printArray(getMaxWindow(arr, w));

}

 


3.单调栈


1)问题:


  • 求数组中任意一个数左右两边比他大(或小)且离他最近的两个数。




2)思路:


  • 在无重复值的情况下,设置一个栈结构,若求大的情况则栈中从栈底到栈顶的顺序为从大到小,反之求两边小的数的情况顺序就为从小到大。下面以求解左右两边较大的数来讨论。



  • 在一个数进站时,先判断栈是否为空或者当前的数是否小于栈顶的数,满足其中任意一种情况就直接压入栈,反之就从栈顶开始出栈,同时记录下出栈元素左边的距离他最近的且比它大的数是压在栈顶下面的数,右边的距离他最近的且比它大的数是即将入栈的数。重复操作直到栈为空或者遇到了比即将入栈的数大的数就停止操作,把即将入栈的数压入栈中。



  • 当遍历完是数组的最后一个元素时,开始清栈操作。具体的做法为一次弹出栈顶元素,记录左边的距离栈顶元素最近的且比它大的数是压在栈顶下面的数,右边的为空,直到栈空。




3)code:

//待补充

 

 



推荐阅读
  • 云原生边缘计算之KubeEdge简介及功能特点
    本文介绍了云原生边缘计算中的KubeEdge系统,该系统是一个开源系统,用于将容器化应用程序编排功能扩展到Edge的主机。它基于Kubernetes构建,并为网络应用程序提供基础架构支持。同时,KubeEdge具有离线模式、基于Kubernetes的节点、群集、应用程序和设备管理、资源优化等特点。此外,KubeEdge还支持跨平台工作,在私有、公共和混合云中都可以运行。同时,KubeEdge还提供数据管理和数据分析管道引擎的支持。最后,本文还介绍了KubeEdge系统生成证书的方法。 ... [详细]
  • JVM 学习总结(三)——对象存活判定算法的两种实现
    本文介绍了垃圾收集器在回收堆内存前确定对象存活的两种算法:引用计数算法和可达性分析算法。引用计数算法通过计数器判定对象是否存活,虽然简单高效,但无法解决循环引用的问题;可达性分析算法通过判断对象是否可达来确定存活对象,是主流的Java虚拟机内存管理算法。 ... [详细]
  • 计算机存储系统的层次结构及其优势
    本文介绍了计算机存储系统的层次结构,包括高速缓存、主存储器和辅助存储器三个层次。通过分层存储数据可以提高程序的执行效率。计算机存储系统的层次结构将各种不同存储容量、存取速度和价格的存储器有机组合成整体,形成可寻址存储空间比主存储器空间大得多的存储整体。由于辅助存储器容量大、价格低,使得整体存储系统的平均价格降低。同时,高速缓存的存取速度可以和CPU的工作速度相匹配,进一步提高程序执行效率。 ... [详细]
  • Android工程师面试准备及设计模式使用场景
    本文介绍了Android工程师面试准备的经验,包括面试流程和重点准备内容。同时,还介绍了建造者模式的使用场景,以及在Android开发中的具体应用。 ... [详细]
  • 生成式对抗网络模型综述摘要生成式对抗网络模型(GAN)是基于深度学习的一种强大的生成模型,可以应用于计算机视觉、自然语言处理、半监督学习等重要领域。生成式对抗网络 ... [详细]
  • 本文回顾了3.21开学以来的学习情况,包括javaWeb课程的迷糊感和未预习导致的不知所措,以及对VOJ题目的归类和解答。午饭前完成了阶乘相关的两道题目。下午的数据结构课听懂了队列的讲解,但有几个疑问未能及时复习。设计模式课程因预习效率低而感到困惑,同时也没搞清楚下节课的内容。晚上去图书馆学习。通过反思和总结,对自己的学习收获有了更深刻的认识。 ... [详细]
  • Tomcat/Jetty为何选择扩展线程池而不是使用JDK原生线程池?
    本文探讨了Tomcat和Jetty选择扩展线程池而不是使用JDK原生线程池的原因。通过比较IO密集型任务和CPU密集型任务的特点,解释了为何Tomcat和Jetty需要扩展线程池来提高并发度和任务处理速度。同时,介绍了JDK原生线程池的工作流程。 ... [详细]
  • 006_Redis的List数据类型
    1.List类型是一个链表结构的集合,主要功能有push,pop,获取元素等。List类型是一个双端链表的结构,我们可以通过相关操作进行集合的头部或者尾部添加删除元素,List的设 ... [详细]
  • 栈和队列的共同处和不同处
    本文主要介绍了栈和队列的共同处和不同处。栈和队列都是由几个数据特性相同的元素组成的有限序列,也就是线性表。队列是限定仅在表的一端插入元素、在另一端删除元素的线性表,遵循先进先出的原则。栈是限定仅在表尾进行插入或删除操作的线性表,遵循后进先出的原则。 ... [详细]
  • 深入理解Kafka服务端请求队列中请求的处理
    本文深入分析了Kafka服务端请求队列中请求的处理过程,详细介绍了请求的封装和放入请求队列的过程,以及处理请求的线程池的创建和容量设置。通过场景分析、图示说明和源码分析,帮助读者更好地理解Kafka服务端的工作原理。 ... [详细]
  • 李逍遥寻找仙药的迷阵之旅
    本文讲述了少年李逍遥为了救治婶婶的病情,前往仙灵岛寻找仙药的故事。他需要穿越一个由M×N个方格组成的迷阵,有些方格内有怪物,有些方格是安全的。李逍遥需要避开有怪物的方格,并经过最少的方格,找到仙药。在寻找的过程中,他还会遇到神秘人物。本文提供了一个迷阵样例及李逍遥找到仙药的路线。 ... [详细]
  • Oracle优化新常态的五大禁止及其性能隐患
    本文介绍了Oracle优化新常态中的五大禁止措施,包括禁止外键、禁止视图、禁止触发器、禁止存储过程和禁止JOB,并分析了这些禁止措施可能带来的性能隐患。文章还讨论了这些禁止措施在C/S架构和B/S架构中的不同应用情况,并提出了解决方案。 ... [详细]
  • 一句话解决高并发的核心原则
    本文介绍了解决高并发的核心原则,即将用户访问请求尽量往前推,避免访问CDN、静态服务器、动态服务器、数据库和存储,从而实现高性能、高并发、高可扩展的网站架构。同时提到了Google的成功案例,以及适用于千万级别PV站和亿级PV网站的架构层次。 ... [详细]
  • 本文介绍了栈和队列的区别及其特点。栈是一种先进后出的线性表,只能在表的一端进行插入和删除操作;队列是一种先进先出的线性表,只能在表的一端进行插入和在另一端进行删除操作。栈和队列是两种广泛使用的线性数据结构,它们的基本操作具有特殊性。栈的遍历需要遍历整个栈才能取出数据,并需要为数据开辟临时空间,而队列基于地址指针进行遍历,可以从头或尾部开始遍历,但不能同时遍历,且无需开辟临时空间。栈和队列在程序设计中具有重要应用。 ... [详细]
  • Linux的uucico命令使用方法及工作模式介绍
    本文介绍了Linux的uucico命令的使用方法和工作模式,包括主动模式和附属模式。uucico是用来处理uucp或uux送到队列的文件传输工具,具有操作简单快捷、实用性强的特点。文章还介绍了uucico命令的参数及其说明,包括-c或--quiet、-C或--ifwork、-D或--nodetach、-e或--loop、-f或--force、-i或--stdin、-I--config、-l或--prompt等。通过本文的学习,读者可以更好地掌握Linux的uucico命令的使用方法。 ... [详细]
author-avatar
继续不插电的名单
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有