LeetCode icon indicating copy to clipboard operation
LeetCode copied to clipboard

Published 20 hours ago • verified publisher icon ylqi007

Data Structure (数据结构)

Open ylqi007 opened this issue 2 years ago • 5 comments

Queue (队列)

Queue是线性表的一种，在操作数据元素时，按照先进先出(First In First Out, FIFO)的规则。

Queue的实现方式: 队列的实现同样有两种方式：顺序存储和链式存储。两者的区别在于数据元素在物理存储结构上的不同。

  1. 顺序存储
  2. 链式存储

1. 顺序存储

顺序存储存在的问题: 由于数组申请的空间有限，到某一时间点，就会出现rear队尾指针到了数组的最后一个存储位置，如果继续存储，由于rear指针无法后移，则会出错。

在数组中做删除数据元素的操作，只是移动了队头指针而没有释放所占空间。

顺序存储的升级版：使用数组存取数据元素时，可以将数组申请的空间想象成首尾连接的环状空间使用。

如何区分空队列和满队列的情况？办法是：牺牲掉一个存储空间

  • 当队列为空时，尾指针rear等于头指针front
  • 当队列为满时，为指针rear的下一个位置等于头指针front

2. 链式存储

队列的链式存储是在链表的基础上，按照“先进先出”的原则操作数据元素。

Reference

ylqi007 avatar Nov 22 '23 07:11 ylqi007

PriorityQueue (Heap, 堆)

  1. 215. Kth Largest Element in an Array
  2. 767. Reorganize String
  3. 239. Sliding Window Maximum
  4. 253. Meeting Rooms II
  5. 632. Smallest Range Covering Elements from K Lists
  6. 347. Top K Frequent Elements
  7. 23. Merge k Sorted Lists
  8. 2551. Put Marbles in Bags
  9. 2402. Meeting Rooms III
  10. 420. Strong Password Checker

ylqi007 avatar Nov 23 '23 21:11 ylqi007

Stack

  1. 20. Valid Parentheses
    1. 71. Simplify Path
    2. 20 & 71都是比较简单、直接的Stack问题。
  2. 42. Trapping Rain Water
    1. 84. Largest Rectangle in Histogram
    2. 85. Maximal Rectangle
    3. 42，84，85可以用相同的思路解决
  3. 880. Decoded String at Index
  4. 2030. Smallest K-Length Subsequence With Occurrences of a Letter
  5. 316. Remove Duplicate Letters
    1. This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/
  6. 1249. Minimum Remove to Make Valid Parentheses
  7. 2751. Robot Collisions
  8. Stack -- Basic Calculator
    1. 227. Basic Calculator II [+, -, *, /]
    2. 224. Basic Calculator [非常好的Stack题目, with parenthesis, +, - and (, )]
    3. 772. Basic Calculator III [With parenthesis, +, -, *, / and (, )]
    4. Basic Calculator Template
  9. 84. Largest Rectangle in Histogram
  10. 394. Decode String
    1. 71. Simplify Path
    2. 150. Evaluate Reverse Polish Notation
  11. 735. Asteroid Collision
  12. 234. Palindrome Linked List
  13. 456. 132 Pattern
  14. 155. Min Stack
  15. 1472. Design Browser History
  16. 2030. Smallest K-Length Subsequence With Occurrences of a Letter
  17. 143. Reorder List
    1. 876. Middle of the Linked List
    2. 206. Reverse Linked List
    3. 21. Merge Two Sorted Lists
  18. 1762. Buildings With an Ocean View
  19. 234. Palindrome Linked List
  20. 844. Backspace String Compare
  21. 739. Daily Temperatures
    1. 496. Next Greater Element I

Monotonic Stack

https://leetcode.com/tag/monotonic-stack/ A monotonic stack is simply a stack where the elements are always in sorted order. A monotonic stack is a stack in which the elements are always sorted. A stack can be monotonically increasing (sorted ascending) or monotonically decreasing (sorted descending).

  1. 739. Daily Temperatures
  2. 901. Online Stock Span

ylqi007 avatar Dec 02 '23 07:12 ylqi007

