算法基础_数据结构

算法基础_数据结构

主要说一下基础数据结构,进阶数据结构后面会说

基础数据结构

1)单链表

实现一个单链表,链表初始为空,支持三种操作:

(1) 向链表头插入一个数;
(2) 删除第k个插入的数后面的数;
(3) 在第k个插入的数后插入一个数

现在要对该链表进行M次操作,进行完所有操作后,从头到尾输出整个链表。

注意:题目中第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了n个数,则按照插入的时间顺序,这n个数依次为:第1个插入的数,第2个插入的数,…第n个插入的数。

输入格式

第一行包含整数M,表示操作次数。

接下来M行,每行包含一个操作命令,操作命令可能为以下几种:

(1) “H x”,表示向链表头插入一个数x。

(2) “D k”,表示删除第k个输入的数后面的数(当k为0时,表示删除头结点)。

(3) “I k x”,表示在第k个输入的数后面插入一个数x(此操作中k均大于0)。

输出格式

共一行,将整个链表从头到尾输出。

数据范围

\( 1≤M≤100000 \)
所有操作保证合法。

输入样例:

10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6

输出样例:

6 4 6 5

分析:数组模拟单链表,注意注释

#include <bits/stdc++.h>
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const double INF = 0x3f3f3f3f3f3f3f3f;
using namespace std;
const int maxn = 1e5 + 6;

// head表示头节点的下标
// e[i] 表示节点i的值
// ne[i] 表示i的下一个节点
int head, e[maxn], ne[maxn];

// 当前已经用到的节点
int idx;

void init(){
    head = -1;
    idx = 0;
}

// 将值为x的节点插到头节点
void add_head(int x){
    ne[idx] = head, head = idx, e[idx++] = x;
}

// 将值为x的系欸但插入下标为k的节点后面
void add(int x, int k){
    ne[idx] = ne[k], ne[k] = idx, e[idx++] = x;
}

// 将下表为k的节点的后面的点删掉
void remove(int k){
    ne[k] = ne[ne[k]];
}

// 输出链表
void print_list(){
    for(int i = head;i != -1;i = ne[i]){
        cout << e[i] << " ";
    }
    cout << endl;
}

int main(){
    int m; sd(m);
    init();
    for(int i = 0;i < m;++i){
        string str = "";
        cin >> str;
        if(str == "H"){
            int x; sd(x);
            add_head(x);
        }else if(str == "D"){
            int k; sd(k);
            if(k == 0) head = ne[head];
            else remove(k - 1);
        }else if(str == "I"){
            int k, x;
            sd(k), sd(x);
            add(x, k - 1);
        }
    }
    print_list();
    
    return 0;
}

2)双链表

实现一个双链表,双链表初始为空,支持5种操作:

(1) 在最左侧插入一个数;
(2) 在最右侧插入一个数;
(3) 将第k个插入的数删除;
(4) 在第k个插入的数左侧插入一个数;
(5) 在第k个插入的数右侧插入一个数

现在要对该链表进行M次操作,进行完所有操作后,从左到右输出整个链表。

注意:题目中第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了n个数,则按照插入的时间顺序,这n个数依次为:第1个插入的数,第2个插入的数,…第n个插入的数。

输入格式

第一行包含整数M,表示操作次数。

接下来M行,每行包含一个操作命令,操作命令可能为以下几种:

(1) “L x”,表示在链表的最左端插入数x。
(2) “R x”,表示在链表的最右端插入数x。
(3) “D k”,表示将第k个插入的数删除。
(4) “IL k x”,表示在第k个插入的数左侧插入一个数。
(5) “IR k x”,表示在第k个插入的数右侧插入一个数。

输出格式

共一行,将整个链表从左到右输出。

数据范围

\( 1≤M≤100000 \)
所有操作保证合法。

输入样例:

10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2

输出样例:

8 7 7 3 2 9

分析:数组模拟双链表,对于在下表为k的左侧插入的问题,只需要在l[k]的右侧插入即可

