双指针，集合问题-LeetCode 344、345、347、349、350
- 2019 年 11 月 30 日
- 筆記
作者：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）
