tags: Algorithm,Two Pointers

tags: Algorithm,Linked List,Fast & Slow Pointers source: https://en.wikipedia.org/wiki/Cycle%5Fdetection Floyd’s tortoise and hare With two pointers: tortoise move slow: move 1 step in each loop. hare move fast: move 2 steps in each loop. If there is a circle existed, tortoise and hare will meet eventually in the circle. Now both tortoise and hare are in the circle, how to figure out the beginning of the circle? We put tortoise back to the beginning they both started. Such as, the first element of the linked list. Then we move both tortoise and hare step by step, they will meet in the beginning of the circle.

tags: Data Structures

tags: Tree

tags: Binary Tree,Tree A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.

tags: Heap (data structure),Data Structures,Complete Binary Tree,Tree source: https://en.wikipedia.org/wiki/Binary%5Fheap Binary tree with two additional constraints: Shape property: complete binary tree. Heap property: the key stored in each node is greater or equal(max-heaps) to or less than or equal to(min-heaps) the keys in the node’s children, according to some total order. Heap operations Insert Steps to add an element to a heap: Add element to the bottom level of the heap at the leftmost open space. Compare to its parent, if they are in the correct the order, stop. If not, swap element with its parent and return to the previous step. Extract: Delete the root from heap Replace the root of heap with the last element on the bottom level. Compare the new root with its children; if they are in the correct order, stop. If not, swap the element with one of its children and return to the previous step. Search Delete Decrease or increase key Heap implementation with array each element a at index i has ...

