Wondershare EdrawMind
Mindmap-Galerie Data Structures and Algorithms
- 14
Data Structures and Algorithms
This mind map about data structures and algorithms covers complexity analysis, binary trees, dynamic programming, sorting, recursion, binary search, and linear structures. I hope this mind map will be helpful to you.
Bearbeitet um 2023-02-14 16:38:07
- Für Sie empfohlen
- Gliederung
Data Structures and Algorithms
Complexity analysis
Indicates the performance of the algorithm in the two dimensions of time and space as the data scale changes, expressed as O(), the lower the value in brackets, the better
time complexity
The relationship between operation process and data size
For example, if the algorithm has a loop indicating that all data must be traversed once, the event complexity is O(n)
If it is a two-level loop, all data needs to traverse both sides, and the time complexity is O(n^2)
space complexity
It mainly depends on the relationship between the additional data structures introduced to solve the problem and the size of the test set data.
Introducing the traversal of constant basis, the space complexity is O(1)
Introducing a data structure with the same size as the data, such as a set, the space complexity is O(n)
You can't have your cake and eat it too, and the same goes for time and space. Usually, space is sacrificed for events, or time is sacrificed for space.
Binary tree
A binary tree is a tree structure in which each node has at most two subtrees. The subtrees are usually called "left subtree" and "right subtree".
Binary tree traversal
Preorder traversal root -> root.left -> root.right
In-order traversal: root.left -> root -> root.right
Postorder traversal: root.left -> root.right -> root
You can see that the X order is determined by the position of the root node. The root in front is the preorder, and the root in the middle is the inorder... and the order of the child nodes is from left to right.
layer traversal
Layer-by-layer traversal is a breadth-first algorithm
Breadth-first search is a traversal search algorithm widely used in trees and graphs.
The algorithm starts with a root node and first visits the node itself. Then traverse its adjacent nodes, then traverse its second-level neighbor nodes, third-level neighbor nodes, and so on.
Leetcode question
Use recursion to solve problems
Top-up: preorder traversal to solve problems
Analyzing conditions
Can you determine some parameters and find the answer starting from the solution of the node itself?
Can you use these parameters and the values of the node itself to decide what should be the parameters passed to its child nodes?
All require a global variable or repeatedly passed parameters to store intermediate results.
path sum
Bottom-down: subsequent traversal solution
Analyzing conditions
For any node in the tree, if you know the answers to its children, can you calculate the answer to that node?
The maximum depth of a binary tree
Restore binary tree
If it is the same binary tree, the lengths of all [left subtree set] and [right subtree set] are equal
Preorder traversal: root node [left subtree set] [right subtree set]
Post-order traversal: [left subtree set] [right subtree set] root node
Used to determine the root node
In-order traversal: [left subtree set] root node [right subtree set]: determine the left and right boundaries based on the root node position
This is the key to solving the problem. From these relationships, a recursive formula can be derived
Use Map to store the results of in-order traversal and quickly locate the root node to clarify the left and right boundaries.
key: the value of the node
value: the index of the node in the array
Construct a binary tree by traversing a sequence in inorder and postorder
Pink = left subtree, red = root node, green = right subtree
is: inorderStart
ri=rootIndex
ie = inorderEnd
ps = postorderStart
pe = postorderEnd
Construct a binary tree from preorder and inorder traversal sequences
dynamic programming
The core idea of dynamic programming is to use the optimal substructure and the nature of overlapping subproblems to optimize the exhaustive method. By saving the intermediate results in an array, space is exchanged for time, and the program runs quickly.
feature
overlapping subproblems
optimal substructure
sort
Comparison sorting
swap sort
Bubble Sort
Algorithm Description
Compare adjacent elements. If the first one is greater than the second one, swap them both
Do the same for each pair of adjacent elements, from the first pair at the beginning to the last pair at the end, so that the element at the end should be the largest number;
Repeat the above steps for all elements except the last one;
Repeat steps 1~3 until sorting is completed.
insertion sort
selection sort
Simple selection sort
Algorithm Description
merge sort
Non-comparative sorting
recursion
When in doubt write down the recursive formula
Use memoization whenever possible
Tail recursion may help when the stack overflows.
Tail recursion optimizes the space complexity of the algorithm by eliminating the stack overhead caused by recursion.
Tail recursion is easier to read and understand than non-tail recursion.
binary search
Binary search is an algorithm that splits the search space in two after each comparison. Ordering is a prerequisite for binary search. Binary search should be considered every time you need to find an index or element in a collection. If the collection is unordered, we can always sort it before applying binary search.
Binary search is a must-test question, and it must be easy to grasp.
Template 1: Find a number in a strictly ordered array, or insert a number
Topic: Square root of x
The idea is still binary search, which is to find the value of val^2 closest to x by continuously compressing the sample space by binary division.
Note that what you are looking for is the mid of the square number closest to x
Topic: Searching Spiral Arrays
Use the mid of conventional binary interpolation search to split the array, determine which part of the two divided parts is ordered, and use the ordered part to determine the boundary of the binary search
Pay attention to the judgment of whether target is within the interval
distinguish grammar
Initial conditions: left = 0, right = length-1
When terminating: left > right
Find left: right = mid-1
Search to the right: left = mid 1
Key attributes
The search criteria can be determined without comparing to both sides of the element
No post-processing is required because at each step you are checking whether the element was found. If you reach the end, you know the element was not found.
At the end of the loop left = right 1 will return the target right neighbor index
Template 2: Find the first occurrence of a number in a strictly ordered array or find the first position greater than or equal to a certain number
distinguish grammar
Initial conditions: left = 0, right = length
When terminating: left == right
Find left: right = mid
Search to the right: left = mid 1
Key attributes
The search condition requires access to the element's immediate right neighbor. At this time right = length - 1
Post-processing is required. The loop/recursion ends when you are left with 1 element. The remaining elements need to be evaluated to see if they meet the criteria.
At the end of the loop left = right will return the coordinates of target
Template 3: Find the maximum value in an array that strictly increases and then strictly decreases (uncommon, used to solve specific question types)
linear structure
array
Top K questions
The idea of solving the problem is to sort. The simplest way is to use the API as shown above. Of course, you will not be able to pass the interview when you write like this.
Using PriorityQueue limited queue
The priority queue sorts the data, with small ones at the head and big ones at the end.
The code is also very simple: time and space are both O(n)
This question tests the sorting algorithm. Only handwritten sorting can meet the interviewer's test points.
Remove duplicates in sorted array
Experience is sorted data. The basic idea is double pointers. The key is that the starting value is 1 and the current value is used to compare the next one -> num[i] != num[i-1]. Time O(n), space O(1)
Remove duplicates in sorted array II
This question is more difficult than the previous question. Two identical elements are allowed, and the experience is still that of a sorted array. What comes to mind is still double pointers, but it is not easy to implement.
A more awesome way to solve problems: compare sizes, the boss on LeetCode is awesome. Time O(n), space O(1)
Based on this, we get the goal of deleting k duplicate items in the sorted array.
Color Classification - Netherlands Flag Question
Merge two sorted arrays
If it doesn't work the right way, let's do it the other way around. Traverse from the tail. Time O(n), space O(1)