文章目录
- 一、双指针算法分类
- 二、相向双指针示例 ( 有效回文串 )
一、双指针算法分类
面试时经常遇到 限制算法复杂度为
的情况 , 就需要使用以下算法 :
- 双指针算法 : 设置两个指针 ( 索引 ) , 进行不同方式的遍历 , 使用最高频的算法 ;
- 打擂台算法 : 设置一个擂主值 , 设置为无穷大或无穷小 , 通过遍历让该擂主值与遍历值打擂台 ; 求最大值最小值常用 ;
- 单调栈算法 ;
- 单调队列算法 ;
双指针算法分类 :
- 相向双指针 : 判断一个字符串是否是回文串 , 从两边向中心遍历 ;
- 背向双指针 : 查找一个字符串的最长回文子串使用的 " 中心线枚举算法 " 就是背向双指针算法 , 从中心向两边遍历 ; ( 出现频率较 - 低 )
- 同向双指针 :
相向双指针算法分类 :
- 翻转类型 : ① 翻转字符串 , ② 判断回文串 ; 两个指针分别指向收尾 , 两边往中间走 , 对比两个指向的元素是否相等 ;
- 两数之和型 : ① 两数之和 , ② 三数之和 ;
- 分割类型 : ① 快速排序 , ② 颜色排序 ; 给定一个数组 , 将其分割成两部分 , 一部分满足某条件 , 另外一部分不满足某条件 ;
二、相向双指针示例 ( 有效回文串 )
有效回文串 : https://www.lintcode.com/problem/415/
如果是不忽略大小写 , 特殊字符的情况 , 可以直接 翻转字符串 , 然后对比是否相等 ; 但是如果添加了上述要求 , 就需要处理大小写 , 特殊字符问题 , 有两种方案 :
- 创建新字符串 , 过滤掉大小写及特殊字符干扰, 然后翻转字符对比 , 这样会增加额外空间开销 ;
- 推荐使用双指针算法 , 一边进行过滤 , 一边进行对比 ;
设计两个指针 , 分别指向字符串的最左侧 和 最右侧 ;
每次遍历 , 都要进行 两个指针的下标判断 , 否则就会导致下标访问越界 ;
代码示例 :
代码语言：javascript复制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);
}
}
