面试时经常遇到 限制算法复杂度为
O ( n )
的情况 , 就需要使用以下算法 :
双指针算法 : 设置两个指针 ( 索引 ) , 进行不同方式的遍历 , 使用最高频的算法 ;
打擂台算法 : 设置一个擂主值..., 设置为无穷大或无穷小 , 通过遍历让该擂主值与遍历值打擂台 ; 求最大值最小值常用 ;
单调栈算法 ;
单调队列算法 ;
双指针算法分类 :
相向双指针 : 判断一个字符串是否是回文串 , 从两边向中心遍历...判断回文串 ; 两个指针分别指向收尾 , 两边往中间走 , 对比两个指向的元素是否相等 ;
两数之和型 : ① 两数之和 , ② 三数之和 ;
分割类型 : ① 快速排序 , ② 颜色排序 ; 给定一个数组..., 特殊字符的情况 , 可以直接 翻转字符串 , 然后对比是否相等 ;
但是如果添加了上述要求 , 就需要处理大小写 , 特殊字符问题 , 有两种方案 :
创建新字符串 , 过滤掉大小写及特殊字符干扰..., 则说明该字符串不是有效回文串
if (left < right && !