雖然目前工作上不需要自己寫算法倚喂，但還是想寫點記錄下什么斋泄。這里推薦個刷題網(wǎng)站LeetCode杯瞻，如果你是個大學未畢業(yè)的學生，我認為做些算法題是非常有必要的炫掐，說不定能在未來的面試時中給你帶來驚喜又兵。接下去我會分享下我在做算法題時會用到的一些方法。本文及未來文章的代碼部分都是 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.題目中通過例子可以清楚看到不考慮標點符號和空格秽梅，所以在遍歷中遇到非自字符或數(shù)字要跳過；
2.這道題不需要考慮大小寫剿牺，所以在比較時要將大寫轉為小寫或者小寫轉為大寫企垦；
3.回文特點就是對稱，所以可以分別在兩端給設一個標記點晒来，左右比較（通過ASCII碼來比較）钞诡，如果遇到不相等，返回false湃崩，反之進行移動荧降，直到左邊的大于等于右邊的循環(huán)停止。
經(jīng)過上述分析攒读，下面就是這道題的一個AC解
class Solution {
public:
//驗證是否是數(shù)字和字符
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])){//跳過非數(shù)字字符的情況
l++;
}else if(!isAlphanumeric(s[r])){//跳過非數(shù)字字符的情況
r--;
}else{
if(lowerCase(s[l])==lowerCase(s[r])){//進行比較,相等繼續(xù)移動這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
就是在一個有序數(shù)組中找到2個數(shù)相加等于給定的數(shù)朵诫，并返回這兩個數(shù)的在數(shù)組中的位置，這里的位置不是從0開始薄扁，所以下面要注意在索引的基礎上加1剪返。
分析這道算法題：
1.暴力解法就是2次遍歷，求出所有和邓梅，時間復雜度O(n^2)随夸，不一定能被AC。
2.其實通過有序這2個字震放，我們可以輕易得到一個O(n)的解法，在左右各設2個標記點驼修，分別為l和r,下面是偽代碼
if(target==numbers[l]+numbers[r]){
//已經(jīng)找到了這2個數(shù)的索引l和r,記錄并分別加1后返回即可殿遂。
}else if(target<numbers[l]+numbers[r]){
r--;//此時2個數(shù)比目標數(shù)大，因為數(shù)組是從小到大有序的乙各，此時希望numbers[r]這個數(shù)變小
}else{同理此時希望numbers[i]這個數(shù)變大
l++;
}
經(jīng)過上述分析墨礁，下面就是這道題的一個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;
}
};
那么如果數(shù)組是無序的呢，這個時候我們可以借助map來解決耳峦，等說到map的時候再來分享恩静。
今天的分享暫時先這樣了，下一篇會說下在雙指針基礎上，移動窗口的使用驶乾。
本文難免有紕漏和錯誤邑飒，如有發(fā)現(xiàn)敬請指正，謝謝级乐！