LinkedList

  1. 146. LRU Cache
  2. 2. Add Two Numbers
  3. 21. Merge Two Sorted Lists
  4. 138. Copy List with Random Pointer
  5. 1472. Design Browser History

ylqi007 avatar Dec 18 '23 00:12 ylqi007

Tree

  1. Binary Tree Traversal
    1. 314. Binary Tree Vertical Order Traversal
    2. 102. Binary Tree Level Order Traversal
    3. How to traverse a tree? https://leetcode.com/problems/binary-tree-level-order-traversal/editorial/
  2. Lowest Common Ancestor (最近公共祖先)
    1. 235. Lowest Common Ancestor of a Binary Search Tree
    2. 236. Lowest Common Ancestor of a Binary Tree
    3. 1644. Lowest Common Ancestor of a Binary Tree II
    4. 1650. Lowest Common Ancestor of a Binary Tree III [Two Pointers]
    5. 1676. Lowest Common Ancestor of a Binary Tree IV [DFS+Set]
  3. Path Sum
    1. 112. Path Sum
    2. 113. Path Sum II
      1. 257. Binary Tree Paths
    3. 437. Path Sum III
      1. Prefix Sum: https://leetcode.com/problems/path-sum-iii/editorial/
      2. Recursive preorder traversal: https://leetcode.com/problems/sum-root-to-leaf-numbers/editorial/
    4. 666. Path Sum IV
  4. 1361. Validate Binary Tree Nodes
  5. 515. Find Largest Value in Each Tree Row [Level traversal]

Others

  1. 863. All Nodes Distance K in Binary Tree
    1. 2385. Amount of Time for Binary Tree to Be Infected
  2. 1361. Validate Binary Tree Nodes [UnionFind]

Depth

  1. :white_check_mark: 104. Maximum Depth of Binary Tree, [DFS is better，因为要traverse到最底层的leaf]
  2. :white_check_mark: 111. Minimum Depth of Binary Tree [BFS is better, 因为只要遇到最早的leaf，就可以提前返回]
    1. 在LC 104中，要求解的是最大depth，要遍历所有的path才能知道最大的depth，因此DFS是更好的求解思路。
    2. 而在LC 111中，要求解的是最小depth，只要逐层遍历，遇到最早的叶子节点时，就是遇到了最小的depth，因此用BFS逐层遍历会更好。
  3. 110. Balanced Binary Tree
    1. LC 110其实就是在LC 104的基础上的变形。用DFS + early return
  4. 559. Maximum Depth of N-ary Tree
    1. LC 559就是在LC 104的基础上把两个子节点扩展成了多个子节点。
    2. ⚠️ DFS的终止条件!!!

Others

  1. 894. All Possible Full Binary Trees
    • Recursion + Memorization, 有点像Fibonacci

1. 二叉树(BT)遍历

以下前四种traversal都有recursion和iteration两种写法

  1. 144. Binary Tree Preorder Traversal [DFS]
  2. 94. Binary Tree Inorder Traversal [DFS]
  3. 145. Binary Tree Postorder Traversal [DFS]
  4. 102. Binary Tree Level Order Traversal [BFS]
  5. 314. Binary Tree Vertical Order Traversal [DFS, BFS]

2. 验证二叉搜索树(BST)

  1. 98. Validate Binary Search Tree
  2. 94. Binary Tree Inorder Traversal
  3. 501. Find Mode in Binary Search Tree

3. 二叉树&二叉搜索树的最近公共祖先

  1. :exclamation:236. Lowest Common Ancestor of a Binary Tree [p or q can be null]
    1. 235. Lowest Common Ancestor of a Binary Search Tree [BST的特点: left.val < root.val < right.val]
  2. :exclamation:1644. Lowest Common Ancestor of a Binary Tree II [p or q cannot be null]
  3. :exclamation:1650. Lowest Common Ancestor of a Binary Tree III [Both p and q exist. Two Pointers]
  4. 1676. Lowest Common Ancestor of a Binary Tree IV

ylqi007 avatar Dec 23 '23 07:12 ylqi007

Trie

  1. 14. Longest Common Prefix

ylqi007 avatar Jan 07 '24 05:01 ylqi007