#include <bits/stdc++.h>
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const double INF = 0x3f3f3f3f3f3f3f3f;
using namespace std;
const int maxn = 1e5 + 6;

int l[maxn], r[maxn], e[maxn];
int idx;

void init(){
    r[0] = 1, l[1] = 0;
    idx = 2;
}

// 在k的右边插入x
void add(int k, int x){
    r[idx] = r[k];
    l[r[k]] = idx;
    r[k] = idx;
    l[idx] = k;
    e[idx++] = x;
}

// 删除第k个节点
void remove(int k){
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

// 输出链表
void print_list(){
    for(int i = r[0];i != 1;i = r[i]){
        cout << e[i] << " ";
    }
    cout << endl;
}

int main(){
    int m; sd(m);
    init();
    while(--m >= 0){
        string str = "";
        cin >> str;
        if(str == "L"){
            int x; sd(x);
            add(0, x);
        }else if(str == "R"){
            int x; sd(x);
            add(l[1], x);
        }else if(str == "D"){
            int k; sd(k);
            remove(k + 1);
        }else if(str == "IL"){
            int k, x;
            sd(k), sd(x);
            add(l[k + 1], x);
        }else {
            int k, x;
            sd(k), sd(x);
            add(k + 1, x);
        }
    }
    print_list();

    return 0;
}

3)栈

实现一个栈,栈初始为空,支持四种操作:

(1) “push x” – 向栈顶插入一个数x;

(2) “pop” – 从栈顶弹出一个数;

(3) “empty” – 判断栈是否为空;

(4) “query” – 查询栈顶元素。

现在要对栈进行M个操作,其中的每个操作3和操作4都要输出相应的结果。

输入格式

第一行包含整数M,表示操作次数。

接下来M行,每行包含一个操作命令,操作命令为”push x”,”pop”,”empty”,”query”中的一种。

输出格式

对于每个”empty”和”query”操作都要输出一个查询结果,每个结果占一行。

其中,”empty”操作的查询结果为“YES”或“NO”,”query”操作的查询结果为一个整数,表示栈顶元素的值。

数据范围

1≤M≤100000
1≤x≤109
所有操作保证合法。

输入样例:

10
push 5
query
push 6
pop
query
pop
empty
push 4
query
empty

输出样例:

5
5
YES
4
NO

AC代码:

#include <bits/stdc++.h>
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const double INF = 0x3f3f3f3f3f3f3f3f;
using namespace std;
const int maxn = 1e3 + 6;

int stk[maxn], tt;

void init(){
    tt = 0;
}

// 插入元素
void Push(int x){
    stk[++tt] = x;
}

// 弹出元素
int Pop(){
    return stk[tt--];
}

// 判断是否为空
bool Empty(){
    if(tt > 0) return false;
    else return true;
}

// 栈顶元素
int Top(){
    return stk[tt];
}

int main(){
    int n; sd(n);
    init();
    while(--n >= 0){
        string op = "";
        cin >> op;
        if(op == "push"){
            int x; sd(x);
            Push(x);
        }else if(op == "query"){
            cout << Top() << endl;
        }else if(op == "pop"){
            Pop();
        }else if(op == "empty"){
            if(Empty()) cout << "YES" << endl;
            else cout << "NO" << endl;
        }
    }

    return 0;
}

4)队列

给定一个大小为n≤106n≤106的数组。

有一个大小为k的滑动窗口,它从数组的最左边移动到最右边。

您只能在窗口中看到k个数字。

每次滑动窗口向右移动一个位置。

以下是一个例子:

该数组为[1 3 -1 -3 5 3 6 7],k为3。

窗口位置最小值最大值
[1 3 -1] -3 5 3 6 7-13
1 [3 -1 -3] 5 3 6 7-33
1 3 [-1 -3 5] 3 6 7-35
1 3 -1 [-3 5 3] 6 7-35
1 3 -1 -3 [5 3 6] 736
1 3 -1 -3 5 [3 6 7]37

