博客

​

​

活动地址：

CSDN21天学习挑战赛

前言

对哈希表，平常做题用的很多的是容器：

map，unordered_map

，对于这两个容器呢，我有详细的介绍在

c++知识专栏

简单介绍

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希（Hash）表，函数f(key)为哈希(Hash) 函数。

模拟散列表（例题）

点击跳转至例题 模拟散列表


这道题要求要求维护一个集合，支持以下操作：

1. 插入一个数x
2. 询问数x是否在集合中出现过

注意：对于哈希表的

下标范围

，需要是一个

质数

，这道题数据范围是1e5，最小的质数是100003 ，但是一般可以设置为

199997

• 
  x % N 如果x为负数的话，那么结果就会是负数
  
  ，但是h数组是没有负数下标的，为了解决这个问题，我们可以进行这个操作
  
  
  (x % N + N) % N
  
  
• memset 的头文件是
  
  cstring
  

#include<iostream>
#include<cstring>
using namespace std ;
const int N = 199997 , inf = 0x3f3f3f3f;
int h[N];
int find(int x)
{
    int t = (x % N + N) % N ;
    while(h[t] != inf && h[t] != x)
    {
        if( ++ t == N) t = 0 ;
    }
    return t;
}
int main()
{
    int T ;
    cin >> T;
    memset(h , 0x3f , sizeof h);
    while(T--)
    {
        char s[2];
        cin >> s[0];
        if(*s == 'I')
        {
            int x ;
            cin >> x ;
            h[find(x)] = x ;
        }
        else 
        {
            int x ;
            cin >> x ;
            if(h[find(x)] == inf) cout << "No" <<endl;
            else cout << "Yes" << endl; 
        }
    }
    return 0 ;
}

最大子集（acwing63场周赛）

​

点击跳转至周赛题：最大子集


在题目中，说容器慎用，所以用容器大概率是不好过的，

重点：证明最大子集中的长度最大为

3

这里的证明方法是acwing创始人 y总的证明方法，我直接搬过来了。

证明：

假设 a < b < c < d , {a,b,c,d}是满足题意的一个子集，所以有图可见



左右同时除以 2的x次方，得到最下面的式子：

左边为1（

奇数

）和2的y-x次方（

偶数

），右边是2的k-x次方（

偶数

）。

奇数加偶数不可能是偶数

，除非

2的y-x次方为奇数

，即 y==x




然后我们可以发现在

a 和 d之间的差值是3*2的x次方

，显然

不是

2的整数次幂，所以这道题符合题意的

最大长度为3

算法复杂度：





遍历每一个数，看它前两个数是否满足题意凑成子集

• 若第一个数满足，第二个数不满足就在结构数组里加入第一个，而不加入第二个
• 若两个都满足，那么直接跳出循环进行输出
• 若都不满足，那就是第一个数，因为一直没有更新答案

这里的

31


，是因为题目上数据范围是-10的9次方~10的九次方，那么最极限的减法结果是 2e9 ， 大于2e9的

最小

的2的整数幂是2的31次幂


一个结果，一个中间数组：

• 因为是从后往前找是否满足的数，所以
  
  先把找到的符合题意的数放入中间数组
  
  ，然后如果
  
  
  结果数组中的元素数目小于中间数组时
  
  
  ，就
  
  更新
  
  结果数组

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std ;
const int N = 1999997 , inf = 0x3f3f3f3f;
const int M = 200010;
int h[N] , q[M];
int n ;
int find(int x)
{
    int t = ((x % N) + N) % N;
    while(h[t] != x && h[t] != inf)
    {
        if(++t == N) t = 0 ;
    }
    return t ;
}
int main()
{
    cin >> n ;
    for(int i = 0 ; i < n ; i++) cin >> q[i] ;
    sort(q,q+n);
    
    memset(h,0x3f, sizeof h);
    
    int res[3] , s[3];
    int rt = 0 , st = 0 ;
    for(int i = 0 ; i < n ; i++)
    {
        for(int j = 0 ; j <= 30 ; j++)
        {
            int d = 1 << j ;
            s[0] = q[i] , st = 1;
            for(int k = 1 ; k <= 2 ; k++)
            {
                int x = q[i] - d * k ;
                if(h[find(x)] == inf) break;
                s[st++] = x ;
            }
            if(rt < st)
            {
                rt = st ;
                memcpy(res,s,sizeof s);
                if(rt == 3) break;
            }
            if(rt == 3) break;
            h[find(q[i])] = q[i];
        }
    }
    cout << rt << endl ;
    for(int i = 0 ; i < rt ; i++)
    {
        cout << res[i] << " " ;
    }
    return 0 ;
}

如果有任何问题的话，可以私信我或者在底下评论哦 ，写文不易，希望大家多多支持！