Notes

tags: Hash Table,Heap (data structure),LeetCode101,Priority Queue,C++ Lambda class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { vector<int> res; unordered_map<int, int> freq; // Note that: we need caputre a map by reference, // otherwise we can't use the operator[]. // See also: https://stackoverflow.com/a/6281071 auto comp_by_map = [&freq](const int& a, const int& b) { return freq[a] < freq[b]; }; // Note that: here we need pass our lambda /comp_by_map/ to the // constructor of std::priority_queue. priority_queue<int, vector<int>, decltype(comp_by_map)> pq(comp_by_map); for (auto n: nums) { freq[n] = freq.find(n) == freq.end() ? 1 : freq[n] + 1; } for (auto iter: freq) { pq.push(iter.first); } while (k > 0) { res.push_back(pq.top()); pq.pop(); k--; } return res; } };

tags: LeetCode101,In-place Travel array in reverse order, and record how many times need to swap, which is how many elements not equal val. class Solution { public: int removeElement(vector<int>& nums, int val) { int k = 0; for (int j = nums.size() - 1; j >= 0; --j) { if (nums[j] == val) { for (int i = 0; i < k; ++i) { swap(nums[i + j], nums[j + i + 1]); } } else { k++; } } return k; } };

tags: Two Pointers,Three Pointers,LeetCode101,Sorting Based on: LeetCode101: 167. Two Sum II - Input Array Is Sorted LeetCode101: 15. 3Sum We create a new loop: class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { sort(nums.begin(), nums.end()); vector<vector<int>> res; int T, S, r, l; for (int i = 0; i < nums.size(); ++i) { if (i > 0 && nums[i] == nums[i - 1]) { continue; } for (int j = i + 1; j < nums.size(); ++j) { if (j > i + 1 && nums[j] == nums[j - 1]) { continue; } l = j + 1; r = nums.size() - 1; T = target - nums[i] - nums[j]; while (l < r) { S = nums[l] + nums[r]; if (S == T) { res.push_back({nums[i], nums[j], nums[l], nums[r]}); while (l < r && nums[l] == nums[l + 1]) { l++; } while (l < r && nums[r] == nums[r - 1]) { r--; } l++; r--; } else if (S < T) { l++; } else { r--; } } } } return res; } };

tags: Priority Queue,LeetCode101 Using a min heap to keep k elements, top is the Kth largest element. class KthLargest { private: // min heap priority_queue<int, vector<int>, std::greater<int>> pq; int K; public: KthLargest(int k, vector<int>& nums) { K = k; for (auto n: nums) { add(n); } } int add(int val) { pq.push(val); while (pq.size() > K) { pq.pop(); } return pq.top(); } }; /** * Your KthLargest object will be instantiated and called as such: * KthLargest* obj = new KthLargest(k, nums); * int param_1 = obj->add(val); */

tags: Heap (data structure),LeetCode101 Find top k values, classical heap problems. Here we need find top 2 values, and pop them from heap, then we will meet two cases: If they are not same, put back the differ between them, continue. Otherwise, continue directly.