当前位置: 首页> 科技> 数码 > 小米新品发布会_东莞网站设计知名 乐云践新_福建seo网站_搜索引擎优化是什么?

小米新品发布会_东莞网站设计知名 乐云践新_福建seo网站_搜索引擎优化是什么?

时间:2025/7/11 8:27:08来源:https://blog.csdn.net/CodeClimb/article/details/144531773 浏览次数:0次
小米新品发布会_东莞网站设计知名 乐云践新_福建seo网站_搜索引擎优化是什么?

【华为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; // 返回总排序操作次数
}

注意:

如果发现代码有用例覆盖不到的情况,欢迎反馈!会在第一时间修正,更新。
解题不易,如对您有帮助,欢迎点赞/收藏

关键字:小米新品发布会_东莞网站设计知名 乐云践新_福建seo网站_搜索引擎优化是什么?

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: