Hash Table

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: Hash Table,LeetCode101,Sorting,Two Pointers Intuition with HashMap class Solution { public: int numRescueBoats(vector<int>& people, int limit) { unordered_map<int, int> cntOfWeights; for (auto iter = people.begin(); iter != people.end(); ++iter) { cntOfWeights[*iter]++; } int r = 0; for (int i = 0; i < people.size(); i++) { if (cntOfWeights[people[i]] == 0) { continue; } cntOfWeights[people[i]]--; for (int j = (limit - people[i]); j > 0; --j) { if (cntOfWeights.find(j) != cntOfWeights.end() && cntOfWeights[j] > 0) { cntOfWeights[j]--; break; } } r++; } return r; } }; Sorting and Two Pointers class Solution { public: int numRescueBoats(vector<int>& people, int limit) { int i = 0; int j = people.size() - 1; // heaviest go first sort(people.rbegin(), people.rend()); for (; i <= j; i++) { if (people[i] + people[j] <= limit) j--; } return i; } };

tags: Math,Hash Table,LeetCode101 class Solution { public: string intToRoman(int num) { vector<string> roman {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}; vector<int> integers {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 }; string r; int times = 0; for (int i = 0; i < integers.size(); ++i) { if (num >= integers[i]) { times = num / integers[i]; num -= times * integers[i]; for (int j = times; j > 0; --j) { r.append(roman[i]); } } } return r; } };

tags: String,LeetCode101,Stack,Hash Table,Hash Set I have solved this problem years before, LeetCode: 316.Remove Duplicate Letters, but still stuck on it. The key idea is not only about stack, but also required a map to record how many same letters behind current one. Which helps us to decide if drop current letter or not, when the new letter is less than the top of stack, which means smaller in lexicographical order. class Solution { public: string removeDuplicateLetters(string s) { vector<int> countOfLetters(26, 0); vector<bool> pickedLetters(26, false); stack<char> st; for (auto iter = s.begin(); iter != s.end(); ++iter) { countOfLetters[*iter - 'a']++; } for (int i = 0; i < s.size(); ++i) { countOfLetters[s[i] - 'a']--; if (pickedLetters[s[i] - 'a']) { continue; } while (!st.empty() && s[i] < st.top() && countOfLetters[st.top() - 'a'] > 0) { pickedLetters[st.top() - 'a'] = false; st.pop(); } st.push(s[i]); pickedLetters[s[i] - 'a'] = true; } string r; while (!st.empty()) { r.push_back(st.top()); st.pop(); } reverse(r.begin(), r.end()); return r; } };

tags: String,LeetCode101,Hash Set,Hash Table,Stack The key idea is similar to LeetCode101: 316. Remove Duplicate Letters, we use a HashMap to track how many letters which is same in the string. Then we use a HashSet to store appeared letters. When there is no more letters appeared in the HashSet, it’s time to partition. class Solution { public: vector<int> partitionLabels(string s) { unordered_map<char, int> cntOfLetters; unordered_set<char> appearedLetters; vector<int> r; int count = 0; for (auto iter = s.begin(); iter != s.end(); ++iter) { cntOfLetters[*iter]++; } for (auto iter = s.begin(); iter != s.end(); ++iter) { appearedLetters.insert(*iter); cntOfLetters[*iter]--; count++; // Append current count to result if there is no appeared letters // behind. bool behind = false; for (auto si = appearedLetters.begin(); si != appearedLetters.end(); ++si) { if (cntOfLetters[*si]){ behind = true; break; } } if (!behind) { r.push_back(count); count = 0; } } if (count > 1) { r.push_back(count); } return r; } };

tags: Monotonic Stack,Hash Table,LeetCode101 Mono-descreasing and reverse order travel class Solution { public: vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) { // Mono-descreasing and reverse order travel. // The next greater of the popped value is the top of the stack, if it has any. // // For example: [1,3,4,2] // the stack goes: // [2] // [4] -> 2 // [4, 3, 1] stack<int> st; vector<int> res; unordered_map<int, int> m; for (int i = nums2.size() - 1; i >= 0; i--) { while (!st.empty() && st.top() < nums2[i]) { int c = st.top(); st.pop(); if (!st.empty()) { m[c] = st.top(); } } st.push(nums2[i]); } while (st.size() > 1) { int c = st.top(); st.pop(); m[c] = st.top(); } for (int i = 0; i < nums1.size(); i++) { if (m.find(nums1[i]) != m.end()) { res.push_back(m[nums1[i]]); } else { res.push_back(-1); } } return res; } }; /* [1,3,5,2,4] [6,5,4,3,2,1,7] The stack goes: [7, 1] [7, 2] -> 1 and 1 is next greater is the top of the stack */

tags: C/C++ source: GeeksforGeeks. “Set vs Unordered_set in C++ STL,” May 28, 2018. https://www.geeksforgeeks.org/set-vs-unordered_set-c-stl/. set Ordered set that implemented by a “Self balancing BST” like Red-Black Tree. Extra find operations equal_range returns range of elements matching a specific key lower_bound returns an iterator to the first element not less than the given key upper_bound returns an iterator to the first element greater than the given key #include <iostream> #include <set> #include <assert.h> using namespace std; int main(void) { set<int> hset; hset.insert(5); hset.insert(8); hset.insert(13); { // Lower bound equal or greater than auto iter = hset.lower_bound(5); assert(*iter == 5); // 5's lower bound is 5 itself in the set } { // Upper bound greater than 5 auto iter = hset.upper_bound(5); assert(*iter == 8); // 5's upper bound is the first value greater than itself } } unordered_set Set that implemented by Hash Table. ...

tags: Sliding Window,Hash Table,LeetCode101 This is an “near by” problem that can be solved by Sliding Window. The k in the problem is somehow means contiguous. And using a HashTable to indicate that two values in the different position are equal. The steps is following: Find two values at each side of window are equal. Return true if the offset between their indices is less than or equal k. Otherwise set left to the new position and continue. class Solution { public: bool containsNearbyDuplicate(vector<int>& nums, int k) { int left = 0; unordered_map<int, int> indices; for (auto right = 0; right < nums.size(); right++) { auto iter = indices.find(nums[right]); if (iter != indices.end()) { if (abs(right - iter->second) <= k) { return true; } left = iter->second + 1; } indices[nums[right]] = right; } return false; } };

tags: Sliding Window,LeetCode101,Hash Table Use HashMap to store counts of letters Two points we should be noticed: The length of substring should be (right - left) + 1, as one side must be counted. We must decrese the number in the counts first, and then slide the left window, or we must decrese the wrong one, please compare between Wrong and Correct. Wrong left++; counts[s[left]]--; Correct counts[s[left]]--; left++; The full code see: ...