Shangsilicon Valley java data structure and algorithm learning notes

Linear structure and nonlinear structure

Sparse array SparseArray

demand

Recording the position of the chessboard can be saved with a binary array, but it will be found that recording a lot of meaningless data and a lot of space waste can be optimized with a sparse array

introduce

Sparse array is to compress redundant data

The first row records the number of rows and columns of the original table and the number of non-zero values

example


code implementation

package com.luyi.DataStructures.sparse;

import java.util.Date;

/**
 * @author Lu Yi
 * @create 2020-12-01 9:26
 */
public class SparseArray {
	public static void main(String[] args) {
		// Create an original two-dimensional array 11 * 11
		// 0 means there are no pieces, 1 means sunspots, and 2 means whites
		int chessArray[][] = new int[11][11];
		chessArray[1][2] = 1;
		chessArray[2][3] = 2;
		// Output the original two-dimensional array
		System.out.println("Output the original two-dimensional array");
		for(int row[] : chessArray){
			for (int data : row){
				System.out.print(data + "\t");
			}
			System.out.println();
		}

		// The idea of transforming two-dimensional array into sparse array
		// 1 first traverse the two-dimensional array to get the number of non-0 data
		int sum = 0;
		for(int i = 0; i < chessArray.length; i++){
			for(int j = 0; j<chessArray.length; j++ ){
				if(chessArray[i][j] != 0){
					sum++;
				}
			}
		}
		System.out.println("Number of non-0 data sum="+ sum);
		// 2 create the corresponding sparse array
		int sparseArray[][] = new int[sum+1][3];
		// Assign values to sparse arrays
		sparseArray[0][0] = 11;
		sparseArray[0][1] = 11;
		sparseArray[0][2] = sum;

		// Traverse a two-dimensional array and store non-zero values in a sparse array
		int index = 1;
		for(int i = 0; i < chessArray.length; i++){
			for(int j = 0; j<chessArray.length; j++ ){
				if(chessArray[i][j] != 0){
					sparseArray[index][0] = i;
					sparseArray[index][1] = j;
					sparseArray[index][2] = chessArray[i][j];
					index++;
				}
			}
		}
		// Output sparse array
		System.out.println("The resulting sparse array is:");
		for (int i = 0;i<sum+1;i++){
			System.out.print(sparseArray[i][0] + "\t");
			System.out.print(sparseArray[i][1] + "\t");
			System.out.print(sparseArray[i][2] + "\t");
			System.out.println();
		}

		// Restore sparse array to two-dimensional array
		// 1 read the first row of the sparse array and create the original two-dimensional array according to the data of the first row
		// 2 read the last few lines of the sparse array and assign values
		int row = sparseArray[0][0];
		int cos = sparseArray[0][1];
		int newChessArray[][] = new int[row][cos];
		for(int i = 0; i < row; i++){
			for(int j = 0; j < cos; j++ ){
				newChessArray[i][j] = 0;
			}
		}
		for (int i = 1; i < sparseArray.length;i++){
			newChessArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
		}

		System.out.println("Output recovered 2D array");
		for(int rows[] : chessArray){
			for (int data : rows){
				System.out.print(data + "\t");
			}
			System.out.println();
		}

	}

}

Code execution results

Output the original two-dimensional array
0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
Number of non-0 data sum=2
The resulting sparse array is:
11 11 2
1 2 1
2 3 2
Output recovered 2D array
0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0

queue

introduce


The clear figure in the figure above shows that the tail front of the queue of the real to be table represents the head of the data. When the data is stored, the front remains unchanged and the position of the front changes. When the data is stored, the position of the rear remains unchanged and the position of the front changes

Array simulation queue idea

rear == maxSize-1 is full. front points to the first position of the queue head. rear points to the specific position of the queue tail

code implementation

package com.luyi.DataStructures.queue;


import java.util.Scanner;

/**
 * @author Lu Yi
 * @create 2020-12-01 10:08
 * Array simulation queue
 */
public class ArrayQueueDemo {
	public static void main(String[] args) {
		// test
		// Create a queue
		ArrayQueue arrayQueue = new ArrayQueue(3);
		char key = ' '; // Receive user input
		Scanner scanner = new Scanner(System.in);
		boolean loop = true; // Control cycle
		// Output a menu
		while (loop){
			System.out.println("s(show): Show pairs of columns");
			System.out.println("e(exit): Exit program");
			System.out.println("a(add): Add data to pair column");
			System.out.println("g(get): Fetching data from a pair of columns");
			System.out.println("h(head): View data for column headers");
			key = scanner.next().charAt(0); //Receive this character
			switch (key) {
				case 's':
					arrayQueue.showQueue();
					break;
				case 'a':
					System.out.println("Enter a number");
					int value = scanner.nextInt();
					arrayQueue.addQueue(value);
					break;
				case 'g':
					try {
						System.out.println("Extracted data:"+arrayQueue.getQueue());
					} catch (Exception e){
						System.out.println(e.getMessage());
					}
					break;
				case 'h':
					try {
						System.out.println("Queue header data:"+arrayQueue.headQueue());
					} catch (Exception e){
						System.out.println(e.getMessage());
					}
					break;
				case 'e':
					scanner.close();
					loop = false;
					break;
				default :
					break;
			}
		}
		System.out.println("Program exit");

	}
}

// Write an ArrayQueue class using an array to simulate a queue
class ArrayQueue {
	private int maxSize; // Represents the maximum capacity of the array
	private int front; // Queue header
	private int rear; // End of queue
	private int[] arr; // Storage data simulation queue

	// Constructor to create a queue
	public ArrayQueue(int maxSize){
		this.maxSize = maxSize;
		arr= new int[maxSize];
		front = rear = -1; // The queue head and tail front point to the first position of the queue head, and the rear point to the specific position of the queue tail
	}

	// Determine whether the queue is full
	public Boolean isFull(){
		return rear == maxSize - 1;
	}

	// Judge whether the column is empty
	public Boolean isEmpty(){
		return rear == front;
	}

	// Add data to pair column
	public void addQueue(int n){
		// Determine whether the queue is full
		if(isFull()){
			System.out.println("Queue full,Data cannot be added");
			return;
		}
		// rear shift back
		arr[++rear] = n;
	}

	// Data out of queue
	public int getQueue(){
		// Judge whether the opponent is empty
		if(isEmpty()){
			throw new RuntimeException("The queue is empty and data cannot be retrieved");
		}
		return arr[++front];
	}

	// Displays all data for the column
	public void showQueue(){
		// Judge whether the queue is empty
		if(isEmpty()){
			System.out.println("Queue is empty");
			return;
		}
		for (int i = 0; i < arr.length; i++){
			System.out.println("arr["+i+"]="+arr[i]);
		}
	}

	// The data displayed on the header of the column is not fetched data
	public int headQueue(){
		// Judge whether it is empty
		if(isEmpty()){
			throw new RuntimeException("Queue is empty,No header data");
		}
		return arr[front + 1];
	}
}

Console results

s(show): displays the pair of columns
e(exit): exit the program
a(add): add data to a pair of columns
g(get): fetch data from the opposite column
h(head): view the data of column headers
s
Queue is empty
s(show): displays the pair of columns
e(exit): exit the program
a(add): add data to a pair of columns
g(get): fetch data from the opposite column
h(head): view the data of column headers
a
Enter a number
10
s(show): displays the pair of columns
e(exit): exit the program
a(add): add data to a pair of columns
g(get): fetch data from the opposite column
h(head): view the data of column headers
s
arr[0]=10
arr[1]=0
arr[2]=0
s(show): displays the pair of columns
e(exit): exit the program
a(add): add data to a pair of columns
g(get): fetch data from the opposite column
h(head): view the data of column headers
a
Enter a number
20
s(show): displays the pair of columns
e(exit): exit the program
a(add): add data to a pair of columns
g(get): fetch data from the opposite column
h(head): view the data of column headers
a
Enter a number
30
s(show): displays the pair of columns
e(exit): exit the program
a(add): add data to a pair of columns
g(get): fetch data from the opposite column
h(head): view the data of column headers
s
arr[0]=10
arr[1]=20
arr[2]=30
s(show): displays the pair of columns
e(exit): exit the program
a(add): add data to a pair of columns
g(get): fetch data from the opposite column
h(head): view the data of column headers
a
Enter a number
40
The queue is full and data cannot be added
s(show): displays the pair of columns
e(exit): exit the program
a(add): add data to a pair of columns
g(get): fetch data from the opposite column
h(head): view the data of column headers
h
Data in queue header: 10
s(show): displays the pair of columns
e(exit): exit the program
a(add): add data to a pair of columns
g(get): fetch data from the opposite column
h(head): view the data of column headers
g
Extracted data: 10
s(show): displays the pair of columns
e(exit): exit the program
a(add): add data to a pair of columns
g(get): fetch data from the opposite column
h(head): view the data of column headers
h
Data in queue header: 20
s(show): displays the pair of columns
e(exit): exit the program
a(add): add data to a pair of columns
g(get): fetch data from the opposite column
h(head): view the data of column headers
g
Extracted data: 20
s(show): displays the pair of columns
e(exit): exit the program
a(add): add data to a pair of columns
g(get): fetch data from the opposite column
h(head): view the data of column headers
g
Extracted data: 30
s(show): displays the pair of columns
e(exit): exit the program
a(add): add data to a pair of columns
g(get): fetch data from the opposite column
h(head): view the data of column headers
g
The queue is empty and data cannot be retrieved
s(show): displays the pair of columns
e(exit): exit the program
a(add): add data to a pair of columns
g(get): fetch data from the opposite column
h(head): view the data of column headers
h
The queue is empty and has no header data
s(show): displays the pair of columns
e(exit): exit the program
Add to column: a
g(get): fetch data from the opposite column
h(head): view the data of column headers

problem

Now the queue has been filled up and all of them are taken out. The current list is theoretically empty
However, the data cannot be added. This array cannot be reused. It can only be used once, which does not achieve the effect of reuse
This array needs to be transformed from an algorithm into a ring array (Modular)

Array simulation ring queue

Note that the front and rear queues have now been adjusted

Ring queue code implementation

package com.luyi.DataStructures.queue;

import java.util.Scanner;

/**
 * Circular array pair column
 * @author Lu Yi
 * @create 2020-12-01 13:54
 */
public class CircleArrayQueue {
	public static void main(String[] args) {
		// test
		// Create a ring queue
		CircleArray arrayQueue = new CircleArray(4); // The array space set to 4 is valid
		char key = ' '; // Receive user input
		Scanner scanner = new Scanner(System.in);
		boolean loop = true; // Control cycle
		// Output a menu
		while (loop){
			System.out.println("s(show): Show pairs of columns");
			System.out.println("e(exit): Exit program");
			System.out.println("a(add): Add data to pair column");
			System.out.println("g(get): Fetching data from a pair of columns");
			System.out.println("h(head): View data for column headers");
			key = scanner.next().charAt(0); //Receive this character
			switch (key) {
				case 's':
					arrayQueue.showQueue();
					break;
				case 'a':
					System.out.println("Enter a number");
					int value = scanner.nextInt();
					arrayQueue.addQueue(value);
					break;
				case 'g':
					try {
						System.out.println("Extracted data:"+arrayQueue.getQueue());
					} catch (Exception e){
						System.out.println(e.getMessage());
					}
					break;
				case 'h':
					try {
						System.out.println("Queue header data:"+arrayQueue.headQueue());
					} catch (Exception e){
						System.out.println(e.getMessage());
					}
					break;
				case 'e':
					scanner.close();
					loop = false;
					break;
				default :
					break;
			}
		}
		System.out.println("Program exit");

	}
}


