Data Structure (数据结构)

[ylqi007]

Queue (队列)

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

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

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

1. 顺序存储

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

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

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

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

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

2. 链式存储

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

Reference

• 队列（Queue）：“先进先出”的数据结构
• 链表
• https://www.falkhausen.de/Java-8/java.util/Collection-Hierarchy.html

[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]

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]

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

• Leetcode面试高频题分类刷题总结

[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]
      • 160. Intersection of Two Linked Lists [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
   • 【算法面试通关40讲】18 - 面试题：验证二叉搜索树

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]

Trie

1. 14. Longest Common Prefix