Notes

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: C/C++,Java,Data Structures In C++ the set container is an ordered or sorted set, unordered_set is the normal set in C++. Differences between them please check set vs unordered_set in C++ STL. In Java there is an java.util.SortedSet interface.

tags: Sliding Window,OrderedSet Use HashSet to attempt to meet the requirements in the window class Solution { public: bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) { auto left = 0; auto K = 0; set<long> hset; // set in cpp is an sorted set for (auto right = 0; right < nums.size(); right++) { K = right - left; if (K > k) { hset.erase(nums[left]); left++; } hset.insert(nums[right]); // some numbers are the same. if (hset.size() < (right - left + 1)) { return true; } // abs less than or equal t auto prev = hset.begin(); for (auto iter = hset.begin(); iter != hset.end(); iter++) { if (iter != prev && abs(*prev - *iter) <= t) { return true; } prev = iter; } } return false; } }; // 1. find previous value that meet the requirement, which is abs(nums[i] - nums[j]) <= t // 2. See if also meet the requirement, which is abs(i - j) <= k, otherwise slide left // // Use a fixed window, which size is ~k~. And maintain a set of numbers in the window. // To check if there numbers meet the requirement. It’s too slow and got “Time Limit Exceeded”: https://leetcode.com/submissions/detail/658425251/testcase/. In this case the t is 0, so we can avoid the embed for loop with a if condition: ...

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: Data Structures