【华为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
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 adjustmentsdef 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 # 无需调整,返回 0else:queue.sort() # 否则排序队列queue.pop(0) # 移除排序后的第一个元素return 1 # 记录一次调整操作# 输入获取
n = int(input()) # 命令对数
cmds = [input() for i in range(2 * n)] # 获取所有命令# 输出结果
print(process_commands(cmds, n))
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; // 返回总调整次数}
}
C++解法
- 解题思路
更新中
C解法
更新中
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; // 返回总排序操作次数
}
注意:
如果发现代码有用例覆盖不到的情况,欢迎反馈!会在第一时间修正,更新。
解题不易,如对您有帮助,欢迎点赞/收藏