• hash整数映射模板(acwing840)

    hash：

    1.插入整数（范围大，如-1e9-1e9）,2.查询某整数是否出现过

    1.拉链法：

    #define _CRT_SECURE_NO_WARNINGS 
    #include
    #include
    #include
    #include
    #include
    #include
    #include<ctime>
    #include
    #include
    #include<stack>
    #include
    #include
    #include
    #include
    #include
    using namespace std;
    #define LL long long 
    using ull = unsigned long long;
    const LL N = 1e5 + 3;//N最好是质数
    vector p[N];
    void insert(int x)
    {
        int k = (x % N + N) % N;
        p[k].push_back(x);
    }
    int find(int x)
    {
        int k = (x % N + N) % N;
        for (int i = 0; i < p[k].size(); i++)
        {
            if (p[k][i] == x)
                return 1;
        }
        return 0;
    }
    int main() {
        int n,x;
        char op[2];
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            scanf("%s %d", op, &x);
            if (op[0] == 'I')
            {
                insert(x);

            }
            else
            {
                if (find(x))
                    printf("Yes\n");
                else
                    printf("No\n");
            }
        }


        return 0;
    }

    2.开放寻地址

    #define _CRT_SECURE_NO_WARNINGS 
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    using namespace std;
    #define LL long long 
    using ull = unsigned long long;
    const LL N = 2e5 + 3;//N最好是质数并且是操作数的2-3倍
    int p[N];//p存映射前整数值
    int find(int x)
    {
        int k = (x % N + N) % N;
        while (p[k] !=1e9+10 && p[k] != x)
        {
                k++;
            if (k == N)
                k = 0;
        }
        return k;
    }
    int main() {
        int n,x;
        char op[2];
        cin >> n;
        for (int i = 0; i <= N; i++)
            p[i] = 1e9 + 10;
        for (int i = 1; i <= n; i++)
        {
            scanf("%s %d", op, &x);
            int k = find(x);
            if (op[0] == 'I')
                p[k] = x;
            else
            {
                if (p[k]!=1e9+10)
                    printf("Yes\n");
                else
                    printf("No\n");
            }
        }


        return 0;
    }

  • 相关阅读:
    长事务 (Long Transactions)
    Monitoring techniques in AWS
    044-WEB攻防-PHP应用&SQL盲注&布尔回显&延时判断&报错处理&增删改查方式
    如何使用cmd运行java程序
    Linux命令万字总结，带你实现基础Linux命令自由
    JAVA基础 - URI、URL和URN的区别
    BACnet /IP转MQTT网关
    语音信号处理的过程及其应用
    【头歌】——抓取Ethernet包（计算机网络）
    Linux系统高并发socket最大连接数所受的各种限制解决
  • 原文地址：https://blog.csdn.net/yusen_123/article/details/133818203