// Write an ArrayQueue class using an array to simulate a queue
class CircleArray  {
	private int maxSize; // Represents the maximum capacity of the array
	// The meaning of the variable of front is adjusted to point to the first element of the queue, that is, arr[front] is the first header element
	// The initial value of front becomes 0
	private int front; // Queue header
	// Adjust the meaning of the rear variable. Rear points to the next position of the last element of the queue, because you want to free up a space for convention. The initial value of rear is 0
	private int rear; // End of queue
	private int[] arr; // Storage data simulation queue

	// Constructor to create a queue
	public CircleArray(int maxSize){
		this.maxSize = maxSize;
		arr= new int[maxSize];
		//front = rear = 0 ; //  The queue head and tail front point to the first position of the queue head, and the rear point to the specific position of the queue tail
	}

	// Determine whether the queue is full
	public boolean isFull(){
		return (rear + 1)% maxSize == front;
	}

	// Judge whether the column is empty
	public boolean isEmpty(){
		return rear == front;
	}

	// Add data to pair column
	public void addQueue(int n){
		// Determine whether the queue is full
		if(isFull()){
			System.out.println("Queue full,Data cannot be added");
			return;
		}
		// Real points to the last position of the alignment and directly adds data to the backward moving real pointer
		arr[rear] = n;
		// If the rear is already at the last position of the array, you need to take the module to the beginning of the array
		rear = (rear + 1) % maxSize;
	}

	// Data out of queue
	public int getQueue(){
		// Judge whether the opponent is empty
		if(isEmpty()){
			throw new RuntimeException("The queue is empty and data cannot be retrieved");
		}
	 	// Here, we need to analyze that front is the first element pointing to the queue
		// 1 first save the value corresponding to front to the temporary variable
		// 2 move the front back
		// 3 Return temporarily saved variables
		int value = arr[front];
		front = (front + 1) % maxSize;
		return value;
	}

	// Displays all data for the column
	public void showQueue(){
		// Judge whether the queue is empty
		if(isEmpty()){
			System.out.println("Queue is empty");
			return;
		}
		// Idea: start traversing from front, and how many elements are traversed
		//
		for (int i = front; i < front + size(); i++){
			System.out.println("arr["+ i % maxSize +"]="+arr[i % maxSize]);
		}
	}

	// The data displayed on the header of the column is not fetched data
	public int headQueue(){
		// Judge whether it is empty
		if(isEmpty()){
			throw new RuntimeException("Queue is empty,No header data");
		}
		return arr[front];
	}

	// Find the number of valid data in the current queue
	public int size() {
		return  (rear + maxSize - front) % maxSize;
	}
}

Operation results

s(show): Show pairs of columns
e(exit): Exit program
a(add): Add data to pair column
g(get): Fetching data from a pair of columns
h(head): View data for column headers
s
 Queue is empty
s(show): Show pairs of columns
e(exit): Exit program
a(add): Add data to pair column
g(get): Fetching data from a pair of columns
h(head): View data for column headers
a
 Enter a number
10
s(show): Show pairs of columns
e(exit): Exit program
a(add): Add data to pair column
g(get): Fetching data from a pair of columns
h(head): View data for column headers
a 20
 Enter a number
s(show): Show pairs of columns
e(exit): Exit program
a(add): Add data to pair column
g(get): Fetching data from a pair of columns
h(head): View data for column headers
s
arr[0]=10
arr[1]=20
s(show): Show pairs of columns
e(exit): Exit program
a(add): Add data to pair column
g(get): Fetching data from a pair of columns
h(head): View data for column headers
a 
Enter a number
30
s(show): Show pairs of columns
e(exit): Exit program
a(add): Add data to pair column
g(get): Fetching data from a pair of columns
h(head): View data for column headers
s
arr[0]=10
arr[1]=20
arr[2]=30
s(show): Show pairs of columns
e(exit): Exit program
a(add): Add data to pair column
g(get): Fetching data from a pair of columns
h(head): View data for column headers
a
 Enter a number
40
 Queue full,Data cannot be added
s(show): Show pairs of columns
e(exit): Exit program
a(add): Add data to pair column
g(get): Fetching data from a pair of columns
h(head): View data for column headers

g
 Extracted data:10
s(show): Show pairs of columns
e(exit): Exit program
a(add): Add data to pair column
g(get): Fetching data from a pair of columns
h(head): View data for column headers
s
arr[1]=20
arr[2]=30
s(show): Show pairs of columns
e(exit): Exit program
a(add): Add data to pair column
g(get): Fetching data from a pair of columns
h(head): View data for column headers
a 10
 Enter a number
s(show): Show pairs of columns
e(exit): Exit program
a(add): Add data to pair column
g(get): Fetching data from a pair of columns
h(head): View data for column headers
s
arr[1]=20
arr[2]=30
arr[3]=10
s(show): Show pairs of columns
e(exit): Exit program
a(add): Add data to pair column
g(get): Fetching data from a pair of columns
h(head): View data for column headers
a 70
 Enter a number
 Queue full,Data cannot be added
s(show): Show pairs of columns
e(exit): Exit program
a(add): Add data to pair column
g(get): Fetching data from a pair of columns
h(head): View data for column headers
h 
Queue header data:20
s(show): Show pairs of columns
e(exit): Exit program
a(add): Add data to pair column
g(get): Fetching data from a pair of columns
h(head): View data for column headers
g 
Extracted data:20
s(show): Show pairs of columns
e(exit): Exit program
a(add): Add data to pair column
g(get): Fetching data from a pair of columns
h(head): View data for column headers
g
 Extracted data:30
s(show): Show pairs of columns
e(exit): Exit program
a(add): Add data to pair column
g(get): Fetching data from a pair of columns
h(head): View data for column headers
g
 Extracted data:10
s(show): Show pairs of columns
e(exit): Exit program
a(add): Add data to pair column
g(get): Fetching data from a pair of columns
h(head): View data for column headers
g
 The queue is empty and data cannot be retrieved
s(show): Show pairs of columns
e(exit): Exit program
a(add): Add data to pair column
g(get): Fetching data from a pair of columns
h(head): View data for column headers
a 50
 Enter a number
s(show): Show pairs of columns
e(exit): Exit program
a(add): Add data to pair column
g(get): Fetching data from a pair of columns
h(head): View data for column headers
a

Linked list

Summary above:

  1. Linked list is stored in the form of nodes, which is chain storage
  2. Each node contains data field and next field: point to the next node
  3. As shown in the figure: it is found that each node of the linked list is not necessarily stored continuously
  4. The linked list is divided into the linked list with the leading node and the linked list without the head node, which is determined according to the actual needs

Single linked list

The single linked list looks continuous, but it's not. It's just a logical structure

Regardless of ranking

Consider ranking

modify

Idea: (1) first find the node and traverse, (2) temp name = newHeroNode. name ; temp. nickname= newHeroNode. nickname

delete

code implementation

package com.luyi.DataStructures.linkedlist;

/**
 * @author Lu Yi
 * @create 2020-12-01 21:10
 */
public class SingleLinkedListDemo {

	public static void main(String[] args) {
		// Create node first
		HeroNode heroNode1 = new HeroNode(1, "Song Jiang", "Timely rain");
		HeroNode heroNode2 = new HeroNode(2, "Lu Junyi", "Jade Unicorn");
		HeroNode heroNode3 = new HeroNode(3, "Wu Yong", "Zhiduoxing");
		HeroNode heroNode4 = new HeroNode(4, "Lin Chong", "Leopard head");

		// Create a linked list
		SingleLinkedList singleLinkedList = new SingleLinkedList();
		// join
//		singleLinkedList.add(heroNode1);
//		singleLinkedList.add(heroNode2);
//		singleLinkedList.add(heroNode3);
//		singleLinkedList.add(heroNode4);
		/**
		 * result:
		 * HeroNode{no=1, name='Name = 'song Jiangyu'}
		 * HeroNode{no=2, name='Lu Junyi ', nickName =' jade Qilin '}
		 * HeroNode{no=3, name='Wu Yong ', nickName =' Zhiduoxing '}
		 * HeroNode{no=4, name='Lin Chong ', nickName =' leopard head '}
		 */
		// Add in order of number
		singleLinkedList.addByOrder(heroNode1);
		singleLinkedList.addByOrder(heroNode4);
		singleLinkedList.addByOrder(heroNode2);
		singleLinkedList.addByOrder(heroNode3);
		singleLinkedList.addByOrder(heroNode3);
		/**
		 * result
		 * The number [3] of the hero to be inserted already exists and cannot be added!
		 * HeroNode{no=1, name='Song Jiang ', nickName =' timely rain '}
		 * HeroNode{no=2, name='Lu Junyi ', nickName =' jade Qilin '}
		 * HeroNode{no=3, name='Wu Yong ', nickName =' Zhiduoxing '}
		 * HeroNode{no=4, name='Lin Chong ', nickName =' leopard head '}
		 */
		// display
		singleLinkedList.list();

		// Test modification node
		HeroNode newHeroNode = new HeroNode(2, "Xiao Lu", "Little Unicorn");
		HeroNode newHeroNode1 = new HeroNode(5, "Xiao Lu", "Little Unicorn");
		singleLinkedList.update(newHeroNode );
		singleLinkedList.update(newHeroNode1 );
		/**
		 * result
		 * HeroNode{no=1, name='Song Jiang ', nickName =' timely rain '}
		 * HeroNode{no=2, name='Lu Junyi ', nickName =' jade Qilin '}
		 * HeroNode{no=3, name='Wu Yong ', nickName =' Zhiduoxing '}
		 * HeroNode{no=4, name='Lin Chong ', nickName =' leopard head '}
		 * No node with number [5] found
		 * Modified linked list
		 *
		 * HeroNode{no=1, name='Song Jiang ', nickName =' timely rain '}
		 * HeroNode{no=2, name='Xiao Lu ', nickName =' Xiao Qilin '}
		 * HeroNode{no=3, name='Wu Yong ', nickName =' Zhiduoxing '}
		 * HeroNode{no=4, name='Lin Chong ', nickName =' leopard head '}
		 */
		// Modified display
		System.out.println("After modification of the linked list");
		System.out.println();
		singleLinkedList.list();

		System.out.println("Delete a node");
		singleLinkedList.delete(1);
		singleLinkedList.delete(2);
		singleLinkedList.delete(3);
		singleLinkedList.delete(4);
		singleLinkedList.list();
		/**
		 * result
		 * Delete a node
		 * The linked list is empty
		 */

	}
}
// Define a one-way linked list to manage our heroes
class SingleLinkedList {
	// Initialize the header node and nod the node. Don't move and don't store specific data
	private HeroNode head =new HeroNode(0,null,null);

