Notes

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()); } };

tags: Data Structures

tags: Sliding Window,LeetCode101,Hash Set Use HashMap to store indices See also: 3. Longest Substring Without Repeating Characters class Solution { public: int maximumUniqueSubarray(vector<int>& nums) { int maximum = 0; int left = 0, right = 0; unordered_map<int, int> indices; for (; right < nums.size(); right++) { int n = nums[right]; if (indices.find(n) != indices.end() && indices[n] + 1 > left) { left = indices[n] + 1; } maximum = max(maximum, std::accumulate(nums.begin() + left, nums.begin() + right + 1, 0)); indices[n] = right; } return maximum; } }; It is too slow, as there is a \(O(n^2)\) time complexity(std::accmulate is the embed \(O(n)\) ). ...

tags: Sliding Window source: Moore, Jordan. “An Introduction to Sliding Window Algorithms.” Medium, July 26, 2020. https://levelup.gitconnected.com/an-introduction-to-sliding-window-algorithms-5533c4fe1cc7. Efficientive algorithm: Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away. – Antoine de Saint-Exupéry The following return values can use a sliding window: Minimum value Maximum value Longest value Shortest value K-sized value And contiguous is one of the biggest clues. Common data structures are strings, arrays and even linked lists. ...

tags: Sliding Window,Brute Force Approach source: GeeksforGeeks. “Window Sliding Technique,” April 16, 2017. https://www.geeksforgeeks.org/window-sliding-technique/. Use a Sliding Window to instead Brute Force Approach, improve time complexity big O from \(O(n^2)\) to \(O(n)\).

tags: Algorithm

tags: Algorithm

tags: Sliding Window,Two Pointers source: 力扣 LeetCode. “题解：借这个问题科普一下「滑动窗口」和「双指针」的区别 - 力扣（LeetCode）.” Accessed March 11, 2022. https://leetcode-cn.com/problems/get-equal-substrings-within-budget/solution/jie-zhe-ge-wen-ti-ke-pu-yi-xia-hua-dong-6128z/. https://stackoverflow.com/a/64078338 Two Pointer to slove the problem of two elements that two pointes pointed. Sliding Window to slove the problem of all elements that in the window.

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

tags: Algorithm Slide right to move forward to find the solution. Slide left to keep the solution, and collect to the results. Must avoid left go to backward.

tags: Linked List,Stack, LeetCode101,2. Add Two Numbers 两数之和的进阶版，位高的数字在链表的头部，常规解法是通过「栈」进行反转链表，然后回退到2. Add Two Numbers的解法。

tags: Data Structures

tags: Data Structures

tags: Linked List, LeetCode101 正常的「链表」遍历操作，需要注意的就是不要在末尾忘记处理进位，如果 carry 大于 0 需要追加到结果链表末尾。

tags: Algorithm,Data Structures 又要开始找工作了，刷题、刷题、刷题！步骤： 按顺序找到题目 解题/学习 总结考察的点（树、双指针、回溯、DP、模拟现实、递归） 刷相同解法框架的题 一些模糊的感觉： 尝试不同的遍历顺序可能是解题关键，正序遍历不行试一下反序遍历，反之亦然！ 以上到达一定量之后在 LeetCode 创建一个新的 session 重新刷起。

tags: Computer Systems,Linux source: 262588213843476. “Fork() Is Evil; Vfork() Is Goodness; Afork() Would Be Better; Clone() Is Stupid.” Gist. Accessed March 2, 2022. https://gist.github.com/nicowilliams/a8a07b0fc75df05f684c23c18d7db234.

tags: English Listening Practice source: https://www.youtube.com/channel/UCSHZKyawb77ixDdsGog4iWA

tags: Learning English

物前白 动前土 行动后面双人来

tags: Financial Management,Wealth,English Listening Practice source: Naval. “How to Get Rich,” December 28, 2019. https://nav.al/rich. YouTube: https://www.youtube.com/watch?v=1-TZqOsVCNM

tags: Design

tags: Online Tools,Material Design,Design source: https://material.io/design/color/the-color-system.html#tools-for-picking-colors full: https://material.io/resources/color/#!/?view.left=0&view.right=0&primary.color=b3e4ff

tags: Design,Material Design: Tools for picking colorsMaterial Design source: Material Design. “Material Design.” Accessed February 12, 2022. https://material.io/design/color/the-color-system.html#color-usage-and-palettes. Principles Hierarchical Color indicates which elements are interactive, how they relate to other elements, and their level of prominence. Important elements should stand out the most. Legible Text and import elements, like icons, should meet legibility standards when appearing on colored backgrounds. Expressive Show brand colors at memorable moments that reinforce your brand’s style. ...

tags: GUI,GTK source: “Text Widget Overview.” Accessed February 9, 2022. https://docs.huihoo.com/gtk/3.0.3/TextWidget.html. GtkTextBuffer for the text to edit. GtkTextIter to manipulate text, can’t be used to preserve positions across buffer modifications GtkTextMark can be used to preserve a position. GtkTextView to show GtkTextBuffer. GtkTextTagTable to control the appearence of text, like bold/color/etc.

tags: Rust GUI,Elm,GTK