虽然目前工作上不需要自己写算法，但还是想写点记录下什么。这里推荐个刷题网站LeetCode，如果你是个大学未毕业的学生，我认为做些算法题是非常有必要的，说不定能在未来的面试时中给你带来惊喜。接下去我会分享下我在做算法题时会用到的一些方法。本文及未来文章的代码部分都是 C++，如果未接触过的朋友，有必要了解如vector,map,set等在C++上是如何使用的。
今天先来说下双指针法。
首先是LeetCode上的125. Valid Palindrome
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.
就是给定一个字符串，判断是不是回文的，是返回true，否的返回false。
分析这道算法题：
1.题目中通过例子可以清楚看到不考虑标点符号和空格，所以在遍历中遇到非自字符或数字要跳过；
2.这道题不需要考虑大小写，所以在比较时要将大写转为小写或者小写转为大写；
3.回文特点就是对称，所以可以分别在两端给设一个标记点，左右比较（通过ASCII码来比较），如果遇到不相等，返回false，反之进行移动，直到左边的大于等于右边的循环停止。
经过上述分析，下面就是这道题的一个AC解
class Solution {
public:
//验证是否是数字和字符
bool isAlphanumeric(char c){
if('a'<=c&&c<='z'||'A'<=c&&c<='Z'||'0'<=c&&c<='9'){
return true;
}else return false;
}
//大写转小写
char upperToLower(char c){
if('A' <= c && c <= 'Z') return c-'A'+'a';
else return c;
}
bool isPalindrome(string s) {
if(s.size()==0) return true;//空字符直接返回
int l=0,r=s.size()-1;//定义两个起始点
while(l<r){
if(!isAlphanumeric(s[l])){//跳过非数字字符的情况
l++;
}else if(!isAlphanumeric(s[r])){//跳过非数字字符的情况
r--;
}else{
if(lowerCase(s[l])==lowerCase(s[r])){//进行比较,相等继续移动这2个标记点
l++;
r--;
}else return false;
}
}
return true;
}
};
接下去再来一道LeetCode上的167. Two Sum II - Input array is sorted
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution and you may not use the same element twice.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
就是在一个有序数组中找到2个数相加等于给定的数，并返回这两个数的在数组中的位置，这里的位置不是从0开始，所以下面要注意在索引的基础上加1。
分析这道算法题：
1.暴力解法就是2次遍历，求出所有和，时间复杂度O(n^2)，不一定能被AC。
2.其实通过有序这2个字，我们可以轻易得到一个O(n)的解法，在左右各设2个标记点，分别为l和r,下面是伪代码
if(target==numbers[l]+numbers[r]){
//已经找到了这2个数的索引l和r,记录并分别加1后返回即可。
}else if(target<numbers[l]+numbers[r]){
r--;//此时2个数比目标数大，因为数组是从小到大有序的，此时希望numbers[r]这个数变小
}else{同理此时希望numbers[i]这个数变大
l++;
}
经过上述分析，下面就是这道题的一个AC解
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int l=0,r=numbers.size()-1;
vector<int> res;
while(l<r){
if(target==numbers[l]+numbers[r]){
res.push_back(l+1);
res.push_back(r+1);
return res;
}else if(target<numbers[l]+numbers[r]){
r--;
}else{
l++;
}
}
return res;
}
};
那么如果数组是无序的呢，这个时候我们可以借助map来解决，等说到map的时候再来分享。
今天的分享暂时先这样了，下一篇会说下在双指针基础上，移动窗口的使用。
本文难免有纰漏和错误，如有发现敬请指正，谢谢！