	// Add method to one-way linked list
	// Train of thought when the numbering sequence is not considered
	// 1. Find the last node of the current linked list
	// 2. Point the next of the last node to the new node
	public void add(HeroNode heroNode){
		// Because the head node cannot be moved, we need an auxiliary node temp
		HeroNode temp = head;
		// Traverse the linked list to find the last
		while (true){
			// Find the end of the linked list
			if(temp.next == null){
				break;
			}
			// If not found, move temp back
			temp = temp.next;
		}
		// When exiting the white loop, temp points to the end of the linked list
		temp.next = heroNode;
	}

	// The second way to add a hero is to insert the hero into the specified position according to the ranking
	// If there is this ranking, the addition fails and a prompt is given
	public void addByOrder(HeroNode heroNode){
		// Because the head node cannot be moved, we still use an auxiliary pointer (variable) to help find the added position
		// Because it is a single list, temp is to find the previous node to add nodes, otherwise it cannot be inserted
		HeroNode temp = head;
		boolean flag = false; // Whether the number added by the flag exists. The default is false
		while(true) {
			if(temp.next == null) { // It indicates that it has reached the end of the linked list
				break;
			}
			if (temp.next.no > heroNode.no) { // Location found in temp and temp Insert this node between next
				break;
			}else if (temp.next.no == heroNode.no) { // Note the number of the heroNode you want to add already exists and cannot be added
				flag = true; // Description number exists
				break;
			}
			temp = temp.next;
		}
		// Judge the value of flag
		if (flag){ // Cannot add description. Number exists
			System.out.println("The number of the hero to insert["+heroNode.no+"]Already exists,Can't join!");
		}else {
			// Insert temp in linked list
			heroNode.next = temp.next;
			temp.next = heroNode;
		}
	}

	// Display linked list traversal
	public void list(){
		// Judge whether the linked list is empty
		if(head.next == null){
			System.out.println("The linked list is empty");
			return;
		}
		// Because the head node cannot be moved, we need a replication node temp
		HeroNode temp = head.next;
		while(true){
			// Output the information of this node
			System.out.println(temp);
			if(temp.next == null){
				break;
			}
			// Move temp backward, otherwise it will be an endless loop
			temp = temp.next;
		}

	}
	// The information of the modified node is modified according to the number. The number cannot be modified
	public void update (HeroNode newHeroNode){
		if(head.next == null){
			System.out.println("The linked list is empty");
			return;
		}
		// Finding the node that needs to be modified is a no query
		HeroNode temp = head.next;
		boolean flag = false; // Indicates whether the node is found
		while (true) {
			if (temp == null) {
				break; // Indicates that the traversal of the linked list has ended (not that the last node has gone out)
			}
			if (temp.no == newHeroNode.no){
				// Find the node to modify
				flag = true;
				break;
			}
			temp = temp.next;
		}
		// Judge whether to find the node to be modified according to the flag
		if(!flag){
			System.out.println("The number was not found["+newHeroNode.no+ "]Node of");
		}else {
			temp.name = newHeroNode.name;
			temp.nickName = newHeroNode.nickName;
		}

	}

	// Delete node
	//Train of thought 1 The head node cannot be moved, so we need a temp auxiliary node to find the previous node to delete the node
	//    2. We need to compare with the label of the last node of temp node
	public void delete(int no){
		HeroNode temp = head;
		boolean flag = false; // Flag whether the node to be deleted is found
		while (true) {
			if (temp.next == null){ // temp has reached the end of the linked list
				break;
			}
			if (temp.next.no == no){
				// The previous node of the node to be deleted was found
				flag = true;
				break;
			}
			temp = temp.next;
		}
		if (flag){
			// Can delete
			HeroNode t = temp.next;
			temp.next = t.next;
			t.next = null;
		}else {
			System.out.println("The was not found no=["+no+"]node,Cannot delete");
		}


	}

}

// Define a HeroNode, and each HeroNode object is a node
class HeroNode {
	public int no;
	public String name;
	public String nickName;
	public HeroNode next; // Point to next node

	// constructor 
	public HeroNode(int hNo, String hName, String hNickName){
		this.no = hNo;
		this.name = hName;
		this.nickName = hNickName;
	}

	// For display convenience, override the toString method


	@Override
	public String toString() {
		return "HeroNode{" +
				"no=" + no +
				", name='" + name + '\'' +
				", nickName='" + nickName + '\'' +
				'}';
	}
}


Single chain surface test

Find the number of effective nodes of the single linked list

	/**
	 *
	 * @param head  Node head of linked list
	 * @return Returns the number of valid nodes
	 */
	public Integer getLength(HeroNode head){
		if (head.next == null){
			// Empty linked list
			return 0;
		}
		int length = 0;
		// Define an auxiliary variable
		HeroNode cur =head.next;
		while (cur != null) {
			length++;
			cur = cur.next;
		}
		return length;
	}

Find the penultimate K node of the single linked list

	// Find the penultimate K node of the single linked list
	// Idea 1 write a method to receive the head node and receive the index (the penultimate index node)
	//     2 first calculate the length of the linked list to find the node of length index
	public HeroNode findNodeStartLast(HeroNode head ,int index){
		// If the linked list is empty, null is returned
		if (head.next == null){
			return null;
		}
		// Change the calendar to get the length of the linked list
		int length = this.getLength(head);
		// Traversal again returns the length - index
		// First do an index check
		if(index <= 0 || index > length){
			return null;
		}
		// Define a secondary node
		HeroNode temp = head.next;
		for(int i = 0 ;i < length-index ;i++ ){
			temp = temp.next;
		}
		return  temp;
	}

Reversal of single linked list (a little difficult)

	// Inversion of single linked list
	public HeroNode reverseNode(HeroNode head){
		if (head.next == null){
			return head;
		}
		HeroNode reverseHeroNode = new HeroNode(0, null, null);
		while (head.next != null){
			if (reverseHeroNode.next == null){
				reverseHeroNode.next = head.next;
				head.next = head.next.next;
				reverseHeroNode.next.next = null;
			}else {
				HeroNode temp = reverseHeroNode.next;
				reverseHeroNode.next = head.next;
				head.next = head.next.next;
				reverseHeroNode.next.next = temp;
			}
		}
		head.next = reverseHeroNode.next;
		return head;
	}

Print the list of orders from the beginning to the end

	// Using stack to print single linked list in reverse order
	public static void reversePrint(HeroNode head){
		if(head.next == null) {
			System.out.println("Queue is empty,Single linked list cannot be printed in reverse order");
			return;
		}
			HeroNode temp = head;
			Stack<HeroNode> heroNodeStack = new Stack<>();
			while (temp.next != null){
				heroNodeStack.add(temp.next);
				temp = temp.next;
			}
			while (heroNodeStack.size() > 0){
				System.out.println(heroNodeStack.pop());
			}
	}

Bidirectional linked list

Single linked list problem


code implementation

package com.luyi.DataStructures.linkedlist;

/**
 * @author Lu Yi
 * @create 2020-12-02 22:06
 */
public class DoubleLinkedListDemo {
	public static void main(String[] args) {
		System.out.println("A test of bidirectional linked list");
		// Create node first
		HeroNode2 heroNode1 = new HeroNode2(1, "Song Jiang", "Timely rain");
		HeroNode2 heroNode2 = new HeroNode2(2, "Lu Junyi", "Jade Unicorn");
		HeroNode2 heroNode3 = new HeroNode2(3, "Wu Yong", "Zhiduoxing");
		HeroNode2 heroNode4 = new HeroNode2(4, "Lin Chong", "Leopard head");

		//Create a two-way linked list object
		DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
		doubleLinkedList.add(heroNode1);
		doubleLinkedList.add(heroNode2);
		doubleLinkedList.add(heroNode3);
		doubleLinkedList.add(heroNode4);

		doubleLinkedList.list();

		// Modify test
		System.out.println();
		System.out.println("Modify test");
		HeroNode2 newHeroNode = new HeroNode2(4, "Gongsun Sheng", "Ruyunlong");
		doubleLinkedList.update(newHeroNode);
		doubleLinkedList.list();

		// Test delete
		System.out.println("Delete test");
		doubleLinkedList.delete(3);
		doubleLinkedList.list();

		// Add test in order
		System.out.println();
		System.out.println("Add test in order");
		HeroNode2 newHeroNode2 = new HeroNode2(0, "Small worker", "Father in law");
		doubleLinkedList.addOrder(newHeroNode2);
		doubleLinkedList.list();
	}
}

// Create a class of two-way linked list
class DoubleLinkedList {
	// Initialize the header node and nod the node. Don't move and don't store specific data
	private HeroNode2 head =new HeroNode2(0,null,null);

	public HeroNode2 getHead() {
		return head;
	}

	public void setHead(HeroNode2 head) {
		this.head = head;
	}

	// The method of traversing a two-way linked list is the same as that of a single linked list
	// Display linked list traversal
	public void list(){
		// Judge whether the linked list is empty
		if(head.next == null){
			System.out.println("The linked list is empty");
			return;
		}
		// Because the head node cannot be moved, we need a replication node temp
		HeroNode2 temp = head.next;
		while(true){
			// Output the information of this node
			System.out.println(temp);
			if(temp.next == null){
				break;
			}
			// Move temp backward, otherwise it will be an endless loop
			temp = temp.next;
		}
	}

	// This method is added to the tail of the bidirectional linked list by default
	public void add(HeroNode2 heroNode){
		// Because the head node cannot be moved, we need an auxiliary node temp
		HeroNode2 temp = head;
		// Traverse the linked list to find the last
		while (true){
			// Find the end of the linked list
			if(temp.next == null){
				break;
			}
			// If not found, move temp back
			temp = temp.next;
		}
		// When exiting the white loop, temp points to the end of the linked list
		// Form a two-way linked list
		temp.next=heroNode;
		heroNode.pre = temp;
	}

	// Add double linked list in order
	void addOrder(HeroNode2 heroNode) {
		HeroNode2 temp = head.next;
		boolean flag = false; // Identifies whether it can be inserted
		if (head.next == null){
			heroNode.pre = head;
			head.next = heroNode;
		}else {
			while (true) {
				if (temp.no == heroNode.no){
					System.out.println("The number already exists and cannot be added");
					flag = true;
					break;
				}else if (temp.no > heroNode.no){
					break;
				}
				if(temp.next == null){
					break;
				}
				temp = temp.next;
			}
			if (!flag){
				heroNode.next = temp;
				heroNode.pre = temp.pre;
				temp.pre.next=heroNode;
				temp.pre=heroNode;
			}
		}

	}

