华为OD机试之最小调整顺序次数、特异性双端队列（Java源码）

最小调整顺序次数、特异性双端队列

题目描述

有一个特异性的双端队列，该队列可以从头部或尾部添加数据，但是只能从头部移出数据。
小A依次执行2n个指令往队列中添加数据和移出数据。其中n个指令是添加数据（可能从头部添加、也可能从尾部添加），依次添加1到n；n个指令是移出数据。
现在要求移除数据的顺序为1到n。
为了满足最后输出的要求，小A可以在任何时候调整队列中数据的顺序。
请问 小A 最少需要调整几次才能够满足移除数据的顺序正好是1到n；

输入描述

第一行一个数据n，表示数据的范围。
接下来的2n行，其中有n行为添加数据，指令为：

• "head add x" 表示从头部添加数据 x，
• "tail add x" 表示从尾部添加数据x，

另外 n 行为移出数据指令，指令为："remove" 的形式，表示移出1个数据；

1 ≤ n ≤ 3 * 10^5。
所有的数据均合法。

输出描述

一个整数，表示 小A 要调整的最小次数。

源码和解析
解析：

其实这个题只要理解了就其实还蛮简单的。小编当时做这个提题目时候前面一脸懵B，压根不知道在说个啥。就只知道要调整次数，但是不确定这个调整次数是啥。
head add 1
[1]
tail add 2
[1, 2]
remove
[2]
head add 3
[3, 2]
tail add 4
[3, 2, 4]
head add 5
[5, 3, 2, 4]
remove
排序了
[3, 4, 5]
remove
[4, 5]
remove
[5]
remove
[]
这个是用例中的例子 输出过程。 认真去体会每个指令执行后的结果
若输入变成
5
head add 2
tail add 1
remove
head add 3
tail add 4
head add 5
remove
remove
remove
remove
排序了1次
那么其输出过程为：
head add 2
[2]
tail add 1
[2, 1]
remove
排序了
[2]
head add 3
[3, 2]
tail add 4
[3, 2, 4]
head add 5
[5, 3, 2, 4]
remove
排序了
[3, 4, 5]
remove
[4, 5]
remove
[5]
remove
[]
排序了2次
====》可以推出 ，当集合中首位值不是集合中最小值是，需要进行调整。而一次调整包含了多次交换位置过程。可以简单的理解为1次排序过程。

示例代码：

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class T33 {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String input = scanner.nextLine();
		int num = Integer.parseInt(input); // 数据范围 并非是数的个数
		List<Integer> numList = new ArrayList<Integer>();
		int count = 0;// 调整次数
		int removeNum = 1;// 下一次需要移走哪一个
		for (int i = 0; i < num * 2; i++) {
			input = scanner.nextLine();
			String strArr[] = input.split(" ");
			System.out.println(input);
			if (strArr[0].equals("remove")) {
				// remove 从头部移出数据
				if (numList.get(0) == removeNum) {
					numList.remove(0);
					removeNum++;
				} else {
					count++;
					// 调整次序 从小到大排序一下
					numList.sort(new Comparator<Integer>() {
						@Override
						public int compare(Integer o1, Integer o2) {
							if (o1 > o2)
								return 1;
							if (o1 < o2)
								return -1;
							return 0;
						}
					});
					System.out.println("排序了");
					numList.remove(0);
					removeNum++;
				}
			}
			// 头部添加
			if (strArr[0].equals("head")) {
				numList.add(0, Integer.parseInt(strArr[2]));
				// continue;
			} else if (strArr[0].equals("tail")) {
				// 尾部添加
				numList.add(Integer.parseInt(strArr[2]));
			}
			System.out.println(numList);
		}
		System.out.println(count);
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54