文章目录
一、双指针算法分类
二、相向双指针示例 ( 有效回文串 )
一、双指针算法分类
----
面试时经常遇到 限制算法复杂度为
O ( n )
的情况 , 就需要使用以下算法 :
双指针算法...: 设置两个指针 ( 索引 ) , 进行不同方式的遍历 , 使用最高频的算法 ;
打擂台算法 : 设置一个擂主值 , 设置为无穷大或无穷小 , 通过遍历让该擂主值与遍历值打擂台 ; 求最大值最小值常用...;
单调栈算法 ;
单调队列算法 ;
双指针算法分类 :
相向双指针 : 判断一个字符串是否是回文串 , 从两边向中心遍历 ;
背向双指针 : 查找一个字符串的最长回文子串使用的 " 中心线枚举算法 "...就是背向双指针算法 , 从中心向两边遍历 ; ( 出现频率较 - 低 )
同向双指针 :
相向双指针算法分类 :
翻转类型 : ① 翻转字符串 , ② 判断回文串 ; 两个指针分别指向收尾 , 两边往中间走...然后对比是否相等 ;
但是如果添加了上述要求 , 就需要处理大小写 , 特殊字符问题 , 有两种方案 :
创建新字符串 , 过滤掉大小写及特殊字符干扰, 然后翻转字符对比 , 这样会增加额外空间开销 ;
推荐使用双指针算法