	// Modifying the order receiving content of a two-way linked list is the same as that of a one-way linked list, except that the type of node has changed
	public void update (HeroNode2 newHeroNode){
		if(head.next == null){
			System.out.println("The linked list is empty");
			return;
		}
		// Finding the node that needs to be modified is a no query
		HeroNode2 temp = head.next;
		boolean flag = false; // Indicates whether the node is found
		while (true) {
			if (temp == null) {
				break; // Indicates that the traversal of the linked list has ended (not that the last node has gone out)
			}
			if (temp.no == newHeroNode.no){
				// Find the node to modify
				flag = true;
				break;
			}
			temp = temp.next;
		}
		// Judge whether to find the node to be modified according to the flag
		if(!flag){
			System.out.println("The number was not found["+newHeroNode.no+ "]Node of");
		}else {
			temp.name = newHeroNode.name;
			temp.nickName = newHeroNode.nickName;
		}
	}

	// Delete a node from the bidirectional linked list
	// For a two-way linked list, you can directly find the node to be deleted, instead of finding the previous node of the node to be deleted like a single linked list
	// You can delete it after you find it
	public void delete(int no){
		HeroNode2 temp = head.next;
		// Judge whether the current linked list is empty
		if (temp == null) {
			System.out.println("The current linked list is empty and cannot be deleted");
		}
		boolean flag = false; // Flag whether the node to be deleted is found
		while (true) {
			if (temp.no == no){
				// The previous node of the node to be deleted was found
				flag = true;
				break;
			}
			temp = temp.next;
		}
		if (flag){
			// Can delete
			// temp.next = temp.next.next;  [single linked list]
			temp.pre.next = temp.next;
			if (temp.next != null) {
				//  If the last node is not deleted
				temp.next.pre = temp.pre;
			}
		}else {
			System.out.println("The was not found no=["+no+"]node,Cannot delete");
		}
	}

}


// Define a HeroNode, and each HeroNode object is a node
class HeroNode2 {
	public int no;
	public String name;
	public String nickName;
	public HeroNode2 next; // Point to the next node, which is null by default
	public HeroNode2 pre; // Point to the previous node, which is null by default

	// constructor 
	public HeroNode2(int hNo, String hName, String hNickName){
		this.no = hNo;
		this.name = hName;
		this.nickName = hNickName;
	}

	// For display convenience, override the toString method


	@Override
	public String toString() {
		return "HeroNode{" +
				"no=" + no +
				", name='" + name + '\'' +
				", nickName='" + nickName + '\'' +
				'}';
	}
}

Single circular linked list

josephus problem

Introduction to one-way ring linked list


Train of thought analysis

package com.luyi.DataStructures.linkedlist;

import com.sun.xml.internal.ws.wsdl.writer.document.soap.Body;
import jdk.nashorn.internal.ir.IfNode;

/**
 * josephus problem 
 * @author Lu Yi
 * @create 2020-12-03 16:49
 */
public class Joseph {
	public static void main(String[] args) {
		CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
		circleSingleLinkedList.addBoy(25);
		circleSingleLinkedList.solveJoseph(1, 2, 25);
		//circleSingleLinkedList.list();
	}
}

// Create a circular single linked list
class CircleSingleLinkedList {
	// Create a first node. There is no number at present. You are setting the number
	private Boy first = new Boy(-1);

	// Add children's nodes to build a circular linked list
	public void addBoy(int nums) {
		// nums does a data check
		if (nums < 1 ) {
			System.out.println("nums The value of is incorrect");
			return;
		}
		Boy currentBoy = null; // Auxiliary pointers help build circular linked lists
		// Use a for loop to create a circular linked list
		for (int i =1; i <= nums; i++) {
			// Create child nodes by number
			Boy newBoy = new Boy(i);
			// If it's the first child
			if (i == 1){
				first = newBoy;
				first.setNext(first); // Form a ring
				currentBoy = first; // Let currentBoy point to the first child, and the first node cannot be moved
			}else {
				currentBoy.setNext(newBoy);
				newBoy.setNext(first);
				currentBoy = newBoy;
			}
		}
	}

	// Traverse the current circular linked list
	public void list(){
		Boy currentBoy = first;
		if (currentBoy.getNo() == -1){
			System.out.println("The current circular linked list is empty,Unable to traverse");
			return;
		}
		while (true) {
			System.out.println("Child number"+currentBoy.getNo());
			currentBoy = currentBoy.getNext();
			if (currentBoy == first){
				break;
			}
		}
	}

	// Calculate the order of the child's circle according to the user's input

	/**
	 *
	 * @param startNo  It means counting from the first child
	 * @param countNum It means counting
	 * @param num Indicates how many children there were at first
	 * @return
	 */
	public void solveJoseph(int startNo, int countNum, int num){
		// Check the data first
		if (first.getNo() == -1 || startNo < 1 || startNo > num){
			System.out.println("Incorrect parameter input,Please re-enter");
			return;
		}
		// Create an auxiliary pointer helper to help complete the child's circle
		Boy helper = first;
		// Let the helper point to the last node of the ring queue first
		while (true) {
			if (helper.getNext() == first) {
				break;
			}
			helper = helper.getNext();
		}
		//Let the child move first before no-starter
		for (int j = 0; j < startNo-1; j++) {
			first = first.getNext();
			helper = helper.getNext();
		}
		// When the child counts off, let the first and helper pointers move countNum - 1 time at the same time, and then circle
		// Here is a loop operation until there is only one node in the circle
		while (true) {
			if (helper == first) { // There is only one person in the current circle
				System.out.print("Last circle: "+first.getNo()+"");
				break;
			}
			for (int i = 0; i < countNum -1; i++ ) {
				first = first.getNext();
				helper = helper.getNext();
			}
			// This is the child's circle after the first point
			System.out.print(first.getNo()+" ");
			first = first.getNext();
			helper.setNext(first);

		}


	}

}


// Create a Boy class to identify a node
class Boy {
	private int no; // number
	private Boy next; // Point to the next node, which is null by default

	public Boy(int no) {
		this.no = no;
	}

	public int getNo() {
		return no;
	}

	public void setNo(int no) {
		this.no = no;
	}

	public Boy getNext() {
		return next;
	}

	public void setNext(Boy next) {
		this.next = next;
	}
}

Stack

introduce



Array simulation stack

code implementation

package com.luyi.DataStructures.stack;

import java.lang.reflect.Array;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @author Lu Yi
 * @create 2020-12-03 19:54
 */
public class ArrayStackDemo {
	public static void main(String[] args) {
		ArrayStack stack =new ArrayStack(4);
		stack.push(1);
		stack.push(2);
		stack.push(3);
		stack.push(4);
		System.out.println(stack.pop());
		System.out.println(stack.pop());

		System.out.println("Traversal stack");
		stack.list();
	}

}

// Define an ArrayStack to represent the stack
class ArrayStack {
	private int maxSize; // Stack size
	private int[] stack; // Array, array simulation stack, put the data of the stack into the array
	private int top = -1; //Indicates that the stack top is initialized to - 1

	// constructor 
	public ArrayStack (int maxSize) {
		this.maxSize = maxSize;
		stack = new int[this.maxSize];
	}

	// Stack full judgment
	public boolean isFull() {
		return top == (maxSize-1);
	}

	// Stack empty
	public boolean isEmpty() {
		return top == -1;
	}

	// Stack operation
	public void push (int value) {
		// Judge whether it is full
		if (isFull()){
			System.out.println("The stack is full,Unable to stack");
			return;
		}
		top++;
		stack[top] = value;
	}

	// Out of the stack returns the data at the top of the stack
	public int pop () {
		// First judge whether the stack is empty
		if (isEmpty()){
			throw new RuntimeException("Stack empty,no data");
		}
		return  stack[top--];
	}

	// Display stack information (traverse the stack). During traversal, it needs to be displayed from the top of the stack
	public void list() {
		if (isEmpty()) {
			System.out.println("Stack empty,no data");
			return;
		}
		int i = top;
		while (i >= 0){
			System.out.println(stack[i--]);
		}
	}


}

Stack implementation calculator

Train of thought analysis (infix expression)

Code implementation (regardless of parentheses)

package com.luyi.DataStructures.stack;

import java.awt.print.Pageable;
import java.util.Stack;

/**
 * @author Lu Yi
 * @create 2020-12-03 20:48
 */
public class Calculator {
	public static void main(String[] args) {
		// Complete the operation of the expression according to the previous idea
		String expression = "7*2*2-5+1-5+3-4";
		// Create two stacks, count stacks, and turn a symbol
		ArrayStack2 numStack = new ArrayStack2(10);
		ArrayStack2 operStack = new ArrayStack2(10);
		// Define the relevant variables required
		int index = 0; // For scanning
		int num1 = 0;
		int num2 = 0;
		int oper = 0;
		int res = 0;
		char ch = ' '; // Save the char of each scan to ch
		String keepNum = ""; // For splicing multiple bits
		// Start scanning Expression with the scanning statement of the while loop
		while (true) {
			// Get each character of Expression in turn
			ch = expression.substring(index, index + 1).charAt(0);
			// Judge whether it is numbers and symbols and deal with them accordingly
			if (operStack.isOper(ch)) { // If operator
				// Judge whether the current symbol stack is empty
				if (!operStack.isEmpty()) {
					// If there are operators in the symbol stack, compare them. If the priority of the current operator is less than or equal to the operator in the stack, you need to pop out two numbers from the number stack
					// Then pop out a symbol from the symbol stack for operation, put the obtained result into the number stack, and then put the current operator into the symbol stack
					if (operStack.priority(ch) <= operStack.priority(operStack.peak())) {
						num1 = numStack.pop();
						num2 = numStack.pop();
						oper = operStack.pop();
						res = numStack.cal(num1, num2, oper);
						// Put the result of the operation on the stack
						numStack.push(res);
						// Put the current operator on the symbol stack
						operStack.push(ch);
					}else {
						// If the priority of the current operator is higher than that of the operator in the stack, it will be directly put into the symbol stack
						operStack.push(ch);
					}
				}else {
					operStack.push(ch);
				}
			}else { // If it's a number, put it directly into the stack. Note that this is a character, not a real number
				// numStack.push(ch - 48);   In this case, there is a problem 13 + 1 = > '1', '3' + '1'
				// When processing multi digit numbers, you can't find a number and put it on the stack immediately, because it may be multi digit numbers
				// When processing numbers, you need to look at one bit after the index of the expression. If it is a number, it will be scanned. If it is a symbol, it will be put on the stack
				// Therefore, we need to define a variable keepNum string to splice multiple bits

				//Number of processing
				keepNum += ch;

				// If ch is the last bit of expression, it is directly put on the stack
				if (index == expression.length()-1){
					numStack.push(ch - 48);
				}else {
					// Judge whether the next character is an array, continue scanning, and if it is an operator, put it on the stack
					// Just look at the last one, not the index++
					if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
						// If the latter bit is an operator, the number is stacked
						numStack.push(Integer.parseInt(keepNum));
						// important!!!!!! Empty keepNum
						keepNum = "";
					}
				}
 			}
			// index +1 and judge whether to scan to the end
			index++;
			if (index >= expression.length()) {
				break;
			}
		}
		// When the expression is scanned, pop out the corresponding numbers and symbols from the number stack and symbol stack in sequence and run
		while (true) {
			// If the symbol stack is empty, there is only one result in the number stack calculated to the last result
			if (operStack.isEmpty()) {
				break;
			}
			num1 = numStack.pop();
			num2 = numStack.pop();
			oper = operStack.pop();
			res = numStack.cal(num1, num2, oper);
			numStack.push(res);
		}
		System.out.println(expression+" = "+res);
	}
}

