数据结构:一般哈希

数据结构:一般哈希

题目描述

在这里插入图片描述
输入样例

5
I 1
I 2
I 3
Q 2
Q 5

输出样例

Yes
No

参考代码

拉链法

#include <iostream>
#include <cstring>
using namespace std;

const int N = 100003;

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

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

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

    return false;
}

int main()
{
    int n;
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    
    while (n --)
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        
        if (*op == 'I') insert(x);
        else
        {
            if (find(x)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

开放寻址法

#include <iostream>
#include <cstring>
using namespace std;

const int N = 200003, null = 0x3f3f3f3f;

int h[N];


int find(int x)
{
    int k = (x % N + N) % N;
    
    while (h[k] != null && h[k] != x)
    {
        k ++;
        if (k == N) k = 0;
    }
    
    return k;
}

int main()
{
    int n;
    scanf("%d", &n);
    memset(h, 0x3f, sizeof h);	// 每一个字节都是0x3f,int类型是4字节,所以是0x3f3f3f3f
    
    while (n --)
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        int k = find(x);
        if (*op == 'I') h[k] = x;
        else
        {
            if (h[k] != null) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

相关推荐

  1. 数据结构-

    2024-06-08 18:48:01       36 阅读
  2. 查找【数据结构

    2024-06-08 18:48:01       31 阅读

最近更新

  1. 6.11 c语言

    2024-06-08 18:48:01       0 阅读
  2. DP专项训练

    2024-06-08 18:48:01       0 阅读
  3. uniapp面试题

    2024-06-08 18:48:01       0 阅读
  4. 【lesson3】服务端Json工具类的设计和实现

    2024-06-08 18:48:01       0 阅读
  5. 力扣475.供暖器

    2024-06-08 18:48:01       0 阅读
  6. 图片based64编码解码python代码

    2024-06-08 18:48:01       0 阅读

热门阅读

  1. Docker

    Docker

    2024-06-08 18:48:01      4 阅读
  2. Redis命令使用示例(一)

    2024-06-08 18:48:01       4 阅读
  3. Ansible——user模块

    2024-06-08 18:48:01       4 阅读
  4. SD-WAN加速跨国服务器访问

    2024-06-08 18:48:01       5 阅读
  5. Spring Boot中实现规则引擎源码教程

    2024-06-08 18:48:01       3 阅读
  6. android:text 总为大写字母的原因

    2024-06-08 18:48:01       3 阅读
  7. input只允许输入数字

    2024-06-08 18:48:01       4 阅读
  8. 数据结构汇总学习(ing)

    2024-06-08 18:48:01       5 阅读
  9. 注解 - @RequestBody

    2024-06-08 18:48:01       4 阅读
  10. 阿里云一键登录号码认证服务

    2024-06-08 18:48:01       5 阅读