面试时经常遇到 限制算法复杂度为
的情况 , 就需要使用以下算法 :
双指针算法分类 :
相向双指针算法分类 :
有效回文串 : 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);
}
}