// You need to create an extension stack directly
// Define an ArrayStack to represent the stack
class ArrayStack2 {
	private int maxSize; // Stack size
	private int[] stack; // Array, array simulation stack, put the data of the stack into the array
	private int top = -1; //Indicates that the stack top is initialized to - 1

	// constructor 
	public ArrayStack2 (int maxSize) {
		this.maxSize = maxSize;
		stack = new int[this.maxSize];
	}

	// Stack full judgment
	public boolean isFull() {
		return top == (maxSize-1);
	}

	// Stack empty
	public boolean isEmpty() {
		return top == -1;
	}

	// Stack operation
	public void push (int value) {
		// Judge whether it is full
		if (isFull()){
			System.out.println("The stack is full,Unable to stack");
			return;
		}
		top++;
		stack[top] = value;
	}

	// Out of the stack returns the data at the top of the stack
	public int pop () {
		// First judge whether the stack is empty
		if (isEmpty()){
			throw new RuntimeException("Stack empty,no data");
		}
		return  stack[top--];
	}

	// Display stack information (traverse the stack). During traversal, it needs to be displayed from the top of the stack
	public void list() {
		if (isEmpty()) {
			System.out.println("Stack empty,no data");
			return;
		}
		int i = top;
		while (i >= 0){
			System.out.println(stack[i--]);
		}
	}

	// View the value at the top of the stack and do not exit the stack
	public int peak() {
		if (top == -1) {
			System.out.println("Empty stack");
			return -1;
		}
		return stack[top];
	}

	// The finite sum of the return operator assumes that the larger the number of the return value, the higher the priority
	public int priority(int oper){
		if (oper == '*' || oper == '/') { // java can compare numbers and characters
			return 1;
		}else if(oper == '+' || oper == '-') {
			return 0;
		}else {
			return -1; // Jiading has only addition, subtraction, multiplication and division in the current calculation formula
		}
	}

	// Judge whether it is an operator
	public boolean isOper(char val) {
		return val == '+' || val == '-' || val == '*' || val == '/';
	}

	// computing method
	public int cal(int num1, int num2, int oper ){
		int res = 0;
		switch (oper){
			case '+' :
				res = num1 + num2;
				break;
			case '-' :
				res = num2 - num1; // Pay attention to the order
				break;
			case '*' :
				res = num2 * num1;
				break;
			case '/' :
				res = num2 / num1; // Pay attention to the order
				break;
			default:break;
		}
		return res;
	}


}

Prefix infix suffix (inverse Polish) expression

Prefix expression (Polish expression)


Infill

Suffix (inverse Polish expression)

Inverse Polish calculator

code implementation

package com.luyi.DataStructures.stack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * @author Lu Yi
 * @create 2020-12-07 8:45
 */
public class PolandNotation {

	public static void main(String[] args) {
		// First define an inverse Polish expression
		//(3+4)*5-6 => 3 4 + 5 * 6 -
		// For convenience, the middle is separated by a space
		String suffixExpression = "3 4 + 5 * 6 -";
		// 1 now put suffixExpression into an ArrayList
		// 2 pass the ArrayList to a method to traverse the ArrayList and complete the calculation with the stack
		List<String> rpnList=getListString(suffixExpression);
		System.out.println("rpnList:"+rpnList);
		System.out.println("The result is: "+calculator(rpnList) );

	}

	// Put an inverse expression and put data and operators into an ArrayList at a time
	public static List<String> getListString(String suffixExpression) {
		// Separate suffixExpression by spaces
		String[] split = suffixExpression.split(" ");
		List<String> list = new ArrayList<String>(Arrays.asList(split));
		return list;
	}
    // Complete the operation of the inverse Polish expression
	// 1. Scan from left to right and press 3 and 4 into the stack;
	// 2. Encounter the + operator, so pop up 4 and 3 (4 is the top element of the stack and 3 is the secondary top element), calculate the value of 3 + 4, get 7, and then put 7 on the stack;
	// 3. Put 5 into the stack;
	// 4. Next is × Operator, so pop up 5 and 7 and calculate 7 × 5 = 35, put 35 into the stack;
	// 5. Put 6 into the stack;
	// 6. Finally, the - Operator calculates the value of 35-6, i.e. 29, so as to obtain the final result
	public static int calculator(List<String> ls) {
		// Creating a stack requires only one
		Stack<String> stack = new Stack<>();
		// Traversal ls
		for(String item : ls) {
			// Use a regular expression to get the number
			if(item.matches("\\d+")) { // The number of multiple bits matches
				// Push 
				stack.push(item);
			}else { // If operator
				// pop out two numbers and operate
				int b = Integer.parseInt(stack.pop());
				int a = Integer.parseInt(stack.pop());
				int res = 0;
				switch (item) {
					case "+":
						res = a+b;
						break;
					case "-":
						res = a-b;
						break;
					case "*":
						res = a*b;
						break;
					case "/":
						res = a/b;
						break;
					default:
						throw new RuntimeException("There is a problem with the symbol");
				}
				stack.push(res+"");
			}
		}
		return Integer.parseInt(stack.pop());
	}
}

Convert infix expression to suffix expression



code implementation

package com.luyi.DataStructures.stack;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * @author Lu Yi
 * @create 2020-12-07 8:45
 */
public class PolandNotation {

	public static void main(String[] args) {

		// Complete the function of converting infix expression into suffix expression
		// 1.  1+((2+3)*4)-5   =>     1 2 3 + 4 * + 5 -
		// 2. Because it is inconvenient to directly operate Str, first convert 1 + ((2 + 3) * 4) - 5 to the List corresponding to infix expression
		//     ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
		// 3. List of infix expression = > list of suffix expression
		// 4.  ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] =>  ArrayList [1,2,3,+,4,*,+,5]
		String expression = "1+((2+3)*4)-5";
		System.out.println("Infix expression:"+ toInfixExpression(expression));
		List<String> parseSuffixExpressList = parseSuffixExpressionList(toInfixExpression(expression));
		System.out.println("Reverse Polish notation :" +parseSuffixExpressList );
		//result
		System.out.println("expression:"+expression+"="+ calculator(parseSuffixExpressList));


		// First define an inverse Polish expression
		//(3+4)*5-6 => 3 4 + 5 * 6 -
		//(30+4)*5-6 => 30 4 + 5 * 6 -
		//4*5-8+60+8/2 =>  4 5 * 8 - 60 + 8 2 / +
		// For convenience, the middle is separated by a space
		String suffixExpression = "4 5 * 8 - 60 + 8 2 / +";
		// 1 now put suffixExpression into an ArrayList
		// 2 pass the ArrayList to a method to traverse the ArrayList and complete the calculation with the stack
		List<String> rpnList=getListString(suffixExpression);
		System.out.println("rpnList:"+rpnList);
		System.out.println("The result is: "+calculator(rpnList) );

	}
	// Convert infix expression to corresponding List
	public static List<String> toInfixExpression(String s) {
		// Define an ArrayList to store the contents of infix expressions
		List<String> arrayList = new ArrayList<String>();
		int i = 0;
		String str; // Splice multiple numbers
		char c; // Put each character into c
		do {
			// If c is a non number, add it directly to ls
			if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) < 57 ){
				arrayList.add(c + "");
				i++;
			}else { // If it is a number, we need to consider the problem of multiple numbers
				str = ""; // str null
				while (i < s.length() && (s.charAt(i) >= 48 && s.charAt(i) <= 57)) {
					str += c;
					i++;
				}
				arrayList.add(str);
			}
		}while (i < s.length());
		return arrayList;
	}

	// List of infix expression = > list of suffix expression LS = ArrayList [1, +, (, (, 2, +, 3,), *, 4,), -, 5]
	public static List<String> parseSuffixExpressionList(List<String> ls) {
		// Define two stacks
		Stack<String> s1 = new Stack<String>(); // Symbol stack
		// The second stack has no pop operation in the whole conversion process, and we need to output it in reverse order later. We replace it with list < string > S2
		// Stack<String> s2 = new Stack<String>();
		List<String> s2 = new ArrayList<String>();

		// Traversal ls
		for (String item : ls) {
			// If it is a number, add s2
			if(item.matches("\\d+")) {
				s2.add(item);
			}else if (item.equals("(")) {
				s1.push(item);
			}else if (item.equals(")")) {
				//If it is the closing parenthesis ")", the operators at the top of s1 stack will pop up in turn and press s2 until the left parenthesis is encountered. At this time, this pair of parentheses will be discarded
				while (!s1.peek().equals("(")){
					s2.add(s1.pop());
				}
				s1.pop(); // Pop up(
			}else {
				// When the priority of item is less than that of the operator at the top of s1 stack, pop up the operator at the top of s1 stack and add it to s2. Go to (4.1) again and compare it with the new operator at the top of s1 stack
				while (s1.size() != 0 && (Operation.getValue(item) <= Operation.getValue(s1.peek()))) {
					s2.add(s1.pop());
				}
				// You also need to stack the Item
				s1.push(item);
			}
		}
		// Add the remaining operators of s1 to s2
		while (s1.size() !=0){
			s2.add(s1.pop());
		}
		return s2; // Because it exists in the list without reverse order, the normal output is an inverse expression
	}
	// Put an inverse expression and put data and operators into an ArrayList at a time
	public static List<String> getListString(String suffixExpression) {
		// Separate suffixExpression by spaces
		String[] split = suffixExpression.split(" ");
		List<String> list = new ArrayList<String>(Arrays.asList(split));
		return list;
	}

    // Complete the operation of the inverse Polish expression
	// 1. Scan from left to right and press 3 and 4 into the stack;
	// 2. Encounter the + operator, so pop up 4 and 3 (4 is the top element of the stack and 3 is the secondary top element), calculate the value of 3 + 4, get 7, and then put 7 on the stack;
	// 3. Put 5 into the stack;
	// 4. Next is × Operator, so pop up 5 and 7 and calculate 7 × 5 = 35, put 35 into the stack;
	// 5. Put 6 into the stack;
	// 6. Finally, the - Operator calculates the value of 35-6, i.e. 29, so as to obtain the final result
	public static int calculator(List<String> ls) {
		// Creating a stack requires only one
		Stack<String> stack = new Stack<>();
		// Traversal ls
		for(String item : ls) {
			// Use a regular expression to get the number
			if(item.matches("\\d+")) { // The number of multiple bits matches
				// Push 
				stack.push(item);
			}else { // If operator
				// pop out two numbers and operate
				int b = Integer.parseInt(stack.pop());
				int a = Integer.parseInt(stack.pop());
				int res = 0;
				switch (item) {
					case "+":
						res = a+b;
						break;
					case "-":
						res = a-b;
						break;
					case "*":
						res = a*b;
						break;
					case "/":
						res = a/b;
						break;
					default:
						throw new RuntimeException("There is a problem with the symbol");
				}
				stack.push(res+"");
			}
		}
		return Integer.parseInt(stack.pop());
	}
}
// Write a class Operation to return the priority corresponding to an operator
class Operation {
	private static int ADD = 1;
	private static int SUB = 1;
	private static int MUL = 2;
	private static int DIV = 2;

