雙指針，集合問題-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）
