文章

10

粉丝

66

获赞

3

访问

42.2k

头像
two pointers解法
P990 浙江大学2021年机试题
发布于2022年5月22日 12:36
阅读数 3.4k

解析:

题目大意:一个队列,只能从一端插入数据,但可以从两端删除数据。现在给定一段数据互不相同的插入序列,然后给一些删除序列,判断这些删除顺序的可行性。

用两个指针pipj分别指向插入序列insertion与删除序列deletion。pi初始指向0,表示第一个数据待插入。每读到一个待删除数据时,有以下情况:

1、当前待删除数据等于待插入数据,把数据进队列然后马上出队列就可以了(相当于什么也不做),然后pi右移,表示下一个数据待插入;

2、当前待删除数据不等于待插入数据,且待删除数据还没有插入,那就一口气把待删除数据之前未插入的数据都插入;

3、当前待删除数据不等于待插入数据,且待删除数据已经插入了,那就检查队列两端是不是待删除数据,不是就意味着这个数无法删除,该删除序列无法实现。

数据结构上,可以用deque,它的用法类似于vector,但是支持时间复杂度为O(1)的两端插入删除操作。

#include <deque>
#include <unordered_set>
#include <iostream>
using namespace std;

void test () {
    int N, K;
    int i, j;
    scanf("%d %d", &N, &K);
    deque<int> insertion(N);
    for (i = 0; i < N; i++) scanf("%d", &insertion[i]);
    for (int k = 0; k < K; k++) {
        unordered_set<int> inserted;
        deque<int> deletion(N), q;
        for (j = 0; j < N; j++) scanf("%d", &deletion[j]);
        for (j = 0, i = 0; j < N; j++) {
            if (deletion[j] == insertion[i]) {
...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发