	// Write a method that returns a priority number
	public static int getValue(String operation) {
		int result = 0;
		switch (operation){
			case "+":
				result = ADD;
				break;
			case "-":
				result = SUB;
				break;
			case "*":
				result = MUL;
				break;
			case "/":
				result = DIV;
				break;
			default:
				System.out.println("The operator does not exist");
				break;
		}
		return result;
	}

}

recursion

Problems that recursion can solve

Important rules of recursion

Maze problem

code implementation

package com.luyi.DataStructures.recursion;

import com.sun.org.apache.xml.internal.resolver.helpers.PublicId;

/**
 * @author Lu Yi
 * @create 2020-12-07 16:01
 */
public class MiGong {
	public static void main(String[] args) {
		// Create a two-dimensional array to simulate the maze
		int[][] map = new int[8][7];
		// Use 1 for walls
		// Upper and lower position 1
		for (int i = 0; i < 7; i++ ) {
			map[0][i] = 1;
			map[7][i] = 1;
		}
		//Left and right position 1
		for (int i = 0; i < 8; i++ ) {
			map[i][0] = 1;
			map[i][6] = 1;
		}
		//
		// Set baffle 1 to indicate
		map[3][1] = 1;
		map[3][2] = 1;
		//map[1][2] = 1;
		//map[2][2] = 1;
		// Output map
		System.out.println("Output map");
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 7; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
		// Using recursive backtracking to find the path map is a reference type, which can dynamically change the value equal to the public variable
		if(setWay(map, 1, 1)){
			// Export new map
			System.out.println("Path of the ball");
			for (int i = 0; i < 8; i++) {
				for (int j = 0; j < 7; j++) {
					System.out.print(map[i][j] + " ");
				}
				System.out.println();
			}
		}else {
			System.out.println("Unable to find");
		}


	}

	// Use recursive backtracking to find the way for the ball
	// Description map is a map
	//     i. J indicates where to start (i,j)
	//     If the ball reaches map[6][5] = the path is found
	//     It is agreed that when map[i][j] is 0, it means that the point has not passed. 1 is the wall, 2 is the path (path of small ball) and 3 is that the position has passed but can't pass
	//     When going through the maze again, you need to determine a strategy (the direction of action, when you can't get through, go to the next direction of the strategy) down - > right - > up - > left. If you can't get through at this point, go back
	/**
	 *
	 * @param map Map
	 * @param i Where do you start
	 * @param j
	 * @return Returns true if the path is found, otherwise false
	 */
	public static boolean setWay(int[][] map, int i, int j) {
		if (map[6][5] == 2){
			// Indicates that the path has been found
			return true;
		}else {
			//If the current point has not passed
			if (map[i][j] == 0){
				// Try down - > right - > Top - > left according to the above strategy
				map[i][j] = 2; // False current point can go
				if (setWay(map, i + 1, j )){ // Go down
					return true;
				}else if (setWay(map,i , j + 1)){ // turn right
					return true;
				}else if (setWay(map, i - 1, j)){ // Go up
					return true;
				}else if (setWay(map, i,j - 1)){ // turn left
					return true;
				}else {
					// It's a dead end to fail to get through this point
					map[i][j] = 3;
					return false;
				}
			}else { // Ken can't walk for 1 is the wall 2 goes through 3
				 return false;
			}
		}
	}

}

Shortest path analysis

At present, the more stupid method
Set all the strategies in four directions: up, down, left, right, left, right, left, right, left, right, left, right, left, right, left, right, left, left, right, left, right, left, right, left, right, left, right, left, right, left, right, left, right, left, right, left, right, left, right, left, right, left

Eight queens problem



code implementation

package com.luyi.DataStructures.recursion;

/**
 * @author Lu Yi
 * @create 2020-12-07 18:25
 */
public class Queen {
	// Define a max to indicate how many queens there are
	int max = 8;
	static int count = 0;
	// Define an array to save the results of Queen placement. Arr [8] = {0, 4, 7, 5, 2, 6, 1, 3}
	int[] arr = new int[max];
	public static void main(String[] args) {
		// Test one
		Queen queen = new Queen();
		queen.check(0); // Put it in the first position


	}
	// Write a method to place the n th queen
	// Note that when entering the check, there will be a for loop, so there will be backtracking
	private void check(int n) {
		if(n == max){ // max has put it in place after changing
			print();
			return;
		}
		// Put the queen in turn to judge whether there is conflict
		for (int i = 0; i < max; i++) {
			// First put the current queen in the first column of the row
			arr[n] = i;
			// Is there a conflict when placing the queen to column i
			if (judge(n)){ // No conflict
				check(n + 1);
			}// If there is a conflict, continue to execute arr[n] = i; Move the line back one position
		}
	}
	/**
	 * Check whether the queen conflicts with the queen already placed in front when placing the nth queen
	 * @param n The n th queen
	 * @return
	 */
	private boolean judge(int n) { // Indicates the nth queen of the
		for (int i = 0; i < n; i++){
			// arr[i] == arr[n] judge whether the nth queen and the ith queen are on the same line
			// Math.abs(n - i) == Math.abs(arr[n] - arr[i]) determines whether the nth queen and the ith queen are on the same slash (because it is currently a one-dimensional array, and the two-dimensional array needs
			//   (by other methods)
			// n = 1 represents the second queen. If it is placed in the second row of the second column, arr[1] = 1
			// Math.abs(1-0) == 1   Math.abs(1 - 0) == Math.abs(1 - 0) established
			// You don't need to judge the same line because n is increasing
			if (arr[i] == arr[n] || Math.abs(n - i) == Math.abs(arr[n] - arr[i])){ // Math.abs is absolute
				return false;
			}
		}
		return true;
	}

	// Write a position for the printing queen
	private void print() {
		System.out.print("The first"+(++count)+"species: ");
		for (int i = 0;i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}
}

Sorting algorithm

Time complexity

Time frequency


Conclusion:

  1. 2n+20 and 2n as n becomes larger, the execution curve is infinitely close, and 20 can be ignored
  2. 3n+10 and 3n as n becomes larger, the execution curve is infinitely close, and 10 can be ignored

Conclusion:

  1. 2n^2+3n+10 and 2n^2 as n becomes larger, the execution curve is infinitely close, and 3n+10 can be ignored
  2. As n^2+5n+20 and n^2 become larger, the execution curve is infinitely close, and 5n+20 can be ignored

Neglect coefficient (not to be ignored for 3rd power and above)

Time complexity









Spatial complexity

Bubble sorting

The basic idea of Bubble Sorting is to compare the sorting sequence from front to back (starting from the elements with smaller subscripts)
If the values of adjacent elements are found to be in reverse order, they will be exchanged, so that the elements with larger values will gradually move from the front to the back, just like bubbles under the water.

Optimization:
Because in the process of sorting, each element is constantly close to its own position. If there is no exchange after a comparison, it indicates that the sequence is orderly. Therefore, it is necessary to
During sorting, set a flag flag to judge whether the elements have been exchanged. This reduces unnecessary comparisons. (the optimization mentioned here can be in the bubbling row
(after the preface is written, proceed)

Code implementation (step)

package com.luyi.sort;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * Bubble sorting
 * @author Lu Yi
 * @create 2020-12-08 13:46
 */
public class BubbleSort {
	public static void main(String[] args) {
		int arr[] = {3,9,-1,10,-2};

		// Show the evolution process of bubble sorting, and compare arr.length-1 times to get the results
		/**
		 * Array after the first sorting
		 * [3, -1, 9, -2, 10]
		 * Array after the second sorting
		 * [-1, 3, -2, 9, 10]
		 * Array after the third sorting
		 * [-1, -2, 3, 9, 10]
		 * Array after the fourth sorting
		 * [-2, -1, 3, 9, 10]
		 */

		// The first sort is to put the largest number last
		int temp = 0; // Temporary variable
		for(int j = 0; j < arr.length - 1; j++ ){
			if(arr[j] > arr[j + 1]){
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j + 1] = temp;
			}
		}
		System.out.println("Array after the first sorting");
		System.out.println(Arrays.toString(arr));

		// For the second sorting, put the second largest number in the penultimate place, and the last number does not participate in the sorting
		for(int j = 0; j < arr.length - 2; j++ ){
			if(arr[j] > arr[j + 1]){
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j + 1] = temp;
			}
		}
		System.out.println("Array after the second sorting");
		System.out.println(Arrays.toString(arr));

		// For the third sorting, put the third largest number in the penultimate place, and the last two numbers do not participate in the sorting
		for(int j = 0; j < arr.length - 3; j++ ){
			if(arr[j] > arr[j + 1]){
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j + 1] = temp;
			}
		}
		System.out.println("Array after the third sorting");
		System.out.println(Arrays.toString(arr));

		// For the fourth sorting, put the fourth largest number in the penultimate position, and the last three numbers do not participate in the sorting
		for(int j = 0; j < arr.length - 4; j++ ){
			if(arr[j] > arr[j + 1]){
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j + 1] = temp;
			}
		}
		System.out.println("Array after the fourth sorting");
		System.out.println(Arrays.toString(arr));
	}
}

Integrated code

	int temp = 0; // Temporary variable
		for (int i = 0; i < arr.length -1; i++){
			for (int j = 0; j< arr.length -1 -i;j++){
				if(arr[j] > arr[j + 1]){
					temp = arr[j];
					arr[j] = arr[j+1];
					arr[j + 1] = temp;
				}
			}
		}
		System.out.println("Bubble sorted array");
		System.out.println(Arrays.toString(arr));

Time complexity O(n^2)

Optimization of bubble sorting

		int arr[] = {3,9,-1,10,20};
		int count = 0; // How many times did you run
		int temp = 0; // Temporary variable
		boolean flag = false; // The identification variable indicates whether to exchange
		for (int i = 0; i < arr.length -1; i++){
			count++;
			for (int j = 0; j< arr.length -1 -i;j++){
				if(arr[j] > arr[j + 1]){
					temp = arr[j];
					arr[j] = arr[j+1];
					arr[j + 1] = temp;
					flag = true;
				}
			}
			if (!flag){ // None of the exchanges have taken place, which means that the order has been arranged and there is no need to conduct n-1 again
				break;
			}else {
				flag = false;
			}
		}
		System.out.println("Run away"+count+"Trip");
		System.out.println("Bubble sorted array");
		System.out.println(Arrays.toString(arr));
		/**
		 * Three times
		 * Bubble sorted array
		 * [-1, 3, 9, 10, 20]
		 */

Mr. Han's computer processes 80000 random numbers in about 20 seconds

Select Sorting Algorithm


code implementation

package com.luyi.sort;

import com.sun.xml.internal.txw2.output.IndentingXMLFilter;

