使用BitSet位集合,一个重复校验工具

2022-11-13 19:11:17 集合 校验 重复

BitSet位集合,一个重复校验工具

BitSet,位集合,用于判断一个int数字是否存在与bitSet中。

使用一个或多个long存储数据,占用内存超级小,因为判断64位二进制long中第n位为1表示n这个数字存在,为0表示不存在。所以一个long可以表示2^63 -1个数字的存在情况。

使用场景,如手机号重复校验,数字id重复校验,QQ号重复校验等大量防重的场景。

存在与否是精确的,说不存在绝对不存在,说存在绝对存在,不像布隆过滤器。

1.bitset的内部实现是long数组,因为一个long位数不够表示时,会扩展到多个long

2.set中每一个位的默认值为false(0)

3.bitset长度按需增长

4.bitset非线程安全

    public static void bitSetDemo() {
        
        BitSet bs = new BitSet(10);
        bs.set(1);
        bs.set(2);
        bs.set(5);
        System.out.println(bs.get(2));//true
        System.out.println(bs.get(1));//true
        System.out.println(bs.get(3));//false,不存在
        System.out.println(bs.get(5));//true
        //返回bitSet中已存入的数量
        System.out.println(bs.cardinality());//3
        //逻辑位数
        System.out.println(bs.length());//6
        //实际位数
        System.out.println(bs.size());//64
        System.out.println(bs.toString());//{1, 2, 5}
        BitSet bs2 = new BitSet();
        bs2.set(1);
        bs2.set(2);
        bs2.set(6);
        System.out.println(bs2.toString());//{1, 2, 6}
        //取交集,两者都有的才保留
        bs.and(bs2);
        System.out.println(bs.toString());//{1, 2}
        //取并集,把两者所有的都保留
        bs.or(bs2);
        System.out.println(bs.toString());//{1, 2, 6}
    }

BitSet的基本用法

概念

bitset可以说是一个多位二进制数,每八位占用一个字节,因为支持基本的位运算,所以可用于状态压缩,n位bitset执行一次位运算的时间复杂度可视为n/32.

基本操作

1.定义:

  • bitset< n > s;

表示一个n位的二进制数,<>中填写位数;

2.位运算操作符:

  • ~s: 返回对s每一位取反后的结果;
  • &,|,^:返回对两个位数相同的bitset执行按位与、或、异或运算的结果;
  • <<, >>:返回把一个bitset左移,右移若干位的结果.(补零);
  • ==,!=:比较两个位数相同的bitset代表的二进制数是否相等;

3.[ ]操作符:

  • s[k] :表示s的第k位,即可取值也可赋值,编号从0开始;

4.count:

  • s.count() 返回二进制串中有多少个1;

5.any/none

若s所有位都为0,则s.any()返回false,s.none()返回true;

若s至少有一位为1,则s.any()返回true,s.none()返回false;

6.set/rest/flip

  • s.set()把s所有位变为1;
  • s.set(k,v)把s的第k位改为v,即s[k]=v;
  • s.reset()把s的所有位变为0.
  • s.reset(k)把s的第k位改为0,即s[k]=0;
  • s.flip()把s所有位取反.即s=~s;
  • s.flip(k)把s的第k位取反,即s[k]^=1;

题目

可达性统计(AcWing164)

思路:

遍历一遍图,在回溯时将子节点状态加入节点状态中,用一个n长度的二进制bitset串记录状态第i位为1表示i节点从该节点可达,最后输出每个节点状态中1的个数即可。遍历时从入度为1的节点开始.

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll inf=1e9+7;
bitset<30005> s[30005];
vector<int> g[30005];
int in[30005], vis[30005];
queue<int> q;
void dfs(int v)
{
    //printf("v=%d\n",v);
    if(vis[v])
    {
        return ;
    }
    s[v][v]=1;
    for(int i=0;i<g[v].size();i++)
    {
        int u=g[v][i];
        dfs(u);
        s[v]|=s[u];
    }
    vis[v]=1;
}
int main()
{
    int n, m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int u, v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        in[v]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(in[i]==0)
        {
            q.push(i);
        }
    }
    while(!q.empty())
    {
        int v=q.front();
        q.pop();
        dfs(v);
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d\n",s[i].count());
    }
}

以上为个人经验,希望能给大家一个参考,也希望大家多多支持。

相关文章