【华为OD-E卷-最小调整顺序次数、特异性双端队列 100分（python、java、c++、js、c）】
题目
有一个特异性的双端队列，该队列可以从头部或尾部添加数据，但是只能从头部移出数据。
小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 要调整的最小次数。
用例
用例一：
输入：
5
head add 1
tail add 2
remove
head add 3
tail add 4
head add 5
remove
remove
remove
remove
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
输出：
1
- 1
python解法
- 解题思路：
- 任务目标：
处理一系列命令（add head, add tail, remove）对一个队列进行操作。
每次执行remove命令时，确保队列头部元素为指定的值current_remove，否则需要调整队列以满足条件。
统计所有remove命令中，为调整队列顺序而进行的排序操作次数。
实现逻辑：
使用一个列表模拟队列。
遍历命令：
对于add head和add tail命令，将元素插入队列的头部或尾部。
对于remove命令：
如果队列头部的元素与current_remove匹配，则直接移除。
否则，对队列进行排序，移除排序后的第一个元素，并记录一次调整操作。
最终返回调整次数。
def process_commands(cmds, n):
# 队列初始化
queue = []
current_remove = 1 # 当前需要移除的目标值
adjustments = 0 # 调整次数统计
for cmd in cmds:
# 处理当前命令
handle_command(cmd, queue, current_remove)
if cmd.startswith("remove"):
# 对队列进行调整
adjustments += adjust_queue(queue, current_remove)
current_remove += 1 # 更新需要移除的目标值
return adjustments
def handle_command(cmd, queue, current_remove):
# 根据命令类型操作队列
if "add" in cmd:
_, _, x = cmd.split() # 提取要添加的值
if "head" in cmd:
queue.insert(0, int(x)) # 添加到队列头部
else:
queue.append(int(x)) # 添加到队列尾部
def adjust_queue(queue, current_remove):
# 检查队列头部是否为目标值
if queue[0] == current_remove:
queue.pop(0) # 如果匹配，直接移除头部
return 0 # 无需调整，返回 0
else:
queue.sort() # 否则排序队列
queue.pop(0) # 移除排序后的第一个元素
return 1 # 记录一次调整操作
# 输入获取
n = int(input()) # 命令对数
cmds = [input() for i in range(2 * n)] # 获取所有命令
# 输出结果
print(process_commands(cmds, n))
- 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
java解法
- 解题思路
- 任务目标：
处理一系列命令（head add、tail add、remove）对队列进行操作。
每次执行remove命令时，如果队列未排序（head add会导致队列无序），需要对队列进行排序，并统计排序次数。
最终输出所有remove命令中，因排序操作产生的调整次数。
核心逻辑：
使用一个变量queueSize记录队列的大小。
使用布尔变量sorted标记队列是否处于有序状态：
head add操作可能破坏有序状态，将sorted设为false。
如果在执行remove时队列无序，则需要排序（adjustments计数加1），并恢复有序状态。
遍历命令列表，依次处理队列的增删操作，并更新状态和调整计数。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int len = Integer.parseInt(in.nextLine()); // 读取命令对数
int total = len * 2; // 总命令数为命令对数的两倍
String[] cmds = new String[total];
int j = 0;
while (j < total) {
cmds[j] = in.nextLine(); // 读取所有命令
j++;
}
System.out.println(calculateAdjustments(cmds)); // 计算并输出调整次数
}
public static int calculateAdjustments(String[] cmds) {
int queueSize = 0; // 当前队列的大小
boolean sorted = true; // 标记队列是否处于有序状态
int adjustments = 0; // 记录排序操作的次数
int i = 0;
while (i < cmds.length) {
String cmd = cmds[i];
if (cmd.startsWith("head add")) {
// `head add` 操作可能破坏队列的有序状态
if (queueSize > 0 && sorted) sorted = false;
queueSize++; // 队列大小加1
} else if (cmd.startsWith("tail add")) {
// `tail add` 操作不会破坏队列的有序状态
queueSize++; // 队列大小加1
} else { // 处理 `remove` 操作
if (queueSize == 0) { // 如果队列为空，跳过当前命令
i++;
continue;
}
if (!sorted) { // 如果队列无序，需要排序
adjustments++; // 增加调整次数
sorted = true; // 恢复有序状态
}
queueSize--; // 移除队列的一个元素
}
i++;
}
return adjustments; // 返回总调整次数
}
}
- 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
C++解法
- 解题思路
更新中
- 1
C解法
更新中
- 1
JS解法
处理一系列命令（head add、tail add、remove）操作一个堆栈。
如果命令是head add，可能导致堆栈的顺序被破坏，需要在执行remove命令时进行排序以恢复顺序。
统计排序操作的次数（即需要恢复顺序的操作次数）。
实现逻辑：
使用stackSize记录当前堆栈的大小。
使用needSort标记堆栈是否需要排序：
head add会导致无序，将needSort设为true。
tail add不会影响顺序。
在remove时，如果needSort为true，需要排序（增加排序计数并重置needSort）。
遍历命令数组，根据命令类型更新堆栈状态和排序计数。
输入输出：
输入：第一行为命令对数n，接下来是2 * n条命令。
输出：所有remove命令中因排序产生的调整次数。
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let commands = [];
let numOps = 0;
rl.on("line", (line) => {
commands.push(line); // 读取输入
if (commands.length === 1) {
numOps = parseInt(commands[0]); // 第一行表示命令对数
} else if (commands.length === 1 + 2 * numOps) {
commands.shift(); // 移除第一行命令对数
console.log(processCommands(commands)); // 处理命令并输出结果
commands = [];
}
});
function processCommands(cmds) {
let stackSize = 0; // 当前堆栈的大小
let needSort = false; // 是否需要排序
let operations = 0; // 排序操作次数统计
cmds.forEach((cmd) => {
if (cmd.startsWith("head add")) {
// 如果是 `head add`，可能导致堆栈无序
if (stackSize > 0) needSort = true; // 如果堆栈非空，标记需要排序
stackSize++; // 增加堆栈大小
} else if (cmd.startsWith("tail add")) {
// 如果是 `tail add`，只增加堆栈大小，不影响顺序
stackSize++;
} else {
// 如果是 `remove` 操作
if (stackSize === 0) return; // 堆栈为空，跳过此命令
if (needSort) {
// 如果需要排序，增加排序操作计数
operations++;
needSort = false; // 排序完成后重置标记
}
stackSize--; // 减少堆栈大小
}
});
return operations; // 返回总排序操作次数
}
- 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
注意：
如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏
评论记录：
回复评论：