tags: Priority Queue,LeetCode101 Max heap priority queue class Solution { public: int findKthLargest(vector<int>& nums, int k) { // max heap priority_queue<int> pq; for (auto iter = nums.begin(); iter != nums.end(); ++iter) { pq.push(*iter); } // The Kth largest element should let k > 1 not k > 0 for (; k > 1; --k) { pq.pop(); } return pq.top(); } };

tags: Priority Queue,LeetCode101 The key ideas: Use a std::pair to hold {count, index}, so it can compare count first then the index. Use a min heap priority queue to get the K weakest rows. class Solution { public: vector<int> kWeakestRows(vector<vector<int>>& mat, int k) { // min heap priority_queue< std::pair<int, int>, vector<std::pair<int, int> >, std::greater<std::pair<int, int> > > pq; for (auto iter = mat.begin(); iter != mat.end(); ++iter) { int c = count((*iter).begin(), (*iter).end(), 1); pq.push({c, iter - mat.begin()}); } vector<int> ret; for (; k > 0; --k) { ret.push_back(pq.top().second); pq.pop(); } return ret; } };

tags: Data Structures,Heap (data structure) The priority queue is solved: The K smallest/largest/weakest X.

tags: Learning English,读书笔记 source: Joseph Devlin. How to Speak and Write Correctly, 2007. http://archive.org/details/how_to_speak_and_write_correctly_librivox. I found this book in my Kindle on the subway to work this morning. And remembered that I downloaded it free from the Kindle store years ago. For some reasons, maybe my English was not good enough to read it, I haven’t read it yet. After read a little, I think it’s prefect for me for now. The reasons is: ...

tags: Data Structures,Tree WHAT is a heap? Tree-based data structure which is essentially an almost complete tree that statifies the heap property. Max heap For any given node C, if P is a parent node of C, then the key(the value) of P is greater than or equal to the key of C. Min heap The P is less than or equal to the key C. When to use a heap? Priority queue. Heapsort.

tags: Algorithm

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,backtracking,LeetCode101 Backtracking and stack overflow Intuition: We can abstract all the operations to a Tree, then apply DFS on it. For example: startValue=2, target=3, the tree looks like: /* 2 /\ / \ / \ 1(-1) 4(x2) /\ /\--+ / \ / \ 0(-1) 2(x2) 3(-1) 8(x2) */ class Solution { public: int brokenCalc(int startValue, int target) { unordered_set<int> visited; return backtracking(0, startValue, target, visited); } int backtracking(int count, int val, int target, unordered_set<int> & visited) { if (val == target) { return count; } if (visited.find(val) != visited.end()) { return -1; } int left = -1, right = -1; count++; visited.insert(val); if (val > 0) { left = backtracking(count, val - 1, target, visited); } if (val <= target * 2) { right = backtracking(count, val * 2, target, visited); } visited.erase(val); if (left != -1 && right != -1) { return min(left, right); } else if (left != -1) { return left; } return right; } }; Change target to startValue class Solution { public: int brokenCalc(int startValue, int target) { int r = 0; while (target > startValue) { target = target % 2 > 0 ? target + 1 : target / 2; r++; } return r + startValue - target; } };

tags: String,LeetCode101,Tricky Initialize a string that fills 'a' in it. Then we turn it to the expected string from end to start. The maximal value of each position in the string is 26. If we start from all elements is 'a' in the string. Then the represent value of the string is n. If it’s not equal to k. Then we need turn the last character of string to r = k - n. Two cases must be handled: ...

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: Two Pointers,Tricky,LeetCode101 The key ideas are: We start from two edges and move to the middle with two pointers. Move the pointer to the middle which side is smaller. class Solution { public: int maxArea(vector<int>& height) { int i = 0, j = height.size() - 1; int water = 0; while (i < j) { water = max(water, (j - i) * min(height[i], height[j])); if (height[i] > height[j]) { --j; } else { ++i; } } return water; } };

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: Algorithm

tags: LeetCode101,Math The key idea is: To use \(log10(10^n) = n\) to get how many digits in the number. Then we need iterate \(n + 1\) times to compare each side. The digit in the left is \(\frac{x}{10^{n-i}} \mod 10\). The digit in the right is \(\frac{x}{10^i} \mod 10\). class Solution { public: bool isPalindrome(int x) { if (x < 0) { return false; } // failed at here if (x < 10) { return true; } int n = log10(x); int ld = pow(10, n); // left div int rd = 1; // right div for (int i = 0; i < (n + 1) / 2; i++) { // left right if (x / ld % 10 != x / rd % 10) { return false; } ld /= 10; rd *= 10; } return true; } };

tags: Algorithm

tags: C/C++ In some problems, we need to detect is our result overflow in a 32-bit integer. The key ideas is check our value before it becomes bigger. For example: // INT_MAX 2147483647 // INT_MIN -2147483648 // INT_MAX's suffix is 7 if (res > INT_MAX / 10 || (res == INT_MAX / 10 && pop > 7)) { return 0; } // INT_MIN's suffix is -8 if (res < INT_MIN / 10 || (res == INT_MIN / 10 && pop < -8)) { return 0; } res = res * 10 + pop; Our final result need a 10 times current value and plus a value, then we check: ...

tags: Tricky,LeetCode101,Integer Overflow The key idea is how to detect integer overflow, it’s same to: LeetCode101: 7. Reverse Integer. class Solution { public: int myAtoi(string s) { auto iter = s.begin(); int base = 1, r = 0, p = 0; // Skip whitespace for (; iter != s.end() && *iter == ' '; ++iter) { } // negative or positive if (*iter == '-' || *iter == '+') { if (*iter == '-') { base = -1; } ++iter; } for (; iter != s.end(); ++iter) { // failed at here: the logic between conditions is OR not AND if (*iter > '9' || *iter < '0') { break; } p = (*iter - '0') * base; // 7 is the INX_MAX's suffix, remember? if (r > INT_MAX / 10 || (r == INT_MAX / 10 && p > 7)) { return INT_MAX; } // 8 is the INT_MIN's suffix, too. if (r < INT_MIN / 10 || (r == INT_MIN / 10 && p < -8)) { return INT_MIN; } r = r * 10 + p; } return r; } };

tags: Tricky,LeetCode101 Make R = total required rows d = R - 2 2 is contains head line and tail line that not need insert a character between two columns. r = current row offset, which starts from 0. c = current column offset, which starts from 0. We can use a formula to make columns, which is \(c(R+d)+r\). For example, "PAYPALISHIRING", numRows=3: P A H N A P L S I I G Y I R The columns only the head and tail rows is correct should be: ...

tags: Tricky,Stack,LeetCode101,Integer Overflow The key is how to detect integer overflow without store to a larger size integer. For this purpose, we could detect integer overflow before carry: The maximal of INT_MAX before carry is \(\frac{INT\_MAX}{10}\). We continue compare pop with the suffix of INT_MAX, 7, if maximal before carry is equal to \(\frac{INT\_MAX}{10}\). The minimal of INT_MIN before carry is \(\frac{INT\_MIN}{10}\) too. We continue compare pop with the suffix of INT_MIN, -8, if minimal before carry is equal to \(\frac{INT\_MIN}{10}\). ...

tags: Stack Intuition for (int i = 0; i < pushed.size(); i++) { if (pushed[i] != popped[pushed.size() - 1 - i]) { return false; } } But the pop/push operations can happend in any sequence. Stack Using a stack. Returns false, IF the next value neither the popped nor pushed. In each sequence we must do a operation: push or pop. When to push: stack is empty, or top of stack is not current popped value When to pop: ...

tags: Stack,LeetCode101 Stack class Solution { public: string minRemoveToMakeValid(string s) { stack<char> st; char open = '(', close = ')'; int open_count = 0; string res; // forward to remove unnecessary close parentheses for (auto iter = s.begin(); iter != s.end(); ++iter) { if (*iter == open) { open_count++; } if (open_count == 0 && *iter == close) { continue; } if (*iter == close) { open_count--; } st.push(*iter); } int close_count = 0; // backward to remove unnecessary open parentheses while (!st.empty()) { if (st.top() == close) { close_count++; } if (st.top() == open) { if (close_count == 0 ) { st.pop(); continue; } close_count--; } res.push_back(st.top()); st.pop(); } reverse(res.begin(), res.end()); return res; } };

tags: Tricky,LeetCode101 original: 0, 2, 1, 4, 3, 5, 7, 6 max: 0, 2, 2, 4, 4, 5, 7, 7 sorted: 0, 1, 2, 3, 4, 5, 6, 7 index: 0, 1, 2, 3, 4, 5, 6, 7 As shown above, the position of break point is same to the position of max value of chunks. So here: ...

tags: Algorithm

tags: Monotonic Stack,LeetCode101,LeetCode101: 496. Next Greater Element I Mono-descreasing stack class Solution { public: vector<int> dailyTemperatures(vector<int>& temperatures) { vector<int> res(temperatures.size(), 0); stack<int> st; for (int i = 0; i < temperatures.size(); i++) { while (!st.empty() && temperatures[st.top()] < temperatures[i]) { res[st.top()] = i - st.top(); st.pop(); } st.push(i); } return res; } }; [73,74,75,71,69,72,76,73]

tags: Monotonic Stack,LeetCode101,Binary Search Tree Mono-descreasing stack Key: The largest number is the root, that we can observe in by iteration. We must clear the stack to fill the right side of BST after loop. The last popped element is the left of current node. From top to bottom, the top element is the right side of the element that under the top. class Solution { public: TreeNode* constructMaximumBinaryTree(vector<int>& nums) { vector<TreeNode*> res(nums.size(), nullptr); stack<int> st; // mono-descreasing stack, remove smaller elements before pushing. TreeNode* root = nullptr; for (int i = 0;i < nums.size(); i++) { res[i] = new TreeNode(nums[i]); while (!st.empty() && nums[st.top()] < nums[i]) { int j = st.top(); st.pop(); if (!st.empty() && nums[st.top()] < nums[i]) { res[st.top()]->right = res[j]; } else { res[i]->left = res[j]; } } if (root == nullptr || res[i]->val > root->val) { root = res[i]; } st.push(i); } while (st.size() > 1) { int j = st.top(); st.pop(); res[st.top()]->right = res[j]; } return root; } };

tags: Monotonic Stack,LeetCode101 Mono-increasing stack Key: Some case should move backward as the new value we meeted is larger than it. When we meet 2 in the stack, and here we need move backward. Some case we need move forward, as the following values are the mono-increaing stack: [1, 2, 5, 3, 4] class Solution { public: int findUnsortedSubarray(vector<int>& nums) { stack<int> st; // mono-increasing int left = -1, right = -2; for (int i = 0; i < nums.size(); i++) { while (!st.empty() && nums[st.top()] > nums[i]) { // move backward if (left == -1 || st.top() < left) { left = st.top(); // left should be the previous index } // move forward for (int j = i; j < nums.size() && nums[j] < nums[st.top()]; j++) { if (j > right) { right = j; } } st.pop(); } st.push(i); } return (right - left) + 1; } }; Failed test cases [2,6,4,8,10,9,15] [1, 2, 3, 4] [1] [2,1] [1,3,2,2,2] [1,2,3,3,3] [2,3,3,2,4] [1,2,5,3,4] [1,3,5,2,4]

tags: Monotonic Stack,LeetCode101 related: LeetCode101: 496. Next Greater Element I Mono-descreasing stack / normal order loop twice Loop twice to solve circular interger array Mono-descreasing stack to store index, avoid HashMap in Next Greater Element I, as there is a cicular array. class Solution { public: vector<int> nextGreaterElements(vector<int>& nums) { vector<int> res(nums.size(), -1); stack<int> st; for (int j = 0, i = 0; j < nums.size() * 2; ++j) { i = j >= nums.size() ? j - nums.size() : j; while (!st.empty() && nums[st.top()] < nums[i]) { res[st.top()] = nums[i]; st.pop(); } st.push(i); } return res; } };

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: Monotonic Stack,LeetCode101 Mono-increasing stack and reverse order travel (Not Work) Notes: We attempt to remove the most large numbers in the left, first, we use the right n numbers to meet the requirements, which is num.length - k and then, using a monotonic increasing stack to keep the result as samller as we can. (A monotonic increasing stack will remove larger elements before pushing.) Also note that: the result’s length is not actually equal num.length - k, it’s less than or equal num.length - k, like num = “10200”, k = 1. Which means the result in stack could be longer than the required or leading ‘0’. ...

tags: Monotonic Stack,LeetCode101,Tricky We travel the numbers in the reverse order: Use a mono-increasing stack to find the largest number(3 in the 132 pattern), the value popped from stack is the second large number(2 in the 132 pattern), if any value less than the second large number, returns true. // Note: // // - subsequence is not contiguous, is i < j < k, not i + 1 = j, j + 1 = k // class Solution { public: bool find132pattern(vector<int>& nums) { int K = INT_MIN; stack<int> mst; // mono-increasing stack for (int i = nums.size() - 1; i >= 0; i--) { if (nums[i] < K) { return true; } while (!mst.empty() && mst.top() < nums[i]) { K = mst.top(); mst.pop(); } mst.push(nums[i]); } return false; } };

tags: Data Structures,Stack source: “Monotonic Stack.” Accessed March 13, 2022. https://liuzhenglaichn.gitbook.io/algorithm/monotonic-stack. A monotonic stack is a stack whose elements are monotonically increasing or descreasing. It’s not only about the order in the stack, it’s also about remove larger/smaller elements before pushing. Monotonically descreasing we need to pop smaller elements from the stack before pushing a new element: vector<int> nums; // fill nums stack<int> st; for (auto i = nums.size() - 1; i >= 0; i--) { while (!st.empty() && st.top() > nums[i]) { st.pop(); } st.push(nums[i]) } To push 3 to [5, 4, 2, 1], we need pop 2, 1 out first. Then the stack become [5, 4, 3] Monotonically increasing vice versa. ...

tags: Binary Search Tree,Binary Tree,Tree

tags: Data Structures,Binary Tree,Tree

tags: Binary Search Tree, AVL Tree,Tree

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

tags: Sliding Window,LeetCode101 Key: sum is greater than or equal to target Compute minimal must above slide left window, as decrease may cause sum less than target. See also 1695. Maximum Erasure Value class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int left = 0; int sum = 0; int minimal = INT_MAX; for (auto right = 0; right < nums.size(); right++) { sum += nums[right]; while (sum >= target) { minimal = min(minimal, right - left + 1); sum -= nums[left++]; } } return minimal == INT_MAX ? 0 : minimal; } };

tags: Sliding Window,LeetCode101,Hash Set Key: Fixed size window, right should start from 9 class Solution { public: vector<string> findRepeatedDnaSequences(string s) { int left = 0; unordered_set<string> results; unordered_set<string> hset; for (auto right = 9; right < s.size(); right++) { string sub(s, left, 10); if (hset.find(sub) != hset.end()) { results.insert(sub); } hset.insert(sub); left++; } return vector<string>(results.begin(), results.end()); } };