import java.util.Arrays;

/**
 * @author Lu Yi
 * @create 2020-12-08 14:27
 */
public class SelectSort {
	public static void main(String[] args) {
		int[] arr = {101,34,119,1};
		//selectSort(arr);   Step analysis
		selectSortAll(arr);
	}
	// Select sort
	public static void selectSort(int[] arr){
		// Use step-by-step derivation
		// first round
		// Original array 101,34119,1
		// First round sorting 1,34119101
		int minIndex = 0;
		int min = arr[0]; // Initial value
		for(int j = 1; j < arr.length;j++){
			if (min > arr[j]){
				minIndex = j;
				min = arr[j];
			}
		}
		int temp = arr[0];
		arr[0] = arr[minIndex];
		arr[minIndex] = temp;
		System.out.println("First round sorting");
		System.out.println(Arrays.toString(arr));

		// Second round
		// First round sorting 1, 34, 119, 101
		// Second round sorting 1, 34, 119, 101
		min = arr[1]; // Initial value
		minIndex = 1;
		for(int j = 1; j < arr.length;j++){
			if (min > arr[j]){
				minIndex = j;
				min = arr[j];
			}
		}
		temp = arr[1];
		arr[1] = arr[minIndex];
		arr[minIndex] = temp;
		System.out.println("Second round sorting");
		System.out.println(Arrays.toString(arr));

		// Third round
		// First round sorting 1, 34, 119, 101
		// Second round sorting 1, 34, 119, 101
		// Second round sorting 1, 34, 101, 119
		min = arr[2]; // Initial value
		minIndex = 2;
		for(int j = 2; j < arr.length;j++){
			if (min > arr[j]){
				minIndex = j;
				min = arr[j];
			}
		}
		temp = arr[2];
		arr[2] = arr[minIndex];
		arr[minIndex] = temp;
		System.out.println("Third round sorting");
		System.out.println(Arrays.toString(arr));

		/**
		 * First round sorting
		 * [1, 34, 119, 101]
		 * Second round sorting
		 * [1, 34, 119, 101]
		 * Third round sorting
		 * [1, 34, 101, 119]
		 */
	}
	// Complete code
	public static void selectSortAll(int[] arr){

		for (int i = 0; i < arr.length -1; i++){
			int min = arr[i];
			int minIndex = i;
			for (int j = i+1; j < arr.length; j++ ){
				if (min > arr[j]){
					min = arr[j];
					minIndex = j;
				}
			}
			if (minIndex != i) {
				int temp = arr[i];
				arr[i] = min;
				arr[minIndex] = temp;
			}
		}
		System.out.println("Select sort");
		System.out.println(Arrays.toString(arr));
	}

}

Time complexity O(n^2)

Mr. Han's computer processes 80000 random numbers for about 3 seconds

Insertion sort method

code implementation

There are a group of calves whose test scores are 101, 34, 119 and 1 respectively. Please rank them from small to large

package com.luyi.sort;

import java.util.Arrays;

/**
 * @author Lu Yi
 * @create 2020-12-08 15:09
 */
public class InsertSort {
	public static void main(String[] args) {
		int[] arr = {101,34,119,1};
		//insertSort(arr);  Step by step demonstration
		insertSortAll(arr);
	}
	// Insert sort
	public static void insertSort(int[] arr){
		// Use step-by-step derivation to explain, which is easy to understand
		// First round 101,34119,1 = > 34101119,1

		// Define a number to insert
		int insertVal = arr[1]; // Initialization because 101 is already in an ordered array, allowing the number to be inserted
		int insertIndex = 1 -1 ; // Initializes the previous number of the number to be inserted

		// Find the insertion position for insertVal
		// Insertindex > = 0 ensures that the inserted position does not exceed the limit
		// Insertval < arr [insertIndex] the number of inserts to be inserted needs to be moved back if the insertion position has not been found
		while (insertIndex >= 0 && insertVal < arr[insertIndex]){
			arr[insertIndex+1] = arr[insertIndex]; // 101 101 119 1
			insertIndex--; // Insertindex > = 0 terminates when it is less than zero
		}
		// When exiting the while loop, insertIndex + 1 is found at the insertion position (because insertIndex is the previous number of the number to be inserted when it is initialized)
		arr[insertIndex+1] = insertVal;
		System.out.println("After the first round");
		System.out.println(Arrays.toString(arr));

		// Second round 34, 101, 119, 1 = > 34, 101, 119, 1

		// Define a number to insert
		insertVal = arr[2]; // Initialization because 101 is already in an ordered array, allowing the number to be inserted
		insertIndex = 2 -1 ; // Initializes the previous number of the number to be inserted

		// Find the insertion position for insertVal
		// Insertindex > = 0 ensures that the inserted position does not exceed the limit
		// Insertval < arr [insertIndex] the number of inserts to be inserted needs to be moved back if the insertion position has not been found
		while (insertIndex >= 0 && insertVal < arr[insertIndex]){
			arr[insertIndex+1] = arr[insertIndex];
			insertIndex--; // Insertindex > = 0 terminates when it is less than zero
		}
		// When exiting the while loop, insertIndex + 1 is found at the insertion position (because insertIndex is the previous number of the number to be inserted when it is initialized)
		arr[insertIndex+1] = insertVal;
		System.out.println("After the second round");
		System.out.println(Arrays.toString(arr));

		// Third round 34, 101, 119, 1 = > 1, 34, 101, 119

		// Define a number to insert
		insertVal = arr[3]; // Initialization because 101 is already in an ordered array, allowing the number to be inserted
		insertIndex = 3 -1 ; // Initializes the previous number of the number to be inserted

		// Find the insertion position for insertVal
		// Insertindex > = 0 ensures that the inserted position does not exceed the limit
		// Insertval < arr [insertIndex] the number of inserts to be inserted needs to be moved back if the insertion position has not been found
		while (insertIndex >= 0 && insertVal < arr[insertIndex]){
			arr[insertIndex+1] = arr[insertIndex]; //
			insertIndex--; // Insertindex > = 0 terminates when it is less than zero
		}
		// When exiting the while loop, insertIndex + 1 is found at the insertion position (because insertIndex is the previous number of the number to be inserted when it is initialized)
		arr[insertIndex+1] = insertVal;
		System.out.println("After the third round");
		System.out.println(Arrays.toString(arr));
		/**
		 * After the first round
		 * [34, 101, 119, 1]
		 * After the second round
		 * [34, 101, 119, 1]
		 * After the third round
		 * [1, 34, 101, 119]
		 */
	}

	// Total insertion sort
	public static void insertSortAll(int[] arr){
		int insertIndex = 0; // Previous position of data to be inserted
		int insertValue = arr[0];
		for (int i = 1; i < arr.length; i++) {
			insertIndex = i - 1; // Previous position of data to be inserted
			 insertValue = arr[i];
			while (insertIndex >=0 && insertValue < arr[insertIndex]){
				arr[insertIndex + 1] = arr[insertIndex];// The previous number of the number to be inserted moves back
				insertIndex --; // Position to be inserted
			}
			// Determine whether assignment is required
			if (insertIndex + 1 != i){
				arr[insertIndex + 1] = insertValue; // When exiting the while loop, insertIndex + 1 is found at the insertion position (because insertIndex is the previous number of the number to be inserted when it is initialized)
			}
			}
		}
		System.out.println("Insert sort");
		System.out.println(Arrays.toString(arr));
	}
}

Time complexity O(n^2)

Mr. Han's computer sorted 80000 random numbers for about 5 seconds

Hash sorting algorithm diagram

Simple insertion sorting problem

Hill sort is an efficient version of insert sort

The efficiency of code implementation (exchange method) is not very high. Mr. Han's computer spent 17 seconds sorting 80000 random numbers

package com.luyi.sort;

import java.util.Arrays;

/**
 * @author Lu Yi
 * @create 2020-12-08 19:45
 */
public class HellSort {
	public static void main(String[] args) {
		int[] arr = {8,9,1,7,2,3,5,4,6,0};
		//Step by step
		//hellSort(arr);
		hellSortAll(arr);
	}
	// Write Hill sort using step-by-step push to (exchange method)
	public static void hellSort(int[] arr){
		// First round sorting of hill array
		// Because the first round of sorting divides 10 data into 10 / 2 = 5 groups
		int temp = 0;
		for (int i = 5; i < arr.length; i++){
			// Traverse all elements in each group (a total of five groups, two elements in each group) with a step field of 5, such as the comparison between the first number and the fifth number
			for(int j = i - 5; j >= 0; j -= 5){
				// If the current element is larger than the element with step size, it indicates the exchange
				if (arr[j] > arr[j + 5]) {
					temp = arr[j];
					arr[j] = arr[j + 5];
					arr[j + 5] = temp;
				}
			}
		}
		System.out.println("After the first round of sorting of hill array");
		System.out.println(Arrays.toString(arr));

		// Second round sorting of hill array
		// Because the second round of sorting divides 10 data into 5 / 2 = 2 groups
		for (int i = 2; i < arr.length; i++){
			// Traverse all elements in each group (a total of five groups, two elements in each group) with a step field of 5, such as the comparison between the first number and the fifth number
			for(int j = i - 2; j >= 0; j -= 2){
				// If the current element is larger than the element with step size, it indicates the exchange
				if (arr[j] > arr[j + 2]) {
					temp = arr[j];
					arr[j] = arr[j + 2];
					arr[j + 2] = temp;
				}
			}
		}
		System.out.println("After the second round of sorting of hill array");
		System.out.println(Arrays.toString(arr));

		// The third round of sorting of hill array
		// Because the third round of sorting divides 10 data into 2 / 2 = 1 groups
		for (int i = 1; i < arr.length; i++){
			// Traverse all elements in each group (a total of five groups, two elements in each group) with a step field of 5, such as the comparison between the first number and the fifth number
			for(int j = i - 1; j >= 0; j -= 1){
				// If the current element is larger than the element with step size, it indicates the exchange
				if (arr[j] > arr[j + 1]) {
					temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
				}
			}
		}
		System.out.println("After the third round of sorting of hill array");
		System.out.println(Arrays.toString(arr));
		/**
		 * After the first round of sorting of hill array
		 * [3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
		 * After the second round of sorting of hill array
		 * [0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
		 * After the third round of sorting of hill array
		 * [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
		 */
	}
	// Total Hill ranking (exchange method)
	public static void hellSortAll(int[]arr){
		int temp = 0;
		int group = arr.length/2;
		while (group != 0) {
			for (int i = group; i < arr.length; i++) {
				for (int j = i - group; j >= 0; j -= group) {
					if (arr[j] > arr[j + 1]) {
						temp = arr[j];
						arr[j] = arr[j + 1];
						arr[j + 1] = temp;
					}
				}
			}
			group /= 2;
		}
		System.out.println("Hill sort results");
		System.out.println(Arrays.toString(arr));
	}


}

The efficiency of code implementation (shift method) is high. Mr. Han's computer spent 1 second sorting 80000 random numbers

	// Optimize Hill sort method of exchange - > shift method
	public static void hellSortBetter(int[] arr){
		int temp = 0;
		int group = arr.length/2;
		while (group != 0) {
			// From group elements, directly insert and sort the groups one by one
			for (int i = group; i < arr.length; i++) {
				int insertIndex = i; //Location to insert
				temp = arr[insertIndex];
				if(arr[insertIndex] < arr[insertIndex - group]){
					while (insertIndex - group >= 0 && temp < arr[insertIndex - group]){
						// move
						arr[insertIndex] = arr[insertIndex - group];
						insertIndex -= group;
					}
					// The insertion position was found after exiting the while loop
					arr[insertIndex] = temp;
				}
			}
			group /= 2;
		}
		System.out.println("Hill sort results");
		System.out.println(Arrays.toString(arr));
	}

Time complexity O(n^(1.3-2))

Quick sorting algorithm


code implementation

package com.luyi.sort;

import java.util.Arrays;

/**
 * @author Lu Yi
 * @create 2020-12-08 21:06
 */
public class QuickSort {
	public static void main(String[] args) {
		int[] arr = {-9,78,0,23,-567,70};
		quickSort(arr, 0,arr.length-1 );
		System.out.println("arr: "+ Arrays.toString(arr));
	}

	/**
	 *
	 * @param arr
	 * @param left Index on the left
	 * @param right Index on the right
	 */
	public static void quickSort(int[] arr, int left, int right){
		int l = left; // Left subscript
		int r = right; // Right subscript
		int temp = 0; //Temporary variable
		// pivot axis
		int pivot = arr[(left + right) / 2];
		// As long as the index on the right is larger than the index on the left, the cycle continues. The purpose is to put the value smaller than pivot on the left and the value larger than pivot on the right
		while (l < r){
			// On the left of pivot, always find a value greater than or equal to pivot before exiting
			while (arr[l] < pivot){ //Find the pivot itself at most
				l += 1;
			}
			// On the left of pivot, always find a value less than or equal to pivot before exiting
			while (arr[r] > pivot){ //Find the pivot itself at most
				r -= 1;
			}
			// If it is true, it means that the values on the left of pivot have all been less than or equal to the values of pivot, and the values on the right have all been greater than or equal to the values of pivot
			if(l >= r){
				break;
			}
			// exchange
			temp = arr[l];
			arr[l] = arr[r];
			arr[r] = temp;

			// Judge if it is found that arr[l] = pivot r moves forward L after the exchange--
			if (arr[l] == pivot){
				r -= 1;
			}else if (arr[r] == pivot){// Judge if it is found that arr[r] = pivot l moves backward L after the exchange++
				l++;
			}
		}
		// If l == r, L + + and r --, otherwise stack overflow will occur
		if (l == r ){
			l++;
			r--;
		}
		// Left recursion
		if (left < r) {
			quickSort(arr,left,r);
		}
		// Recursive right
		if (right > l) {
			quickSort(arr, l, right);
		}
	}
}

Mr. Han's computer sorted 80000 random numbers in less than a second, 80w data in less than a second, 800W in 2-3 seconds

The time complexity of fast scheduling is O (nlogn), but the space complexity is high

Merge sort


code implementation

package com.luyi.sort;

import java.util.Arrays;
import java.util.TimerTask;

/**
 * Merge sort
 * @author Lu Yi
 * @create 2020-12-09 9:50
 */
public class MergeSort {
	public static void main(String[] args) {
		int[] arr = {8,4,5,7,1,3,6,2};
		int[] temp = new int[arr.length]; // Merging and sorting requires additional space
		mergeSort(arr, 0, arr.length-1, temp);

		System.out.println("After merging and sorting: "+ Arrays.toString(arr));
	}

	//Opening + closing method
	public static void mergeSort(int[] arr, int left, int right, int[] temp){
		if (left < right) {
			int mid = (left + right) / 2; // Intermediate index
			//Decompose recursively to the left
			mergeSort(arr, left, mid, temp);
			// Decompose recursively to the right
			mergeSort(arr, mid+1, right, temp);

			// The above is the decomposition method
			// Merge once after each decomposition
			merge(arr, left, mid, right,temp);
		}
	}

	/**
	 *  Merging method
	 * @param arr Original array
	 * @param left Initial index of left ordered sequence
	 * @param mid  Intermediate index
	 * @param right Index right
	 * @param temp  Transit array
	 */
	public static void merge(int[] arr,int left, int mid, int right, int[] temp){
		int i = left; //Initialization i, the initial index of the ordered sequence on the left
		int j = mid+1;// Initialize j the initial index on the right
		int t = 0; //Initialize the index of temp array

		// First fill the left and right (ordered) data into temp according to the rules
		// Until one of the ordered sequences on the left and right is processed
		while (i <= mid && j <= right){
			// If the current element of the ordered sequence on the left < = the current element of the ordered sequence on the right, put the current element on the left at the position of t of temp
			if (arr[i] <= arr[j]){
				temp[t++] = arr[i++];// Put back
			}else {
				temp[t++] = arr[j++];
			}
		}
		// Add the data of the remaining array to the tail of temp at one time
		while (i <= mid){ //The ordered sequence on the left has the remaining data. Add the remaining ordered data to the temp array in turn
			temp[t++] = arr[i++];
		}
		while (j <=right){ //The ordered sequence on the right has the remaining data. Add the remaining ordered data to the temp array in turn
			temp[t++] = arr[j++];
		}

		// Put the temp array back into the arr
		// Note that not all are copied at a time
		t = 0;
		int tempLeft = left;// The first merge tempLeft=0 right=1 / / the second merge tempLeft=2 right=3 / / the third merge tempLeft=0 right=3
		//  Last merge tempLeft=0 right=7
		while (tempLeft <= right){
			arr[tempLeft++] = temp[t++];
		}
	}

}

Time complexity O(nlogn) Mr. Han's computer sorted 80000 random numbers in less than 0-1 seconds, 80w a second and 800w3-4 seconds

Cardinality sort (bucket sort)


Stable sorting: if the array to be sorted has two identical numbers, such as A1 = A2 = 1 {a1,2,3}, A2} after sorting {a1,a2,2,3} a1 is still in front of A2



code implementation

package com.luyi.sort;

import java.util.Arrays;

/**
 * @author Lu Yi
 * @create 2020-12-09 13:43
 */
public class RadixSort {
	public static void main(String[] args) {
		int[] arr = {53,3,542,748,14,214};
		//radixSort(arr);
		radixSortAll(arr);
	}
	// Radix sort 
	public static void radixSort(int[] arr){
		// Simulate one round of sorting (sorting for the single digit of each element)

		// Define a two-dimensional array to represent a two-dimensional array, and each bucket is a one-dimensional array
		// Description the two-dimensional array contains 10 one-dimensional arrays
		//     In order to prevent data overflow when putting in numbers, the size of each one-dimensional array is array length()
		//     Obviously, space changes time
		int[][] bucket = new int[10][arr.length];
		// In order to record how many data are actually stored in each bucket, we define a one-dimensional array to record the number of each bucket
		// Bucket elementcounts [0] is the number of data put into bucket[0]
		int[] bucketElementCounts = new int[10];
		for (int j = 0; j < arr.length; j++){
			// Fetches the bits of each element
			int digitOfElement = arr[j] % 10;
			// Put it into the corresponding bucket
			bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
			bucketElementCounts[digitOfElement]++;
		}
		// Put the data in the bucket
		int index = 0;
		// Traverse each bucket and put the data in the bucket into the original array
		for (int k = 0;k < bucket.length; k++){
			if (bucketElementCounts[k] != 0){
				for (int j = 0; j < bucketElementCounts[k]; j++){
					arr[index++] = bucket[k][j];
				}
			}
			// In the first round, you need to set the bucket elementcounts array to zero
			bucketElementCounts[k]= 0;
		}
		System.out.println("The array after the first round of single digit processing:" + Arrays.toString(arr));

		// Simulate the second round (sort the ten digits of each element)

		for (int j = 0; j < arr.length; j++){
			// Fetch the ten digits of each element
			int digitOfElement = arr[j] / 10 % 10;
			// Put it into the corresponding bucket
			bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
			bucketElementCounts[digitOfElement]++;
		}
		// Put the data in the bucket
		 index = 0;
		// Traverse each bucket and put the data in the bucket into the original array
		for (int k = 0;k < bucket.length; k++){
			if (bucketElementCounts[k] != 0){
				for (int j = 0; j < bucketElementCounts[k]; j++){
					arr[index++] = bucket[k][j];
				}
			}
			bucketElementCounts[k]= 0;
		}
		System.out.println("The second round is the array after processing ten digits:" + Arrays.toString(arr));

		// Simulate three rounds (sort the hundreds of each element)

		for (int j = 0; j < arr.length; j++){
			// Fetch the hundredth of each element
			int digitOfElement = arr[j] /100 % 10;
			// Put it into the corresponding bucket
			bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
			bucketElementCounts[digitOfElement]++;
		}
		// Put the data in the bucket
		index = 0;
		// Traverse each bucket and put the data in the bucket into the original array
		for (int k = 0;k < bucket.length; k++){
			if (bucketElementCounts[k] != 0){
				for (int j = 0; j < bucketElementCounts[k]; j++){
					arr[index++] = bucket[k][j];
				}
			}
			bucketElementCounts[k]= 0;
		}
		System.out.println("The array after the third round of processing hundreds:" + Arrays.toString(arr));

	}

	// Total cardinality sort
	public static void radixSortAll(int[] arr){
		int[][] bucket = new int[10][arr.length];
		int[] bucketElementCounts = new int[10];
		int index;
		// Need to get the maximum number
		int max = arr[0];
		for (int i = 1; i < arr.length; i++){
			if (max < arr[i]){
				max = arr[i];
			}
		}
		int maxLength = (max+"").length();
 		for (int i = 0, n = 1; i < maxLength; i++, n *=10) {
			for (int j = 0; j < arr.length; j++){
				int digitOfElement = arr[j] / n % 10;
				// Put the corresponding bucket into
				bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
				bucketElementCounts[digitOfElement]++;
			}
			// Put the data in the bucket
			index = 0;
			// Traverse each bucket and put the data in the bucket into the original array
			for (int k = 0;k < bucket.length; k++){
				if (bucketElementCounts[k] != 0){
					for (int j = 0; j < bucketElementCounts[k]; j++){
						arr[index++] = bucket[k][j];
					}
				}
				bucketElementCounts[k]= 0;
			}

		}
		System.out.println("Results of cardinality sorting" + Arrays.toString(arr));
	}


}

Time complexity O(nlogn) Mr. Han's computer spent less than 0-1 second 80w 1 second less than 800w1 second 8000w 80000000 *11 *4 /1024/1024/1024 = 3.3G memory to sort 80000 random numbers

If there are negative numbers, cardinality sorting is not used

Comparison of eight sorting algorithms

Heap sorting can only be understood after learning binary tree

Search algorithm

Binary search algorithm

d

Tags: Java Algorithm data structure

Posted by billy_111 on Mon, 02 May 2022 15:25:11 +0300