Taking Smart Notes With Org-mode
  • About
  • Articles
  • Notes
  • Search
Home » Projects

Data Structures

March 11, 2022 · 1 min · Gray King
  • tags: Computer Systems

Links to this note


    LeetCodeNJ

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

    June 6, 2022 · 1 min · Gray King

    Graph

    tags: Data Structures,Algorithm

    April 27, 2022 · 1 min · Gray King

    Tree

    tags: Data Structures

    March 29, 2022 · 1 min · Gray King

    Binary heap

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

    March 29, 2022 · 1 min · Gray King

    Priority Queue

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

    March 29, 2022 · 1 min · Gray King

    Heap (data structure)

    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.

    March 28, 2022 · 1 min · Gray King

    Monotonic Stack

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

    March 13, 2022 · 1 min · Gray King

    Binary Search Tree

    tags: Data Structures,Binary Tree,Tree

    March 12, 2022 · 1 min · Gray King

    OrderedSet

    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.

    March 12, 2022 · 1 min · Gray King

    Hash Table

    tags: Data Structures

    March 11, 2022 · 1 min · Gray King

    Hash Set

    tags: Data Structures

    March 11, 2022 · 1 min · Gray King

    Stack

    tags: Data Structures

    March 11, 2022 · 1 min · Gray King

    Linked List

    tags: Data Structures

    March 11, 2022 · 1 min · Gray King

    LeetCode101

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

    March 11, 2022 · 1 min · Gray King

    二叉树的遍历

    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; } }; 非递归遍历 【刷题】二叉树非递归遍历 ...

    February 20, 2021 · 1 min · Gray King
© 2025 Taking Smart Notes With Org-mode · Powered by Hugo & PaperMod