您的任务是确定滑动窗口位于每个位置时,窗口中的最大值和最小值。

输入格式

输入包含两行。

第一行包含两个整数n和k,分别代表数组长度和滑动窗口的长度。

第二行有n个整数,代表数组的具体数值。

同行数据之间用空格隔开。

输出格式

输出包含两个。

第一行输出,从左至右,每个位置滑动窗口中的最小值。

第二行输出,从左至右,每个位置滑动窗口中的最大值。

输入样例:

8 3
1 3 -1 -3 5 3 6 7

输出样例:

-1 -3 -3 -3 3 3
3 3 5 5 6 7

AC代码

#include <bits/stdc++.h>
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const double INF = 0x3f3f3f3f3f3f3f3f;
using namespace std;
const int maxn = 1e6 + 6;

// 假溢出队列
int qu[maxn], hh, tt = -1;

// 入队
void push(int x){
    qu[++tt] = x;
}

// 出队
int pop(){
    return qu[hh++];
}

// 判空
bool empty(){
    if(hh <= tt) return false;
    else return true;
}

// 取队首元素
int front(){
    return qu[hh];
}

int main(){
    int n; sd(n);
    while(--n >= 0){
        string op = ""; cin >> op;
        if(op == "push"){
            int x; sd(x);
            push(x);
        }else if(op == "empty"){
            if(empty()) puts("YES");
            else puts("NO");
        }else if(op == "pop"){
            pop();
        }else if(op == "query"){
            cout << front() << endl;
        }
    }
    
    return 0;
}

5)单调栈

给定一个长度为N的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出-1。

输入格式

第一行包含整数N,表示数列长度。

第二行包含N个整数,表示整数数列。

输出格式

共一行,包含N个整数,其中第i个数表示第i个数的左边第一个比它小的数,如果不存在则输出-1。

数据范围

1≤N≤105
1≤数列中元素≤109

输入样例:

5
3 4 2 7 5

输出样例:

-1 3 -1 2 2

AC代码:

#include <bits/stdc++.h>
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const double INF = 0x3f3f3f3f3f3f3f3f;
using namespace std;
const int maxn = 1e5 + 6;

int stk[maxn], tt;

int main(){
    int n; sd(n);
    for(int i = 0;i < n;++i){
        int x; sd(x);
        while(tt && stk[tt] >= x) tt--;
        if(tt) cout << stk[tt] << " ";
        else cout << -1 << " ";
        stk[++tt] = x;
    }
    cout << endl;

    return 0;
}

6)单调队列

给定一个大小为n≤10的数组。

有一个大小为k的滑动窗口,它从数组的最左边移动到最右边。

您只能在窗口中看到k个数字。

每次滑动窗口向右移动一个位置。

以下是一个例子:

该数组为[1 3 -1 -3 5 3 6 7],k为3。

窗口位置最小值最大值
[1 3 -1] -3 5 3 6 7-13
1 [3 -1 -3] 5 3 6 7-33
1 3 [-1 -3 5] 3 6 7-35
1 3 -1 [-3 5 3] 6 7-35
1 3 -1 -3 [5 3 6] 736
1 3 -1 -3 5 [3 6 7]37

您的任务是确定滑动窗口位于每个位置时,窗口中的最大值和最小值。

输入格式

输入包含两行。

第一行包含两个整数n和k,分别代表数组长度和滑动窗口的长度。

第二行有n个整数,代表数组的具体数值。

同行数据之间用空格隔开。

输出格式

输出包含两个。

第一行输出,从左至右,每个位置滑动窗口中的最小值。

第二行输出,从左至右,每个位置滑动窗口中的最大值。

输入样例:

8 3
1 3 -1 -3 5 3 6 7

输出样例:

-1 -3 -3 -3 3 3
3 3 5 5 6 7

AC代码:

#include <bits/stdc++.h>
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const double INF = 0x3f3f3f3f3f3f3f3f;
using namespace std;
const int maxn = 1e6 + 6;

