使用BitSet位集合,一个重复校验工具
阿拉的梦想 人气:0BitSet位集合,一个重复校验工具
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,用于表示一个int是否在集合中,通过get方法来判断是否存在。 底层使用一个long来表示数据, 可以把long看成64位的01二进制,第n位为1表示n存在, 第n位为0表示n不存在。 */ 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()); } }
以上为个人经验,希望能给大家一个参考,也希望大家多多支持。
加载全部内容