move instruction

basic operation instruction

compared instruction

those instruction will return a value:

8 Kind of Sorting Algorithm

Bubble sort

1
2
3
4
5
6
7

def bubble_sort(lists):
    count = len(lists)
    for i in range(0, count):
        for j in range(i + 1, count):
            if lists[i] > lists[j]:
                lists[i], lists[j] = lists[j], lists[i]
    return lists

Read More

N-Queens Problem

Overview

The eight queens problem is a question with chess as the background: how to place eight queens on an 8×8 chess board so that no queen can directly eat other queens? In order to achieve this purpose, any two queens are not in the same horizontal, vertical or diagonal. The eight queen problem can be extended to the more general N-Queens Problem.

more information about n-queens problem please google it.

C++ Code

1
2
3
4
5
6
7
8
9
10
11
12

int NQueens(int n) {
    int upperlim = (1 << n) - 1, sum = 0;
    std::function<void(int,int,int)> dfs = [&](int row,int ld,int rd) {
        if(row == upperlim) {++sum;return;}
        for(int cur = upperlim & (~(row|ld|rd)),pos = 0;cur ;dfs(row|pos,(ld|pos)<<1,(rd|pos)>>1)) {
            pos = cur & (-cur);
            cur -= pos;
        }
    };
    dfs(0,0,0);
    return sum;
}

Read More

Topological Sort Chinese version address

Topological Sort

Overview

Topological sorting means ordering a Directed Acyclic Graph(DAG) to get an ordered linear sequence.

In this way, it may be understood more abstractly.

For example, a project consists of four subsections A, B, C, and D, and A depends on B and D. C depends on D. Now to develop a plan to write A, B, C, D the order of execution. At this point, you can use topological sorting, which is used to determine the order in which things happen.

In topological sorting, if there is a path from the vertex A to the vertex B, B appears behind the A in the ranking result.

Algorithm Introduction

1. Create a queue Q and a topological ordered result queue T.
2. Put all the nodes that do not depend on the vertex in the Q.
3. When Q has vertices, perform the following steps.
   1. Take a vertex n from Q (delete n from Q) and put it in T (add n to the result set).
   2. For every adjacent point m (n is the starting point and m is the ending point).
      1. Remove the edge (n, m).
      2. If m does not depend on the vertex, put b into Q.

The vertex A does not depend on the vertex, which means there is no edge to the end of the A.

Read More

Breadth First Search Chinese version address

Breadth First Search

Overview

The breadth first search algorithm, also known as “width first search” or “horizontal priority search”, is called BFS.

From a vertex in the graph, each of the not visited adjacent points of the V is accessed in turn after accessing the starting vertex, then the adjacency points are accessed in turn from these adjacent points, and the adjacent points of the vertex to be accessed are accessed before the adjacent points of the vertices that are accessed, until all the adjacent points of the vertices are accessed. If the vertices are not accessed at this time, we need to select another vertex which has never been visited as a new starting point, repeat the above process until all the vertices in the graph are accessed.

In other words, the process of breadth first search is the starting point and from near to far, access to the path and the path length of the starting vertex and the path length of 1,2…

Diagram

Breadth first search for undirected graphs

The following is an example of undirected graph, to demonstrate the depth-first search.

Read More

Depth First Search Chinese version address

Depth First Search

Overview

Depth first search of the graph is similar to the preorder traversal of the tree.

Suppose that the initial state is that all the vertices in the graph are not accessed, then starting from a vertex and first access to it, nextly, the depth first search traversal from each of its non-accessed adjacency points in turn, until all the vertices that have a path to the starting vertex in the graph are accessed. If there are other vertices that are not accessed, then choose another unvisited vertex as a starting point, repeat the above process until all graph vertices have been visited.

Diagram

Depth first search for undirected graphs

The following is an example of undirected graph, to demonstrate the depth first search.

Read More

Adjacency List Graph Chinese version address

Adjacency List Graph

Adjacency List Undirected Graph

Adjacency matrix undirected graph refers to an undirected graph represented by an adjacency list.

The above graph contains 7 vertices of A, B, C, D, E, F, G, and it also contains<A,C>, <A,D>, <A,F>, <B,C>, <C,D>, <E,G>, <F,G>, in total 7 edges. Since this is an undirected graph, the edge <A,C> and the edge <C,A> are the same edges. The table of edges is listed in alphabetical order..

Read More

Adjacency Matrix Graph Chinese version address

Adjacency Matrix Graph

Adjacency Matrix Undirected Graph

Adjacency matrix undirected graph refers to an undirected graph represented by an adjacency matrix.

The above graph contains 7 vertices of A, B, C, D, E, F, G, and it also contains, , , , , , , in total 7 edges. Since this is an undirected graph, the edge and the edge are the same edges. The table of edges is listed in alphabetical order.

Read More

Basic Graph Theory Chinese version address

Graph Theory

The definition of graph

The graph is composed of some points and the connection between these points. points are often called vertices, and the lines between points are called edges. It is usually written as G = (V,E).

Types of Graphs

According to whether the direction of the edge, the graph can be divided into: undirected and directed graph.

Undirected graph

Read More

RedBlackTree III Chinese version address

The Last Section

Basic operation of red black trees

Delete

The method of deleting a node is the same as that of deleting a node in a binary search tree.

Binary search tree Delete pseudo code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

TREE-DELETE(T, z)  
  if left[z] = NIL or right[z] = NIL  
      then y ← z  
      else y ← TREE-SUCCESSOR(z)  
  if left[y] ≠ NIL  
      then x ← left[y]  
      else x ← right[y]  
  if x ≠ NIL  
      then p[x] ← p[y]  
  if p[y] = NIL  
      then root[T] ← x  
      else if y = left[p[y]]  
              then left[p[y]] ← x  
              else right[p[y]] ← x  
  if y ≠ z  
      then key[z] ← key[y]  
           copy y's satellite data into z  
  return y

Read More