// 单调队列 - 滑动窗口
int arr[maxn], qu[maxn], hh, tt;

int main(){
    int n, k; sd(n), sd(k);
    hh = 0, tt = -1;
    for(int i = 0;i < n;++i){
        sd(arr[i]);
    }
    for(int i = 0;i < n;++i){
        if(hh <= tt && i - k + 1 > qu[hh]) hh++;
        while(hh <= tt && arr[qu[tt]] >= arr[i]) tt--;
        qu[++tt] = i;
        if(i >= k - 1)
            cout << arr[qu[hh]] << " ";
    }
    cout << endl;
    hh = 0, tt = -1;
    for(int i = 0;i < n;++i){
        if(hh <= tt && i - k + 1 > qu[hh]) hh++;
        while(hh <= tt && arr[qu[tt]] <= arr[i]) tt--;
        qu[++tt] = i;
        if(i >= k - 1)
            cout << arr[qu[hh]] << " ";
    }
    cout << endl;

    return 0;
}

7)KMP

给定一个模式串S,以及一个模板串P,所有字符串中只包含大小写英文字母以及阿拉伯数字。

模板串P在模式串S中多次作为子串出现。

求出模板串P在模式串S中所有出现的位置的起始下标。

输入格式

第一行输入整数N,表示字符串P的长度。

第二行输入字符串P。

第三行输入整数M,表示字符串S的长度。

第四行输入字符串M。

输出格式

共一行,输出所有出现位置的起始下标(下标从0开始计数),整数之间用空格隔开。

数据范围

1≤N≤104
1≤M≤105

输入样例:

3
aba
5
ababa

输出样例:

0 2

AC代码:

#include <bits/stdc++.h>
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const double INF = 0x3f3f3f3f3f3f3f3f;
using namespace std;
const int maxn = 1e5 + 6;
 
int Next[maxn];
queue<int > ans;
 
void ca_next(string str, int len){
    int k = -1; Next[0] = -1;//-1表示不存在最大公共前缀后缀,方便后面的访问
    for (int i = 1; i < len; i++){
        while (k > -1 && str[k + 1] != str[i])  k = Next[k];
        if (str[k + 1] == str[i])   k++;
        Next[i] = k;
    }
}
 
void KMP(string ts, string ps){
    int ts_len = ts.size(),ps_len = ps.size();
    ca_next(ps, ps_len);
    int k = -1;
    for (int i = 0; i < ts_len; i++){
        while (k >-1 && ps[k + 1] != ts[i])  k = Next[k];
        if (ps[k + 1] == ts[i])   k++;
        if (k == ps_len - 1)  ans.push(i - ps_len + 1);
    }
    if(ans.empty()) ans.push(-1);
}
 
int main(){
    string s = "ABABABABGFABAC";
    string p = "ABAB";
    int slen, plen;
    sd(plen); cin >> p;
    sd(slen); cin >> s;
    KMP(s,p);
    while(!ans.empty()){
        cout << ans.front() << " ";
        ans.pop();
    }
    cout << endl;

    return 0;
}
//4

8)Trie

维护一个字符串集合,支持两种操作:

  1. “I x”向集合中插入一个字符串x;
  2. “Q x”询问一个字符串在集合中出现了多少次。

共有N个操作,输入的字符串总长度不超过 105105,字符串仅包含小写英文字母。

输入格式

第一行包含整数N,表示操作数。

接下来N行,每行包含一个操作指令,指令为”I x”或”Q x”中的一种。

输出格式

对于每个询问指令”Q x”,都要输出一个整数作为结果,表示x在集合中出现的次数。

每个结果占一行。

数据范围

1≤N≤2∗1041≤N≤2∗104

输入样例:

5
I abc
Q abc
Q ab
I ab
Q ab

输出样例:

1
0
1

AC代码:

#include <bits/stdc++.h>
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
using namespace std;
const int maxn = 3e6 + 6;
const int N = 1e5 + 6;

