Data Structures

tags: Algorithm,Data Structures Make my best effort to move to Nanjing for my son. This is a successor of LeetCode101.

tags: Data Structures,Algorithm

tags: Data Structures

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: Data Structures,Heap (data structure) The priority queue is solved: The K smallest/largest/weakest X.

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: 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: Data Structures,Binary Tree,Tree

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

tags: Data Structures

tags: Data Structures

tags: Data Structures

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

tags: Algorithm,Data Structures,Binary Search Tree 分为三种：前序、后序和中序，其中最容易用栈改写的是后序。 前序(Preorder)：Root -> Left -> Right class Solution { public: void processPreorderTraversal(TreeNode* root, vector<int> & collector) { if (root == nullptr) { return; } processPreorderTraversal(root->left, collector); collector.push_back(root->val); processPreorderTraversal(root->right, collector); } vector<int> inorderTraversal(TreeNode* root) { vector<int> ret; if (root == nullptr) { return ret; } processPreorderTraversal(root, ret); return ret; } }; 中序(Inorder): Left -> Root -> Right class Solution { public: void processInorderTraversal(TreeNode* root, vector<int> & collector) { if (root == nullptr) { return; } processInorderTraversal(root->left, collector); collector.push_back(root->val); processInorderTraversal(root->right, collector); } vector<int> inorderTraversal(TreeNode* root) { vector<int> ret; if (root == nullptr) { return ret; } processInorderTraversal(root, ret); return ret; } }; 后序(Postorder)：Left -> Right -> Root class Solution { public: void processPostorderTraversal(TreeNode* root, vector<int> & collector) { if (root == nullptr) { return; } processPostorderTraversal(root->left, collector); processPostorderTraversal(root->right, collector); collector.push_back(root->val); } vector<int> postorderTraversal(TreeNode* root) { vector<int> ret; if (root == nullptr) { return ret; } processPostorderTraversal(root, ret); return ret; } }; 非递归遍历 【刷题】二叉树非递归遍历 ...