使用BitSet位集合,一個重復校驗工具
BitSet位集合,一個重復校驗工具
BitSet,位集合,用于判斷一個int數(shù)字是否存在與bitSet中。
使用一個或多個long存儲數(shù)據(jù),占用內(nèi)存超級小,因為判斷64位二進制long中第n位為1表示n這個數(shù)字存在,為0表示不存在。所以一個long可以表示2^63 -1個數(shù)字的存在情況。
使用場景,如手機號重復校驗,數(shù)字id重復校驗,QQ號重復校驗等大量防重的場景。
存在與否是精確的,說不存在絕對不存在,說存在絕對存在,不像布隆過濾器。
1.bitset的內(nèi)部實現(xiàn)是long數(shù)組,因為一個long位數(shù)不夠表示時,會擴展到多個long
2.set中每一個位的默認值為false(0)
3.bitset長度按需增長
4.bitset非線程安全
public static void bitSetDemo() { /** BitSet,用于表示一個int是否在集合中,通過get方法來判斷是否存在。 底層使用一個long來表示數(shù)據(jù), 可以把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中已存入的數(shù)量 System.out.println(bs.cardinality());//3 //邏輯位數(shù) System.out.println(bs.length());//6 //實際位數(shù) 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可以說是一個多位二進制數(shù),每八位占用一個字節(jié),因為支持基本的位運算,所以可用于狀態(tài)壓縮,n位bitset執(zhí)行一次位運算的時間復雜度可視為n/32.
基本操作
1.定義:
bitset< n > s;
表示一個n位的二進制數(shù),<>中填寫位數(shù);
2.位運算操作符:
~s
: 返回對s每一位取反后的結(jié)果;&,|,^
:返回對兩個位數(shù)相同的bitset執(zhí)行按位與、或、異或運算的結(jié)果;<<, >>
:返回把一個bitset左移,右移若干位的結(jié)果.(補零);==,!=
:比較兩個位數(shù)相同的bitset代表的二進制數(shù)是否相等;
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所有位變?yōu)?;s.set(k,v)
把s的第k位改為v,即s[k]=v;s.reset()
把s的所有位變?yōu)?.s.reset(k)
把s的第k位改為0,即s[k]=0;s.flip()
把s所有位取反.即s=~s;s.flip(k)
把s的第k位取反,即s[k]^=1;
題目
可達性統(tǒng)計(AcWing164)
思路:
遍歷一遍圖,在回溯時將子節(jié)點狀態(tài)加入節(jié)點狀態(tài)中,用一個n長度的二進制bitset串記錄狀態(tài)第i位為1表示i節(jié)點從該節(jié)點可達,最后輸出每個節(jié)點狀態(tài)中1的個數(shù)即可。遍歷時從入度為1的節(jié)點開始.
代碼:
#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()); } }
以上為個人經(jīng)驗,希望能給大家一個參考,也希望大家多多支持腳本之家。
相關(guān)文章
Spring配置中transactionAttributes的使用方法介紹
這篇文章主要介紹了Spring配置中transactionAttributes的使用方法介紹的相關(guān)內(nèi)容,具有一定參考價值,需要的朋友可以了解下。2017-09-09深入了解SpringAOP中的jdk動態(tài)代理與CGlib
這篇文章主要介紹了深入了解SpringAOP中的jdk動態(tài)代理與CGlib,一般我們編寫程序的思想是縱向的,也就是一個方法代碼從該方法第一行開始往下一步一步走,直到走完最后一行代碼,也就是說很多業(yè)務都需要的比如用戶鑒權(quán),資源釋放等,需要的朋友可以參考下2023-12-12基于Java8 Stream API實現(xiàn)數(shù)據(jù)抽取收集
這篇文章主要介紹了基于Java8 Stream API實現(xiàn)數(shù)據(jù)抽取收集,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-03-03