【算法题】——数组、双指针

1、 Leecode题目：两个数组的交集（查找 set）
思路： 一个数组元素都放入到哈希表中 ，然后看另一个数组中的元素在不在，最后结果存到unordered_set中转化成vector输出 set是insert vector是push_back

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {int len1 = nums1.size();int len2 = nums2.size();unordered_set<int> set1;unordered_set<int> res;vector<int> res1;for(int i=0;i<len1;i++){set1.insert(nums1[i]);}for(int i=0;i<len2;i++){if(set1.find(nums2[i]) != set1.end()){res.insert(nums2[i]);} }auto it = res.begin();for(;it != res.end();){res1.push_back(*it);it++;}return res1;}
};

2、删除有序数组的重复项（）
删除有序数组的重复项2（）
思路：快慢指针，第一个题只需要快指针和指针的前一个对比，不相同快慢指针分别++；第二题的思路由于相同元素最多保留2个，所以和慢指针-2的位置进行比较不是和快指针-2的位置进行比较，因为慢指针保留的是最后的结果指针，所以和慢指针比较，相当于快指针位置的元素选择保留还是不保留。

class Solution {
public:int removeDuplicates(vector<int>& nums) {//快指针遍历原来的数组 慢指针存储结果 超过2个的存2个int fast = 2,slow = 2;int len = nums.size();if(len <= 2) return len; // 由于是从2开始的所以需要特殊判断while(fast < len){if(nums[fast]  != nums[slow-2] ) {nums[slow] = nums[fast];slow++;}else{slow=slow;}fast++;}return slow;}
};

3、移除元素：快慢指针
4、反转字符串中的元音字母
思路：快慢指针区间分割。两个指针相对走，有时候也可以同一个方向走。

class Solution {
public:string reverseVowels(string s) {int len = s.length();if(len <= 1) return s;unordered_set<char> cc = {'a','e','i','o','u','A','E','I','O','U'};int i= 0 ,j = len -1;while(i < j){while( i < len && cc.count(s[i]) == 0) i++;while( j >=0 && !cc.count(s[j]) ) j--;if(i < j ) {swap(s[i++],s[j--]);}}return s;}
};

5、 长按键入
思路：双指针
标准串：saeed
输入的长串：ssaaedd
思路：i指针指向标准串，j指针指向输入的长串，如果相同，i和j分别向后移动，如果不相同，要进行判断j和j-1位置相同吗，相同j向后移动，否则，直接break；

class Solution {
public:bool isLongPressedName(string name, string typed) {int lenn = name.length();int lent = typed.length();if(lent < lenn) return false;if( lent == 1) return name[0]==typed[0] ? true : false;int i = 1,j=1;while(j < lent){if(i < lenn && name[i] == typed[j]){i++; j++;}else if(   typed[j] == typed[j-1]) { j++; }else {return false;}}return i == lenn ? true : false;}
};

6、最小石头的重量
思路： 优先队列 ，将元素放进队列中，然后自动排序了，取出堆顶两个元素，只有当有差值的时候才会将差值放进队列中，相等就等价于pop了，直到还剩1个石头或者没有石头的时候停止，没有就返回0，有的话返回最后一个石头的重量。

class Solution {
public:int lastStoneWeight(vector<int>& stones) {//优先队列priority_queue<int> q;for(int s : stones){q.push(s);}while(q.size() > 1){int a = q.top();q.pop();int b = q.top();q.pop();if(a > b){q.push(a-b);}}return q.empty() ? 0 : q.top();}
};
/*
priority_queue 底层是大堆
*/