LeetCode 刷题【26. 删除有序数组中的重复项、27. 移除元素、28. 找出字符串中第一个匹配项的下标】
26. 删除有序数组中的重复项
自己做
解1：双指针
class Solution {
public:int removeDuplicates(vector<int>& nums) {int len = 1;if(nums.size() == 1) //长度为1，根本不用删除直接返回return len;vector<int>::iterator p = nums.begin();vector<int>::iterator q = nums.begin();q++;while(q != nums.end()){if(*p == *q) //相同，删除重复元素q = nums.erase(q);else{ //不同，跳过q++;p++;len++;}}return len;}
}; 
解2：空间换时间
上面用erase太浪费时间了
class Solution {
public:int removeDuplicates(vector<int>& nums) {if(nums.size() == 1) //长度为1，根本不用删除直接返回return 1;vector<int> res; //新的存放数组vector<int>::iterator p = nums.begin();res.push_back(*p); //赋值第一个元素while(p != nums.end()){if(*(--res.end()) != *p) //不相同元素，保存，否则跳过res.push_back(*p);elsep++;}nums = res;return nums.size();}
};
27. 移除元素
自己做
解：空间换时间
class Solution {
public:int removeElement(vector<int>& nums, int val) {vector<int> res;for(vector<int>::iterator it = nums.begin(); it != nums.end(); it++){if(*it != val) //不相同，保存到新的数组中res.push_back(*it);}nums = res; //重新给nums赋值return nums.size();}
};
28. 找出字符串中第一个匹配项的下标
自己做
解1：逐字匹配暴力解
class Solution {
public:int strStr(string haystack, string needle) {int len1 = haystack.size();int len2 = needle.size();for(int i = 0; i < len1 - len2 + 1; i++){ //i表示匹配的起始下标bool is_exist = true; //确认是否匹配，默认是匹配for(int j = 0; j < len2; j++){ //开始匹配if(needle[j] != haystack[i + j]) //不匹配is_exist = false;}if(is_exist) //匹配，返回return i;}//不匹配return -1;}
};
解2：KMP
忘了，只记得next数组什么的，不过KM其实在不算长的字符串匹配中也不会优秀多少
记得有KMP、优化KMP，下面是翻笔记时间
KMP
class Solution {
public:int strStr(string haystack, string needle) {int len1 = haystack.size(); //主串长度int len2 = needle.size(); //子串长度if(len2 == 0) //子串为空，直接返回return 0;//next数组存放位移下标(这里初始化后都默认为0，表示前面没一个相等的，还是要从头开始，没有大位移)vector<int> next(len2); //根据子串处理next数组（这里的i表示前面的部分，j表示后面的部分）//next数组中的数表示如果j出现了匹配失败，那么子串指针就位移到i位置（next数组会在对应j-1中存放i，这表示i、j前面的部分都相同）for(int i = 0, j = 1; j < len2; j++){ //next[0]这个位置直接为0，因为前面根本不可能有相匹配的部分while(i > 0 && needle[i] != needle[j]){ //出现了不相等的情况i = next[i - 1]; //i、j出现匹配失败，i的指针位移参考next数组}if(needle[i] == needle[j]){ //两者相等i++; //i往后挪（尽可能往后匹配）} //这里表示j前面的元素（包括j）与i前面的元素（不包括i）都一致//当进行匹配时，利用j = next[j - 1]进行大位移next[j] = i; }//上面完成了next数组的初始化，下面是匹配过程for(int i = 0, j = 0; i < len1; i++){ //i表示主串指针，j表示子串指针while(j > 0 && haystack[i] != needle[j]) //不匹配就根据next数组回滚j = next[j - 1];if(haystack[i] == needle[j]) //阶段性胜利，i、j往后移j++;if(j == len2){ //匹配成功return i - len2 + 1; //这里的i指向了匹配的尾部，我们要返回头部}}return -1;}
};