📄️ 10.1 C++ STL
When solving problems, we almost always rely on various data structures to assist us. Therefore, we must familiarize ourselves with the characteristics of each data structure. C++ STL provides several data structures (the actual underlying implementation may vary depending on the compiler):
📄️ 10.2 Python Common Data Structures
Similar to C++ STL, Python also provides various data structures (the underlying details may vary depending on the implementation):
📄️ 10.3 Arrays
448. Find All Numbers Disappeared in an Array
📄️ 10.4 Stacks and Queues
232. Implement Queue using Stacks
📄️ 10.5 Monotonic Stack
Monotonic Stack is a technique that maintains the monotonic increasing (or decreasing) property of a stack to solve comparison problems in $O(n)$ time complexity.
📄️ 10.6 Priority Queue
Priority queue allows retrieving the maximum value in $O(1)$ time and inserting or removing the maximum value in $O(\log n)$ time.
📄️ 10.7 Double-Ended Queue
239. Sliding Window Maximum
📄️ 10.8 Hash Table
A hash table (also known as a hash map) uses $O(n)$ space complexity to store data. By leveraging a hash function, it maps positions to achieve approximate $O(1)$ time complexity for insertion, lookup, and deletion operations. Hash tables can be utilized for tasks such as frequency counting and content recording.
📄️ 10.9 Multisets and Mappings
332. Reconstruct Itinerary
📄️ 10.10 Prefix Sum and Integral Image
A one-dimensional prefix sum (cumulative sum, cumsum) and a two-dimensional integral image (summed-area table, image integral) are techniques used to precompute the sums of one-dimensional segments or two-dimensional rectangles up to each position. This allows for faster calculations and queries. If you need to index values from the prefix sum or integral image, they can be stored in a hash table. If you need to record values for each position, they can be stored in one-dimensional or two-dimensional arrays, often in conjunction with dynamic programming.
📄️ 10.11 Exercises
Basic Difficulty