双指针，集合问题-LeetCode 344、345、347、349、350
双指针，集合问题-LeetCode 344、345、347、349、350
作者：TeddyZhang
双指针，集合问题：LeetCode #344 345 347 349 350
1
编程题
【LeetCode #344】反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。 你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1： 输入：["h","e","l","l","o"] 输出：["o","l","l","e","h"]
解题思路：
利用首尾指针，然后向中间走，走的同时交换两个位置的值！本来是用C++只需要三行代码，但凸显不了我们的示例，因此使用异或来取代swap函数！这个之前题目有说到过！
class Solution {
public:
void reverseString(vector<char>& s) {
int l = 0, r = s.size()-1;
while(l < r){
//swap(s[l++], s[r--]);
s[l] ^= s[r];
s[r] ^= s[l];
s[l] ^= s[r];
l++, r--;
}
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reverse-string
【LeetCode #345】反转字符串的元音字母
编写一个函数，以字符串作为输入，反转该字符串中的元音字母。
示例 1: 输入: "hello" 输出: "holle"
解题思路：
依然是双指针（首尾指针）的方法，当不满足元音时，则跳过，如果满足，则交换两个值。判断一个字符是否为元音，这里使用了哈希表！但其实使用string中的find函数更加高效一些！
class Solution {
public:
string reverseVowels(string s) {
int chares[] = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'}; //也可以使用string.find
unordered_set<char> set(chares, chares+10);
int l = 0, r = s.size()-1;
while(l < r){
if(set.find(s[l]) == set.end()){
l++;
}else if(set.find(s[r]) == set.end()){
r--;
}else{
//swap(s[l++], s[r--]);
s[l] ^= s[r];
s[r] ^= s[l];
s[l] ^= s[r];
l++, r--;
}
}
return s;
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reverse-vowels-of-a-string/
【LeetCode #347】前K个高频元素
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1: 输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]
解题思路：
map按照value大小排序，由于map是关联容器，本身就是有序的，但是按照key来排序的，这个之前也说过，map的迭代器是双向迭代器，而sort函数只支持随机访问迭代器，因此需要拷贝到vector中进行排序处理！ 满满的套路呀，之前就遇到过这种的！
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
vector<int> res;
map<int, int> m;
for(auto num: nums){
m[num]++;
}
vector<pair<int, int>> vec(m.begin(), m.end());
sort(vec.begin(), vec.end(), [](pair<int, int>& a, pair<int, int>& b){
return a.second > b.second;
});
int i = 0;
while(i < k){
res.push_back(vec[i++].first);
}
return res;
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/top-k-frequent-elements/
【LeetCode #349】两个数组的交集
给定两个数组，编写一个函数来计算它们的交集。
示例 1: 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2]
解题思路：
直接使用STL算法中的set操作函数，注意set有关的函数必须在排序序列中使用，因此必须先排序！然后使用unique函数去重即可！
（STL库函数版本）
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
vector<int> res;
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
set_intersection(nums1.begin(), nums1.end(), nums2.begin(), nums2.end(), back_inserter(res));
auto it = unique(res.begin(), res.end());
res.erase(it, res.end());
return res;
}
};（非库函数版本）
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
vector<int> res;
for(int i = 0; i < nums1.size(); i ++){
for(int j = 0; j < nums2.size(); j++){
if(nums1[i] == nums2[j]){
res.push_back(nums1[i]);
break;
}
}
}
sort(res.begin(), res.end());
auto it = unique(res.begin(), res.end());
res.erase(it, res.end());
return res;
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/intersection-of-two-arrays/
【LeetCode #350】两个数组的交集 II
给定两个数组，编写一个函数来计算它们的交集。
示例 1: 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2,2]
解题思路：
相比于上一道题，简单了，不用最后的去重了，太easy了，无力吐槽了！讲道理不应该更难么？
在非库函数版本中，我们可以使用映射map的方法，统计nums1中元素的个数，如果再nums2中出现，则减1，并将目标元素压入res中！
（库函数版本）
vector<int> res;
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
set_intersection(nums1.begin(), nums1.end(), nums2.begin(), nums2.end(), back_inserter(res));
auto it = unique(res.begin(), res.end());
res.erase(it, res.end());
return res;（非库函数版本）
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
map<int, int> m;
vector<int> res;
for(auto i: nums1){
m[i]++;
}
for(auto i: nums2){
if(m[i] != 0){
m[i]--;
res.push_back(i);
}
}
return res;
}
};来源：力扣（LeetCode）