Shulou(Shulou.com)06/03 Report--

This article mainly explains "what are the data structures and algorithms that JAVA must master". Interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn what data structures and algorithms JAVA must master.

Common linked lists of data structures

The underlying data structure of LinkedHashSet LinkedList consists of linked lists and hash tables.

It is convenient to add and delete data, but it takes time to access it.

Array

ArrayList is easy to access data, but it takes time to add and delete data.

Heap

Heap is a tree structure of a graph, which is used to implement a "priority queue". A priority queue is a data structure that allows you to add data freely, but when you take out the data, you need to start with the minimum value and take it out sequentially.

Characteristics of the heap:

Each node in the ① heap has at most two child nodes

The ② child node must be larger than the parent node

③ puts the new data on the bottom line to the left. When there is no extra space in the bottom line, start another line and add the data to the leftmost end of the line.

④ if the number of the child node is less than that of the parent node, the parent node is exchanged with the smaller of its left and right two child nodes

The data at the top of the heap is always the smallest, so no matter how much data there is, the time complexity of taking out the minimum is O (1).

It is known that the height of the tree is log2n, so the time complexity of the reconstructed tree is O (logn).

Stack (LIFO)

Slightly

Queue (FIFO)

Slightly

Hash table HashSet

The underlying data structure of TreeSet is red-black tree.

The hash function (Hash) calculates key, and the hash value is divided by the length of the array 5 to get the rest. The remainder is the number of the key, which is the location.

If a hash conflict occurs, it is important to use a linked list for storage (chain address method) to set the appropriate space for the array

In addition to the chain address method, there are several ways to resolve conflicts. Among them, the "open address method" is widely used. This method means that when a conflict occurs, an alternate address (the location on the array) is calculated immediately and the data is stored. If there is still a conflict, continue to calculate the next alternate address until the address is available. Alternate addresses can be calculated by using hash functions or "linear detection" multiple times.

Binary tree

Features:

The first ① is that the value of each node is greater than that of any node on its left subtree.

② is that the value of each node is less than the value of any node on its right subtree.

The smallest node of the ③ binary search tree should start at the top and look at its lower left end. The minimum value here is 3.

The largest node of the ④ binary search tree should start at the top and look at its lower right end.

When adding data, compared with the top data, move to the left if it is smaller than him, if there is no node on the left, add the inserted data to the lower left as a new node, and move to the right if it is larger than him (left, small, right, big).

When deleting data, if the node does not have a child node to delete directly, if one is deleted, the child node is added, if there are two, delete it and find the largest complement from the left subtree.

The number of comparisons depends on the height of the tree. So if the number of nodes is n and the shape of the tree is more balanced, the maximum number of comparisons and movements is log2n. Therefore, the time complexity is O (logn). However, if the shape of the tree extends longitudinally to one side, the tree becomes very high, and the time complexity becomes O (n).

Sorting by common algorithms

Bubbling sort

Bubble sorting is an algorithm that repeats the operation of "comparing the size of two adjacent numbers from the right of the sequence, and then swapping the positions of the two numbers according to the result." In this process, the number will float slowly from right to left to the top of the sequence, like a bubble, so this algorithm is called "bubble sorting".

The time complexity of bubble sorting is O (N2).

Select sort

Selective sorting is the algorithm that repeats the operation of finding the minimum value from the data to be sorted and swapping it with the leftmost number of the sequence. Linear lookup is used when finding the minimum value in a sequence

The maximum number of times in each round is 1. If the input data is arranged from small to large, there is no need for any exchange. The time complexity of selective sorting is the same as that of bubble sorting, which is O (N2).

Insert sort

The idea of inserting sorting is to take a piece of data from the unsorted area on the right and insert it into the appropriate location in the sorted area.

The time complexity is the same as that sorted by bubbles, both O (N2).

Heap sort

First of all, all the data is stored in the heap, and the heap is built in descending order, and then when the data is extracted from the descending heap, it will be fetched from the largest data, so the extracted data is output in reverse order, and the sorting is completed.

The time complexity of heap sorting is O (nlogn).

Merge and sort