// Trie树 - 字符串统计
int son[N][26], cnt[N], idx;
char str[N];

void insert(char *str){
    int p = 0;
    for (int i = 0; str[i]; i ++ ){
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}

int query(char *str){
    int p = 0;
    for (int i = 0; str[i]; i ++ ){
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

int main(){
    int n;
    scanf("%d", &n);
    while (n -- ){
        char op[2];
        scanf("%s%s", op, str);
        if (*op == 'I') insert(str);
        else printf("%d\n", query(str));
    }

    return 0;
}

9)并查集

一共有n个数,编号是1~n,最开始每个数各自在一个集合中。

现在要进行m个操作,操作共有两种:

  1. “M a b”,将编号为a和b的两个数所在的集合合并,如果两个数已经在同一个集合中,则忽略这个操作;
  2. “Q a b”,询问编号为a和b的两个数是否在同一个集合中;

输入格式

第一行输入整数n和m。

接下来m行,每行包含一个操作指令,指令为“M a b”或“Q a b”中的一种。

输出格式

对于每个询问指令”Q a b”,都要输出一个结果,如果a和b在同一集合内,则输出“Yes”,否则输出“No”。

每个结果占一行。

数据范围

1≤n,m≤105

输入样例:

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

输出样例:

Yes
No
Yes

AC代码:一般并查集

#include <bits/stdc++.h>
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
using namespace std;
const int maxn = 1e5 + 6;

int fa[maxn];

int Find(int a){
    return a == fa[a] ? fa[a] : fa[a] = Find(fa[a]);
}

void Union(int a, int b){
    int p = Find(a), q = Find(b);
    if(p != q){
        fa[p] = q;
    }
}

int main(){
    int n, m; sd(n), sd(m);
    for(int i = 0;i < maxn;++i) fa[i] = i;
    for(int i = 0;i < m;++i){
        string str; cin >> str;
        int a, b; sd(a), sd(b);
        if(str == "M") Union(a, b);
        else {
            int p = Find(a), q = Find(b);
            if(p != q) puts("No");
            else puts("Yes");
        }
    }
    
    return 0;
}

哈希并查集(仍然很玄学,不知道如何优化时间复杂度)

#include <bits/stdc++.h>
#include <unordered_map>
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
using namespace std;
const int maxn = 1e5 + 6;

unordered_map<int ,int > fa;

int Find(int a){
    // 取或的顺序不能交换
    if(!fa.count(a) || fa[a] == a){
        return fa[a] = a;
    }
    return fa[a] = Find(fa[a]);
}

void Union(int a, int b){
    int p = Find(a), q = Find(b);
    if(p != q){
        fa[p] = q;
    }
}

int main(){
    int n, m; sd(n), sd(m);
    for(int i = 0;i < m;++i){
        string str; cin >> str;
        int a, b; sd(a), sd(b);
        if(str == "M") Union(a, b);
        else {
            int p = Find(a), q = Find(b);
            if(p != q) puts("No");
            else puts("Yes");
        }
    }
    
    return 0;
}

10)堆

输入一个长度为n的整数数列,从小到大输出前m小的数。

输入格式

第一行包含整数n和m。

第二行包含n个整数,表示整数数列。

输出格式

共一行,包含m个整数,表示整数数列中前m小的数。

数据范围

1≤m≤n≤1051≤m≤n≤105,
1≤数列中元素≤1091≤数列中元素≤109

输入样例:

5 3
4 5 1 3 2

输出样例:

1 2 3

AC代码:

#include <bits/stdc++.h>
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const double INF = 0x3f3f3f3f3f3f3f3f;
using namespace std;
const int maxn = 1e5 + 6;

// -- 如何手写一个堆 heap[maxn], size = 1;
/* 支持的功能:
 * 1.插入一个数 heap[size++] = x; up(size);
 * 2.删除最小值 heap[1] = heap[size--]; down(1);
 * 3.求集合当前的最小值 heap[1];
 * 4.删除任意一个元素 heap[k] = heap[size--]; down(k), up(k);
 * 5.修改任意一个元素 heap[k] = x; up(k), down(k);
 */

int heap[maxn];
int Size = 0;

void up(int k){
    int fi = k >> 1;
    if(fi > 0 && heap[fi] > heap[k]){
        swap(heap[k], heap[fi]);
        up(fi);
    }
}

void down(int k){
    int lson = k << 1, rson = lson + 1;
    int ret = k;
    if(lson <= Size && heap[lson] < heap[ret]) ret = lson;
    if(rson <= Size && heap[rson] < heap[ret]) ret = rson;
    if(ret == k) return ;
    else {
        swap(heap[ret], heap[k]);
        down(ret);
    }
}

int Get_Size(){
    return Size;
}

void Insert(int x){
    heap[++Size] = x;
    up(Size);
}

int Top(){
    return heap[1];
}

void Pop(){
    heap[1] = heap[Size--];
    down(1);
}

void Del_Loc(int k){
    heap[k] = heap[Size--];
    down(k), up(k);
}

void Change_Loc(int k, int x){
    heap[k] = x;
    down(k), up(k);
}


int main(){
    int n, m; sd(n), sd(m);
    for(int i = 0;i < n;++i){
        int tmp; sd(tmp);
        Insert(tmp);
    }
    for(int i = 0;i < m;++i) {
        cout << Top() << " ";
        Pop(); 
    }

    return 0;
}

11)哈希表

