问题描述

你有一个盒子，你可以往里面放数，也可以从里面取出数。

初始时，盒子是空的，你会依次做 Q 个操作，操作分为两类：

1. 插入操作：询问盒子中是否存在数 x，如果不存在则把数 x 丢到盒子里。
2. 删除操作：询问盒子中是否存在数 x，如果存在则取出 x。

对于每个操作，你需要输出是否成功插入或删除。

输入

第一行一个正整数 Q，表示操作个数。

接下来 Q 行依次描述每个操作。每行 2 个用空格隔开的非负整数 op,x 描述一个操作：op 表示操作类型，op=1 则表示这是一个插入操作，op=2 则表示这是一个删除操作；x 的意义与操作类型有关，具体见题目描述。

输出

按顺序对所有操作输出，对于每个操作输出一行，如果成功则输出“Succeeded”（不含引号），如果失败则输出“Failed”（不含引号）。

样例输入

6
1 100  插入
1 100  插入
2 100  删除
1 200  插入
2 100  删除
2 200  删除

样例输出

Succeeded
Failed
Succeeded
Succeeded
Failed
Succeeded

提示

[对于 x 较小的情况，我们只需要用数组记录每个数是否在盒子里即可。]

[对于 x 较大的情况，我们可不可以用什么方法把它们“变小”呢？可以想想哈希表哦！]

一. 图解

二. 具体实现（C++版）

typedef long long ll;
const int Mod = 1000003;
vector<ll> table[Mod];
//哈希函数
int Hash(ll x){
    return x%Mod;
}
// 执行操作时会调用这个函数
// op：对应该次操作的 op（具体请见题目描述）
// x：对应该次操作的 x（具体请见题目描述）
// 返回值：如果输出为"Succeeded"，则这个函数返回 1，否则返回 0
bool check(int op, ll x) {
    int h = Hash(x);//求出x的哈希值
    //在链表中找到x（采用C++中的vector或者Java中的List去实现链表的功能）
    vector<ll>::iterator ptr = table[h].end();//返回向量尾指针
    for(vector<ll>::iterator it = table[h].begin();it!=table[h].end();++it)
      //如果x存在
        if((*it)==x){ptr = it;break;}

    if(op==1){//x不存在则插入
        if(ptr == table[h].end()){
            table[h].push_back(x);//向量尾部增加一个元素X
            return 1;
        }
        return 0;
    }else{//op为2，则执行删除操作
        if(ptr != table[h].end()){//用最后一个元素去填补要删除的元素
            *ptr = table[h].back();//back()得到数组的最后一个单元的引用,即最后一个单元元素的数值
            table[h].pop_back();//去掉数组的最后一个元素
            return 1;
        }
        return 0;
    }
}

补充C++的vector知识

int main()
{
    vector<int> a;
    for(int i=0;i<10;i++)
    {
        a.push_back(i);//向尾部增加元素
    }
    printf("%d",a.at(3));//返回位置1元素的引用，输出3
    printf("%d",a.begin());//返回向量头指针，指向第一个元素
    printf("%d",a.end());//返回向量尾指针，指向向量最后一个元素的下一个位置
    printf("%d",a.back());//返回尾元素的引用，输出9
    a.pop_back();//去掉数组的最后一个元素
    return 0;
}