文章目录

• 一、双指针算法分类
• 二、相向双指针示例 ( 有效回文串 )

一、双指针算法分类

---

面试时经常遇到 限制算法复杂度为 $O(n)$ 的情况 , 就需要使用以下算法 :

• 双指针算法 : 设置两个指针 ( 索引 ) , 进行不同方式的遍历 , 使用最高频的算法 ;
• 打擂台算法 : 设置一个擂主值 , 设置为无穷大或无穷小 , 通过遍历让该擂主值与遍历值打擂台 ; 求最大值最小值常用 ;
• 单调栈算法 ;
• 单调队列算法 ;

双指针算法分类 :

• 相向双指针 : 判断一个字符串是否是回文串 , 从两边向中心遍历 ;
• 背向双指针 : 查找一个字符串的最长回文子串使用的 " 中心线枚举算法 " 就是背向双指针算法 , 从中心向两边遍历 ; ( 出现频率较 - 低 )
• 同向双指针 :

相向双指针算法分类 :

• 翻转类型 : ① 翻转字符串 , ② 判断回文串 ; 两个指针分别指向收尾 , 两边往中间走 , 对比两个指向的元素是否相等 ;
• 两数之和型 : ① 两数之和 , ② 三数之和 ;
• 分割类型 : ① 快速排序 , ② 颜色排序 ; 给定一个数组 , 将其分割成两部分 , 一部分满足某条件 , 另外一部分不满足某条件 ;

二、相向双指针示例 ( 有效回文串 )

---

有效回文串 : https://www.lintcode.com/problem/415/

如果是不忽略大小写 , 特殊字符的情况 , 可以直接 翻转字符串 , 然后对比是否相等 ;
但是如果添加了上述要求 , 就需要处理大小写 , 特殊字符问题 , 有两种方案 :

• 创建新字符串 , 过滤掉大小写及特殊字符干扰, 然后翻转字符对比 , 这样会增加额外空间开销 ;
• 推荐使用双指针算法 , 一边进行过滤 , 一边进行对比 ;

设计两个指针 , 分别指向字符串的最左侧 和 最右侧 ;

每次遍历 , 都要进行 两个指针的下标判断 , 否则就会导致下标访问越界 ;

代码示例 :

public class Solution {/*** @param s: 一个字符串* @return: 该字符串是否有有效回文串*/public boolean isPalindrome(String s) {if (s == null) {return false;}// 双指针int left = 0, right = s.length() - 1;while (left < right) {// 左指针向右移动, 一直移动, 直到遇到一个合法的字符, 即字母或数字while (left < right && !isValid(s.charAt(left))) {left ++;}// 右指针向左移动, 一直移动, 直到遇到一个合法的字符, 即字母或数字while (left < right && !isValid(s.charAt(right))) {right --;}// 对比两个指针指向的字符, 如果不相等, 则说明该字符串不是有效回文串if (left < right && !isEqual(s.charAt(left), s.charAt(right))) {return false;}// 两指针相向移动left++;right--;}return true;}/*** 判定字符串是否是字母或数字* @param c 被判定的字符串* @return 是否是字母或数字*/private boolean isValid(char c) {return Character.isLetter(c) || Character.isDigit(c);}/*** 对比两个字符是否相等, 忽略大小写, 先将字符转为小写字母, 然后再对比* @param a 对比的字符一* @param b 对比的字符二* @return 字符转为小写字母后, 是否相等*/private boolean isEqual(char a, char b) {return Character.toLowerCase(a) == Character.toLowerCase(b);} }class Main{public static void main(String[] args) {boolean isPalindrome = new Solution().isPalindrome("A man, a plan, a canal: Panama");System.out.println(isPalindrome);} }

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的【算法】双指针算法 ( 双指针算法分类 | 相向双指针 | 有效回文串 )的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。