机考E卷100分题 - 最小的调整次数特异性双端队列
题目描述
有一个特异性的双端队列，该队列可以从头部或尾部添加数据，但是只能从头部移出数据。
小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 要调整的最小次数。
示例1
输入
5
head add 1
tail add 2
remove
head add 3
tail add 4
head add 5
remove
remove
remove
remove
1234567891011
输出
1
1
说明
解题思路
Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int number = scanner.nextInt();//数据的范围
scanner.nextLine();
Queue<Integer> queue = new LinkedList<>();//模拟双端队列
boolean in_order = true;//是否按顺序删除
int result = 0;//最小的调整顺序次数
for (int i = 0; i < 2 * number; i++) {
String input_str = scanner.nextLine();
String[] operation = input_str.split(" ");
if (operation[0].equals("head")) {//从头部添加元素
if (!queue.isEmpty() && in_order) {//不按顺序删除
in_order = false;
}
queue.add(Integer.parseInt(operation[2]));
} else if (operation[0].equals("tail")) {//从尾部添加元素
queue.add(Integer.parseInt(operation[2]));
} else {//删除元素
if (queue.isEmpty()) {
continue;
}
if (!in_order) {//不按顺序删除
result++;
in_order = true;
}
queue.poll();
}
}
System.out.println(result);//输出最小的调整顺序次数
}
}
1234567891011121314151617181920212223242526272829303132333435363738
Python
from collections import deque
number = int(input()) # 数据的范围
queue = deque() # 模拟双端队列
in_order = True # 是否按顺序删除
result = 0 # 最小的调整顺序次数
for i in range(2 * number):
input_str = input()
operation = input_str.split(" ")
if operation[0] == "head": # 从头部添加元素
if len(queue) != 0 and in_order: # 不按顺序删除
in_order = False
queue.appendleft(int(operation[2]))
elif operation[0] == "tail": # 从尾部添加元素
queue.append(int(operation[2]))
else: # 删除元素
if len(queue) == 0:
continue
if not in_order: # 不按顺序删除
result += 1
in_order = True
queue.pop()
print(result) # 输出最小的调整顺序次数
123456789101112131415161718192021222324252627
JavaScript
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
let number = 0;
let operations = [];
rl.on('line', (input) => {
if (number === 0) {
number = parseInt(input);
} else {
operations.push(input.split(" "));
if (operations.length === 2 * number) {
rl.close();
}
}
});
const queue = []; // 模拟双端队列
let in_order = true; // 是否按顺序删除
let result = 0; // 最小的调整顺序次数
rl.on('close', () => {
for (let i = 0; i < 2 * number; i++) {
const operation = operations[i];
if (operation[0] === "head") { // 从头部添加元素
if (queue.length !== 0 && in_order) { // 不按顺序删除
in_order = false;
}
queue.unshift(parseInt(operation[2]));
} else if (operation[0] === "tail") { // 从尾部添加元素
queue.push(parseInt(operation[2]));
} else { // 删除元素
if (queue.length === 0) {
continue;
}
if (!in_order) { // 不按顺序删除
result += 1;
in_order = true;
}
queue.pop();
}
}
console.log(result); // 输出最小的调整顺序次数
});
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849
C++
#include <iostream>
#include <queue>
using namespace std;
int main() {
int number;
cin >> number;
cin.ignore();
queue<int> queue;
bool in_order = true;
int result = 0;
for (int i = 0; i < 2 * number; i++) {
string input_str;
getline(cin, input_str);
string operation[3];
int j = 0;
for (char c : input_str) {
if (c == ' ') {
j++;
} else {
operation[j] += c;
}
}
if (operation[0] == "head") {
if (!queue.empty() && in_order) {
in_order = false;
}
queue.push(stoi(operation[2]));
} else if (operation[0] == "tail") {
queue.push(stoi(operation[2]));
} else {
if (queue.empty()) {
continue;
}
if (!in_order) {
result++;
in_order = true;
}
queue.pop();
}
}
cout << result << endl;
return 0;
}
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849
C语言
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 600000 // 定义队列的最大容量（2n）
int queue[MAX_SIZE]; // 模拟双端队列的数组
int front = 0; // 队列头部索引
int rear = -1; // 队列尾部索引
int size = 0; // 当前队列中的元素数量
int main() {
int n;
scanf("%d", &n); // 读取数据范围n
int result = 0; // 记录最小的调整顺序次数
int expected = 1; // 期望移除的下一个元素
int in_order = 1; // 标记是否按顺序删除
for (int i = 0; i < 2 * n; i++) {
char operation[10];
int x;
scanf("%s", operation); // 读取操作类型
if (operation[0] == 'r') { // 如果是 "remove" 操作
if (queue[front] != expected) { // 如果移除的元素不是期望的
in_order = 0; // 标记为不按顺序
} else {
expected++; // 移除的元素符合预期，更新下一个期望值
}
front = (front + 1) % MAX_SIZE; // 更新头部索引
size--; // 减少队列中的元素数量
} else { // 如果是 "head add" 或 "tail add" 操作
scanf("%*s %d", &x); // 读取要添加的元素x
if (operation[0] == 'h') { // 如果是 "head add"
front = (front - 1 + MAX_SIZE) % MAX_SIZE; // 更新头部索引
queue[front] = x; // 从头部添加元素
} else { // 如果是 "tail add"
rear = (rear + 1) % MAX_SIZE; // 更新尾部索引
queue[rear] = x; // 从尾部添加元素
}
size++; // 增加队列中的元素数量
}
if (!in_order && size == 0) { // 如果当前不按顺序且队列为空
result++; // 增加调整次数
in_order = 1; // 重置为按顺序状态
}
}
printf("%d\n", result); // 输出最小的调整顺序次数
return 0;
}
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455
大厂原题(全网最全，持续更新) 文章被收录于专栏
主要记录自己的刷题日常，学而时习之。
投递华为等公司10个岗位