Aha! Algorithm Chapter 2 - Section 1 - decrypt QQ number

Decrypt QQ number - queue

The new semester begins. Xiaoha is xiaohum's new deskmate (xiaoha is a little beauty). Xiaohum asks xiaoha about the QQ number. Of course, xiaoha won't tell xiaohum directly. You know the reason. So xiaoha gave xiaohum a string of encrypted numbers, and xiaoha also told xiaohum the decryption rules. The rule is as follows: first delete the first number, then put the second number at the end of the string, then delete the third number, put the fourth number at the end of the string, and then delete the fifth number... Until the last number is left, and then delete the last number. According to the order of deletion just now, connecting these deleted numbers together is xiaoha's QQ. Now you can help Xiao hum. Xiaoha encrypted a string of numbers for xiaohum as "6 3 1 7 5 8 9 2 4"


It can be found that the process of decrypting QQ number is like "queuing" the number. We take two numbers from the front of the number every time, throw the first one away, and put the second one at the end of the number. The specific process is as follows:

At first, the string was "6 3 1 7 5 8 9 2 4"
The first time: delete 6 and put 3 at the end of the number, and update the number to "1 7 5 8 9 2 4 3";
The second time: delete 1 and put 7 at the end of the number, that is, update it to "5 8 9 2 4 3 7";
The third time: delete 5 and put 8 at the end of the number, that is, update it to "9 2 4 3 7 8";
The fourth time: delete 9 and put 2 at the end of the number, that is, update it to "4 3 7 8 2";
The fifth time: delete 4 and put 3 at the end of the number, that is, update it to "7 8 2 3";
Sixth time: delete 7 and put 8 at the end of the number, that is, update it to "2 3 8";
The seventh time: delete 2 and put 3 at the end of the number, that is, update it to "8 3";
8th time: delete 8 and put 3 at the end of the number, i.e. update to "3";
9th time: delete 3.
Therefore, the order of the deleted numbers is "6 1 5 9 4 7 2 8 3", which is xiaoha's QQ number

The rules and process of decryption are clear. Now let's implement it with code!

The topic gives us a string of numbers, so we need to use an array to store these numbers, define an array with a length of 100, and initialize the array, that is:

	System.out.println("Please enter the to be decrypted QQ Number of numbers of No.:");
	int n = sc1.nextInt();
	Scanner sc1 = new Scanner(System.in);
	System.out.println("Please enter the to be decrypted QQ number:");
	Scanner sc1 = new Scanner(System.in);
	int a[] = new int[100];
	for(int i = 0;i < n; i++){ // Initialize array
		a[i] = sc2.nextInt();
	}

After that, you can start analog decryption. The first step of decryption is to delete the number. The simplest way to delete the number in the array is to move all the subsequent numbers to the front and overwrite the previous numbers. For example, when we are queuing to buy tickets, the people in front buy and leave, and all the people in the back need to take a step forward to make up for the vacant seats, but this method is very time-consuming.

However, this gives us a good idea - queuing. We can regard this string of numbers as a queue, and then define two integer variables head and tail to point to the next position of the queue's head (i.e. the first) and tail (i.e. the last).

You may ask: why does tail not record the tail directly, but record the next position of the tail?
This is because when there is only one element left in the queue, the coincidence of the head and tail of the queue will cause some trouble. We stipulate here that when the head and tail of the team coincide, the queue is empty.

Here I would like to briefly add the concept of queue:

Queue is a special linear structure, which only allows deletion at the head of the queue, which is called "out of queue"; Inserting at the tail of the queue is called "joining the queue".
When there is no element in the queue (i.e. head==tail), it is called an empty queue.
In our daily life, there are many situations that conform to the characteristics of queues. For example, as we mentioned before, each window in line to buy tickets is a queue. In this queue, newcomers always stand at the back of the queue. The earlier people come, the earlier they will be able to buy tickets, that is, those who come first will serve first.
We call it the First In First Out (FIFO) principle.



Replenishment completed! Move on!

Xiaoha gave xiaohum 9 encrypted QQ numbers. After we put all the 9 numbers in the queue,

head = 0;
tail = 9; (9 numbers are put into the array, and the subscript of the array is 0 ~ 8, so tail = 8+1 = 9)

At this time, the number between head and tail is the "effective" number in the current queue. If you want to delete a number, you can set head + + to OK. In this way, you can still keep the number between head and tail as the "valid" number in the current queue. Although this wastes a space, it saves a lot of time, which is very cost-effective. Adding a new number is also very simple. Put the number to be added at the end of the team, that is, q[tail], and then tail + + is OK!
(Note: space for time is also an idea of the algorithm)

Summary:

Delete a number by the head of the queue: head++
Add a number at the end of the team (assuming that this number is x)Operation: q[tail] = x;
								   tail++; 


The whole decryption process is shown as follows:

The complete code is as follows:

import java.util.Scanner;
public class T1 {
	public static void main(String[] args) {
		// QQ number decryption
		// Enter the number of QQ numbers to be decrypted and the QQ number to be decrypted
		System.out.print("Please enter the to decrypt QQ Number of numbers of No.:");
		Scanner sc1 = new Scanner(System.in);
		int n = sc1.nextInt();
		System.out.println("Please enter the to decrypt QQ number:");
		// Because the way we choose to delete data is to go back directly to head + +,
		// At the same time, tail + + continues to create new space backward, so we need more array space than the number of QQ numbers
		// So when we create the array q, we give more space
		// Although this wastes space, it saves a lot of time. It is also an idea of the algorithm "exchanging space for time"
		int q[] = new int[101]; 
		Scanner sc2 = new Scanner(System.in);
		for(int i = 0; i < n; i++) { // Cycle to read QQ number
			q[i] = sc2.nextInt();
		}
		
		// Define two integer variables to mark the array subscript as the head pointer and tail pointer
		
		int head = 0; // Header pointer, array subscript = 0
		
		// The position of the tail of QQ is equal to the position of the next tail of QQ,
		// Because the subscript of the array starts from 0, the subscript of the 9th number is 8,
		// Therefore, the subscript of the next position at the end of the team is 9, that is, the number of numbers of QQ number
		int tail = n; 
		
		// If you don't know how many times to cycle or the number of cycles can't be calculated immediately, use the while loop
		// When the last number is deleted, the head pointer and tail pointer point to the same number to end the loop
		while(head < tail) { 
			System.out.print(q[head]+" "); // Print team leader element
			head++; // Take the first element out of the queue, that is, the head pointer points to the next element,
			
			// According to the title, the next element of the first element of the team needs to be placed at the end of the team,
			// After the first element of the team leaves the team, the element pointed to by the head needs to be placed at the end of the team,
			// Therefore, the element value is assigned to the space pointed to by the tail pointer
			q[tail] = q[head];
			
			// After the assignment, the tail pointer moves backward
			tail++;
			// The head pointer also moves backward
			head++;
			// At this point, the first decryption process is completed
			// Delete the first number and put the second number at the end of the number
			// At this time, the head points to the third number, which will be deleted at the beginning of the next cycle
			// Then start the next round of decryption process until the end of the cycle, and complete all decryption processes
		}
	}
}

The operation results are as follows:

Tags: Java Algorithm data structure queue

Posted by srikanthiv on Mon, 23 May 2022 14:04:57 +0300