华为OD机试真题【特异性双端队列 | 最小调整顺序次数】

1、题目描述

【特异性双端队列 | 最小调整顺序次数】

给定一个队列，但是这个队列比较特殊，可以从头部添加数据，也可以从尾部添加数据，但是只能从头部删除数据。
输入一个数字n，会依次添加数字1~n（也就是添加n次）。
但是在添加数据的过程中，也会删除数据，要求删除必须按照1~n按照顺序进行删除，所以在删除时，可以根据需要调整队列中数字的顺序以满足删除条件。

【输入描述】
第一行一个数据N，表示数据的范围。
接下来的2N行是添加和删除语句。
其中：
head add x 表示从头部添加元素 x，
tail add 表示从尾部添加元素，
remove表示删除元素。

【输出描述】
输出一个数字，表示最小的调整顺序次数。

【示例一】
输入：
5
head add 1
tail add 2
remove
head add 3
tail add 4
head add 5
remove
remove
remove
remove
输出:
1

说明:
第1步: [1]
第2步: [1,2]
第3步:头部删除1,无需调整，还剩[2]
第4步: [3,2]
第5步: [3,2,4]
第6步: [5,3,2,4]
第7步:头部删除2，调整顺序再删除，还剩3，4, 5]
第8步:头部删除3，无需调整，还剩[4，5]
第9步:头部删除4，无需调整，还剩[5]
第10步:头部删除5,无需调整
只需要调整1次

2、解题思路

有题可想到双端队列的特性，初始化一个空双端队列Q和一个从1开始的计数变量start, 盱记录下一个要删除的元素。
遍历输入的操作列表，根据操作类型执行不同操作:
1.如果操作是“remove"，则检查队列的第一个元素是否等于start:
2.如果相等，则从队列头部删除阮素并将start 加1。
3.如果不相等，则调整队列顺序，从队列头部删除元素,将调整次数加1,将start 加1。
4.如果操作是“head add"或“tail add",则根据操作将元素添加到队列的头部或尾部。

3、参考代码

import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class 特异性双端队列最小调整顺序次数 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = Integer.parseInt(in.nextLine());
            List<String> strings = new ArrayList<>();

            for (int i = 0; i < 2 * n; i++) {
                strings.add(in.nextLine());
            }

            Deque<Integer> deque = new LinkedList<>();
            int reVal = 1;
            int res = 0;
            for (String string : strings) {
                if ("remove".equals(string)) {
                    if (deque.isEmpty()) {
                        continue;
                    }
                    if (deque.peekFirst() == reVal) {
                        deque.removeFirst();
                        reVal++;
                    } else {
                        List<Integer> list = new ArrayList<>(deque);
                        Collections.sort(list);
                        deque.clear();
                        deque.addAll(list);
                        deque.removeFirst();
                        reVal++;
                        res++;
                    }
                } else {
                    String[] arr = string.split(" ");
                    if ("head".equals(arr[0])) {
                        deque.addFirst(Integer.valueOf(arr[2]));
                    } else if ("tail".equals(arr[0])) {
                        deque.addLast(Integer.valueOf(arr[0]));
                    }
                }
            }
        }
    }
}

4、相似题目