Transferred from: Micro reading  https://www.weidianyuedu.com

Data structure and algorithm are programmers' internal mental skills and basic skills. Whether in artificial intelligence or other computer science fields, mastering solid knowledge of data structure and algorithm will often help a lot! Today I recommend you a good data structure and algorithm resources. Features: full code implementation!

The author of this resource, Mr. Wang Zheng, is the columnist of the beauty of data structures and algorithms, a former Google engineer and followed by 50000 + people. He summarized the 50 necessary data structures and algorithms for programmers, as well as the corresponding code implementation. The open source address is:

https://github.com/wangzheng0822/algo

Let's take a look at what the necessary 50 data structures and algorithms contain.

Array

• Problem: implement an array that supports dynamic capacity expansion

• Problem: realize an ordered array with fixed size, and support dynamic addition, deletion and modification operations

• Problem: realize the combination of two ordered arrays into one ordered array

Linked list

• Problem: realize single linked list, circular linked list and two-way linked list, and support addition and deletion operations

• Problem: realize single linked list inversion

• Problem: realize the combination of two ordered linked lists into an ordered linked list

• Problem: realize the intermediate node of the linked list

Stack

• Problem: implement a sequential stack with an array

• Problem: use a linked list to implement a linked stack

• Problem: programming simulation realizes the forward and backward functions of a browser

Queue

• Problem: implement a sequential queue with an array

• Problem: use a linked list to implement a linked queue

• Problem: implement a circular queue

Recursion

• Problem: programming Fibonacci sequence evaluation f(n)=f(n-1)+f(n-2)

• Problem: programming factorial n!

• Problem: program to realize the full arrangement of a set of data sets

Sort

• Problem: realize merge sort, quick sort, insert sort, bubble sort and select sort

• Problem: find the K-th largest element of a set of data in the time complexity of programming O(n)

Binary search

• Problem: implement a binary search algorithm for an ordered array

• Problem: implement the fuzzy binary search algorithm (such as the first element greater than or equal to the given value)

Hash table

• Problem: implement a hash table based on linked list method to solve conflict problems

• Problem: implement an LRU cache elimination algorithm

String

• Problem: implement a character set, which only contains the Trie tree of 26 English letters a ~ z

• Problem: implement a simple string matching algorithm

Binary tree

• Problem: implement a binary search tree, and support insert, delete and search operations

• Problem: find the successor and precursor nodes of a node in the binary search tree

• Problem: realize the pre, middle and post order of binary tree and traversal by layer

Pile

• Problem: implement a small top heap, large top heap and priority queue

• Problem: implement heap sorting

• Problem: merge K ordered arrays using priority queue

• Problem: find the maximum Top K of a set of dynamic data sets

Figure

• Problem: realize the representation of adjacency matrix and adjacency table of directed graph, undirected graph, weighted graph and weighted graph

• Problem: realize the depth first search and breadth first search of the graph

• Problem: implement Dijkstra algorithm and A * algorithm

• Problem: Kahn algorithm and DFS algorithm for topological sorting

Backtracking

• Problem: using backtracking algorithm to solve the eight queens problem

• Problem: using backtracking algorithm to solve 0-1 knapsack problem

Divide and conquer

• Problem: use divide and conquer algorithm to find the number of reverse pairs of a group of data

Dynamic programming

• Question: 0-1 knapsack problem

• Problem: minimum path and

• Problem: programming to achieve the shortest editing distance of levinstein

• Problem: the programming implementation finds the longest common subsequence of two strings

• Problem: programming the longest increasing subsequence of a data sequence

All the above data structures and algorithms are equipped with corresponding program codes. A major feature is that the code is equipped with multiple programming languages, such as Python, C, Java, Go, Scala, etc.

For example, for common sorting algorithms, such as bubble sorting, insertion sorting and selection sorting, the author gives the corresponding Python code implementation:

""" Bubble sort, insertion sort and selection sort Bubble sort, insert sort, select sort Author: Wenru"""from typing import List# Bubble sorting def bubble_sort(a: List[int]): length = len(a) if length <= 1: return for i in range(length): made_swap = False for j in range(length - i - 1): if a[j] > a[j + 1]: a[j], a[j + 1] = a[j + 1], a[j] made_swap = True if not made_swap: break# Insert sort def insertion_sort(a: List[int]): length = len(a) if length <= 1: return for i in range(1, length): value = a[i] j = i - 1 while j >= 0 and a[j] > value: a[j + 1] = a[j] j -= 1 a[j + 1] = value# Select sort def selection_ sort(a: List[int]): length = len(a) if length <= 1: return for i in range(length): min_ index = i min_ val = a[i] for j in range(i, length): if a[j] < min_ val: min_ val = a[j] min_ index = j a[i], a[min_index] = a[min_index], a[i]def test_ bubble_ sort(): test_ array = [1, 1, 1, 1] bubble_ sort(test_array) assert test_ array == [1, 1, 1, 1] test_ array = [4, 1, 2, 3] bubble_ sort(test_array) assert test_ array == [1, 2, 3, 4] test_ array = [4, 3, 2, 1] bubble_ sort(test_array) assert test_ array == [1, 2, 3, 4]def test_ insertion_ sort(): test_ array = [1, 1, 1, 1] insertion_ sort(test_array) assert test_ array == [1, 1, 1, 1] test_ array = [4, 1, 2, 3] insertion_ sort(test_array) assert test_ array == [1, 2, 3, 4] test_ array = [4, 3, 2, 1] insertion_ sort(test_array) assert test_ array == [1, 2, 3, 4]def test_ selection_ sort(): test_ array = [1, 1, 1, 1] selection_ sort(test_array) assert test_ array == [1, 1, 1, 1] test_ array = [4, 1, 2, 3] selection_ sort(test_array) assert test_ array == [1, 2, 3, 4] test_ array = [4, 3, 2, 1] selection_ sort(test_array) assert test_ array == [1, 2, 3, 4]if __ name__ ==  "__main__":  array = [5, 6, -1, 4, 2, 8, 10, 7, 6] bubble_ sort(array) print(array) array = [5, 6, -1, 4, 2, 8, 10, 7, 6] insertion_ sort(array) print(array) array = [5, 6, -1, 4, 2, 8, 10, 7, 6] selection_ sort(array) print(array)

Of course, there are code implementations of other programming languages, which are not listed here one by one!

At present, this resource has harvested 6000 stars on GitHub. Is a good data structure and algorithm reference code. It's worth seeing.