7-1 symmetrical sorting (25 points)
The title comes from PTA
You work for the albatross circus with a group of ugly stars as pillars. You have just completed a program that outputs their list in non descending order according to the length of the stars' name string (that is, the length of the current name is at least the same as that of the previous name). However, your boss doesn't like this output format. He proposes that the length of the first and last names of the output is short, while the length of the middle part is slightly longer, which appears symmetrical. The specific method mentioned by the boss is to deal with the list that has been sorted by length one by one, putting the former at the head of the current sequence and the latter at the tail. For the first case in the input example, Bo and Pat are the first pair of names, Jean and Kevin are the second pair, and so on.
Input format:
The input contains several test cases. The first line of each case contains an integer n (n > = 1), indicating the number of name strings. The next N lines each line a name string, which is arranged by length. The name string does not contain spaces, and each string contains at least one character. n=0 is the end of input flag.
Output format:
For each test case, first output a line of "Set n", where n starts from 1, indicating the case serial number. Next is the n-line name output, as shown in the output example.
Input example:
7 Bo Pat Jean Kevin Claude William Marybeth 6 Jim Ben Zoe Joey Frederick Annabelle 5 John Bill Fran Stan Cece 0
Output example:
SET 1 Bo Jean Claude Marybeth William Kevin Pat SET 2 Jim Zoe Frederick Annabelle Joey Ben SET 3 John Fran Cece Stan Bill
key problem:
How to put the front one and then the back one???
Is there anything (class) that can directly implement this, one in front and one in back
solve the problem:
I have to say that Java is a cow. You can't think of it, you can't do it, you don't have to know, and you can't forget it.
When we first know Java data structures, we don't know what useful classes and methods are. With a try attitude, we start to look at the relevant classes that implement the interface Queue and find the relevant methods. When I see the class linkedblockingdeque < E >, I don't know what it is. I know that there are two methods to help me solve the above problems.
| describe | |
|---|---|
| void | putFirst(E e) inserts the specified element at the beginning of this two ended queue, waiting for free space if necessary. |
| void | Putlist (E) inserts the specified element at the end of this two ended queue, waiting for free space if necessary. |
code
import java.util.Scanner;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingDeque;
public class Main {
public static void main(String[] args) throws InterruptedException {
Scanner input = new Scanner(System.in);
LinkedBlockingDeque<Object> s = new LinkedBlockingDeque<>();
Stack<Object> swop = new Stack<Object>();//Store all names
int count = 1;//Counter
int sum;
while ((sum = input.nextInt()) != 0) {
for (int i = 0; i < sum; i++) {
String name = input.next();
swop.push(name);
}
//Names are stored alternately at the head and tail of the team
if (sum % 2 == 0) {
for (int j = 0; j < sum; j++) {
if (j % 2 == 0) {
s.putLast(swop.pop());
} else {
s.putFirst(swop.pop());
}
}
} else {
for (int j = 0; j < sum; j++) {
if (j % 2 == 0) {
s.putFirst(swop.pop());
} else {
s.putLast(swop.pop());
}
}
}
System.out.println("SET " + count);
for (int j = 0; j < sum; j++) {
System.out.println(s.pop());
}
count++;
}
input.close();
}
}
Problems and doubts encountered
- Why is it just the opposite of the correct answer when the number of names is even (odd) without judging whether sum is odd or even?
- Is there another class to replace linkedblockingdeque < E >?
Optimize and solve doubts
At first, it was discovered by mistake that the real idea was:
Create a stack, a queue. All names are stored in the stack in order. When they are out of the stack, they just become names in all order. The long ones are at the top and the short ones are at the bottom. Then, when they are out of the stack, they are placed one by one at the head of the team and the other at the end of the team.
After understanding the above ideas, the problems and doubts encountered will be solved.
- Without judgment, when the number of names is odd, it is asymmetric, so when it is odd, you can put the top element of the stack into the queue in advance.
- After a few days of study, I have learned some superficial things. LinkedList is generally used as a queue in Java, so I can solve the problem in the same way.
| describe | |
|---|---|
| void | Addfirst (E) inserts the specified element at the beginning of this list. |
| void | Addlast (E) adds the specified element to the end of this list. |
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Stack;
public class Main2 {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
LinkedList<Object> s = new LinkedList<>();
Stack<Object> swap = new Stack<Object>();//Store all names
int count = 1;//Counter
int sum;//Number of names
while ((sum = input.nextInt()) != 0) {
for (int i = 0; i < sum; i++) {
String name = input.next();
swap.push(name);
}
if (sum % 2 != 0) {//It is an odd number to put the top element of the stack into the queue first
s.add(swap.pop());
sum = sum - 1;
}
//Store alternately at the head and tail of the team
for (int j = 0; j < sum; j++) {
if (j % 2 == 0) {
s.addLast(swap.pop());
} else {
s.addFirst(swap.pop());
}
}
System.out.println("SET " + count);
while (!s.isEmpty()) {//Print all the elements in the queue and stack them one by one.
System.out.println(s.pop());
}
count++;
}
input.close();
}
}
There are countless cross paths on the road of life. No matter which path you take, I wish you a bright future when you recover from poverty———— Devour the earth