维护一个集合,支持如下几种操作:

  1. “I x”,插入一个数x;
  2. “Q x”,询问数x是否在集合中出现过;

现在要进行N次操作,对于每个询问操作输出对应的结果。

输入格式

第一行包含整数N,表示操作数量。

接下来N行,每行包含一个操作指令,操作指令为”I x”,”Q x”中的一种。

输出格式

对于每个询问指令“Q x”,输出一个询问结果,如果x在集合中出现过,则输出“Yes”,否则输出“No”。

每个结果占一行。

数据范围

1≤N≤1051≤N≤105
−109≤x≤109−109≤x≤109

输入样例:

5
I 1
I 2
I 3
Q 2
Q 5

输出样例:

Yes
No

1.拉链法

#include <bits/stdc++.h>
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const double INF = 0x3f3f3f3f3f3f3f3f;
using namespace std;
const int maxn = 1e5 + 3;

int h[maxn], e[maxn], ne[maxn], idx;

void Insert(int x){
    int k = (x % maxn + maxn) % maxn;
    e[idx] = x, ne[idx] = h[k], h[k] = idx++;
}

bool Find(int x){
    int k = (x % maxn + maxn) % maxn;
    for(int i = h[k];i != -1;i = ne[i]){
        if(e[i] == x) return true;
    }
    return false;
}

int main(){
    int n; sd(n);
    memset(h, -1, sizeof h);
    while(--n >= 0){
        string op; cin >> op;
        int x; sd(x);
        if(op == "I"){
            Insert(x);
        }else {
            if(Find(x)) puts("Yes");
            else puts("No");
        }
    }

    return 0;
}

2.开发寻址法

#include <bits/stdc++.h>
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const double INF = 0x3f3f3f3f3f3f3f3f;
using namespace std;
const int maxn = 2e5 + 3;

int h[maxn];

int Find(int x){
    int k = (x % maxn + maxn) % maxn;
    while(h[k] != inf && h[k] != x){
        k++;
        if(k == maxn) k = 0;
    }
    return k;
}

int main(){
    int n; sd(n);
    fill(begin(h), end(h), inf);
    while(--n >= 0){
        string op; cin >> op;
        int x; sd(x);
        int k = Find(x);
        if(op == "I"){
            h[k] = x;
        }else {
            if(h[k] == inf) puts("No");
            else puts("Yes");
        }
    }

    return 0;
}
1+

发表评论

电子邮件地址不会被公开。 必填项已用*标注

2 × 5 =