当前位置：首页 > news >正文

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

news 2025/6/25 8:07:11

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

题目描述

有一个特异性的双端队列，该队列可以从头部或尾部添加数据，但是只能从头部移出数据。
小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>() {@Overridepublic 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);}
}