The merge sorting algorithm divides the sequence into two subsequences of the same length, and merges the subsequences when they cannot be further divided (that is, when there is only one data in each subsequence). Merging refers to the merging of two ordered subsequences into a single ordered sequence. This operation is repeated until all the subsequences are merged into one.

Run time complexity is O (nlogn)

Quick sort

The quick sorting algorithm first randomly selects a base value (pivot) in the sequence, and then divides the numbers other than the base value into two categories: "numbers that are smaller than the base value" and "numbers that are larger than the base value". Quick sort is used again when solving sub-problems, even in this quick sort. Sorting is complete only if there is only one number left in the subproblem.

The overall time complexity is O (nlogn).

Array lookup

Linear search

Linear lookup requires a continuous sequential check of data from scratch, so when the amount of data is large and the target data is low, or when the target data does not exist, the number of comparisons will be more and more time-consuming. If the amount of data is n, the time complexity of linear search is O (n).

Binary search (abbreviated)

Search of graphs

Breadth first search

Breadth-first search is an algorithm for searching graphs. Suppose we start at a vertex (that is, the starting point), and we do not know the overall structure of the graph, and our aim is to search along the edge from the starting point until we reach the specified vertex (that is, the end point). Every time you reach a vertex in the process, you will judge whether it is the end or not. Breadth-first search will first start from the vertex near the starting point.

Depth first search

Depth-first search and breadth-first search, like breadth-first search, are algorithms for searching graphs, and the purpose is to search from the starting point to the specified vertex (end point). The depth-first search continues down one path until it can no longer continue, and then turns back to search for the next alternate path.

Behrman-Ford algorithm (omitted)

Behrman-Ford (Bellman-Ford) algorithm is an algorithm for solving the shortest path problem in a graph.

Dickstra algorithm (abbreviated)

A * algorithm (omitted)

Security algorithm

Shared key encryption

Public key encryption

Hybrid encryption

Duffy-Herman exchange

Other algorithms

K-means algorithm

Euclid algorithm

Primality test

Page ranking

Hanoi Tower

[expansion]

Representation of graphs: adjacency matrix and adjacency table

Traversal algorithm: depth search and breadth search (required)

Shortest path algorithm: Floyd,Dijkstra (required)

Minimum spanning tree algorithm: Prim,Kruskal (required)

Practical common algorithms: critical path, topological sorting (principle and application)

Bipartite graph matching: pairing, Hungarian algorithm (principle and application)

Extension: centrality algorithm, community discovery algorithm (principle and application)

two。 The diagram is still quite difficult, but I think many of the algorithms involved in the diagram are quite practical, such as the calculation of the shortest path, and so on. I still suggest reading here, you can read the fourth edition of the algorithm.

3. Search and backtracking algorithm

Greedy algorithm (must-learn) heuristic search algorithm: A* pathfinding algorithm (understanding) map coloring algorithm, N queen problem, optimal processing order traveling salesman problem

This convenience is only related to some algorithms, I think if you can, learn them all. Like the idea of greedy algorithm, you must learn it. It is recommended to do exercises to learn, leetcode direct topic brush.

4. Dynamic planning

Tree DP:01 knapsack problem Linear DP: longest common subsequence, longest common substring interval DP: Matrix maximum (sum and product) digital DP: digital game state compression DP: traveling salesman

I think dynamic programming is the most difficult algorithmic idea. I remember that when I first came into contact with dynamic planning, I looked at the problem of knapsack 01. I didn't understand it for a long time, but I understood the basic idea behind it, but I couldn't get the answer. In a fit of anger, after dozens of continuous brushes on leetcdoe topics, I mastered the routine of dynamic planning and had my own set of templates. But to tell you the truth, dynamic planning is really a lot of fucking exams, learning algorithms and doing exercises must be mastered. It is recommended that we first understand what dynamic programming is, and then leetcode topic brush, anyway, just the above questions.

5. Character matching algorithm

Regular expression pattern matching: KMP, Boyer-Moore

6. Stream correlation algorithm

Maximum flow: shortest augmentation path, Dinic algorithm maximum flow minimum cut: maximum benefit problem, box number problem minimum cost maximum flow: minimum cost path, recreation to this, I believe that "what JAVA must master the data structure and algorithm" have a deeper understanding, might as well come to the actual operation! Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.