Nodes connected to each other in the form of a network

vertex: node

Edge: edge, a pair of nodes

weight/cost

directed graph

Undirected graph

adjacency matrix

adjacency list

Breadth First Search DFS

Depth First Search TFS

Implement breadth and depth first search

Check if the graph is a tree

Count the number of edges in a graph

Find the shortest distance between two vertices

Also known as: prefix tree, a special tree-like data structure

Very effective in solving string related problems

Provide quick search

Search a word in a dictionary

Automatic suggestions in search engines

Routing for IP

Count the total number of words in the dictionary tree

Print all words stored in dictionary tree

Sort elements in an array using a dictionary tree

Form words from a dictionary using a dictionary tree

Build T9 dictionary: Dictionary tree DFS

Store uniquely identified objects in the form of key-value pairs

Dictionary: a collection of key-value pairs

Search object value using key key

HashSet/HashMap in Java, unordered_map in C, dict in Python

<br>Working principle: For set. The key gets an index through the hash function, and then the value is stored in the array. <br>For get, find the index through the key and hash functions and get the value.

The key can be a string, an integer, or something of unknown length. Therefore, it is appropriate to use O(L); in a strict sense, the time complexity of any operation is O(keySize) rather than O(1)<br>

128 Hash functions

Collision means that two different keys obtain two identical values ​​after calculation by the hash function. There are two main ways to resolve conflicts:<br>Open Hashing. It means that in the array on which the hash table is based, each position is the head node of a Linked List. In this way, conflicting <key, value> tuples are placed in the same linked list. <br>Closed Hashing. It means that when a conflict occurs, the subsequent elements will go to the next position to find an empty space<br>

129 rehash

Hash function

Hash table size

Collision handling method

Find symmetric key-value pairs in an array

Will the hash table be used flexibly to solve the problem?

Are you proficient in the basic principles of hash tables?

Track the complete path for convenience

Find if an array is a subset of another array

Checks whether the given arrays are disjoint

526. Load Balancer<br>

134. LRU cache strategy<br>657. Insert Delete GetRandom O(1)<br>954. Insert Delete GetRandom O(1) - Duplicates allowed<br>209. The first character that appears only once

Data Stream class problems<br>960. First Unique Number in a Stream II<br>138. Sum of subarrays<br>105. Copying a linked list with random pointers<br>171. Out-of-order string<br>124. longest continuous sequence

insertion sort

Quick sort

selection sort

merge sort

Radix sort

Heap sort

static lookup table

dynamic lookup table

Hash table

Algorithm 1:O(n) lowerBound O(1) add

Algorithm 2:O(logn) lowerBound O(logn) add

one-dimensional array

Two-dimensional array

Multidimensional Arrays

subarray

Array interval problem

external sorting problem

Bit operations

Tree arrays are rarely considered

increase get

delete delete

insert insert,

size size

Find the second smallest element in an array

Find the first non-repeating integer

Rearrange positive and negative values ​​in an array

65. Median of two sorted arrays, difficult problem<br>

6. Merge Sorted Arrays II<br>64. Merge Sorted Arrays<br>839. Merge two sorted interval lists<br>486. Merge K Sorted Arrays<br>577. Merge K sorted interval lists<br>547 . Intersection of two arrays<br>548. Intersection of two arrays II<br>793. Intersection of multiple arrays<br>654. Sparse matrix multiplication<br>931. Median of K Sorted Arrays<br>149. Buying and selling stocks The best time<br>405. Submatrix whose sum is zero<br>944. Maximum Submatrix<br>943. Range Sum Query - Immutable<br>665. Plane Range Sum-Immutable Matrix<br>840. variable range summation

LIFO. For example, in logistics loading, the goods loaded later are unloaded first.

Used for non-recursive traversal of binary trees, computing reverse Polish expressions, etc.

The main data structure of non-recursive implementation of DFS

In breadth-first search (BFS), the nodes to be expanded are recorded.

Queues can be used to implement message queues to complete asynchronous tasks.

When the speed of message production and consumption is inconsistent, a message queue is needed to temporarily store messages that have been sent but not received.

Use a storage structure (commonly used arrays, occasionally linked lists) to store elements

Use one array to implement three stacks?

Implement a stack using two queues? <br>

the difference

Exercises<br>

push, insert element at the top

pop returns and removes the top element of the stack

isEmptyThe stack is empty and returns true

top returns the top element without removing it

Java uses java.util.Stack, which extends from the Vector class and supports operations such as push(), pop(), peek(), empty(), and search().

C, just use the stack in <stack>. The method is similar to Java, except that peek() in C is called top(), and when pop(), the return value is empty.

Python, use list directly, use slicing operations like [-1] to view the top of the stack, use list.pop() when popping the top of the stack, and use list.append() when pushing the top of the stack. <br>

Using the stack to evaluate postfix expressions

Sort the elements of the stack

Determine whether an expression is parenthetically balanced

FIFO first-in first-out sequential storage linear data structure, supermarket checkout

Used as the main data structure for the BFS algorithm

Insert elements at the end of the enqueue queue

dequeue removes the head element of the queue

isEmpty column is empty and returns true

top returns the first element of the queue

Implement queue using linked list?

Implement a queue with two stacks? <br>

Implement queue using circular array?

Use queue to represent stack

Reverse the first k elements of the queue

Use a queue to generate binary numbers from 1 to n

642. Moving Average from Data Stream<br>

955. Implement Queue by Circular Array<br>

Node chain: each node contains data and pointers to subsequent nodes

Implement file system, hash table, adjacency list

one-way linked list

Doubly linked list

insertAtEnd

insertAtHead

Delete

DeleteAtHead

Search

isEmpty, is empty, returns true

Reverse linked list

Detect cycles in linked lists

Returns the nth node from the last in the linked list

Remove duplicates from linked list

hierarchical data structure

Made up of vertices and edges

There are no cycles in the tree as shown in the graph

root root node

parentparent node

child child node

leaf node

sibling sibling node

N-ary tree

Line segment trees are basically not tested, they are universal.

Binary tree, often tested

Find the height of a binary tree

Find the kth maximum value in a binary search tree

Find the node that is distance k from the root node

Find the ancestor nodes of a given node in a binary tree

104. Merge K Sorted Lists<br>