使用BitSet位集合,一個(gè)重復(fù)校驗(yàn)工具
BitSet位集合,一個(gè)重復(fù)校驗(yàn)工具
BitSet,位集合,用于判斷一個(gè)int數(shù)字是否存在與bitSet中。
使用一個(gè)或多個(gè)long存儲(chǔ)數(shù)據(jù),占用內(nèi)存超級(jí)小,因?yàn)榕袛?4位二進(jìn)制long中第n位為1表示n這個(gè)數(shù)字存在,為0表示不存在。所以一個(gè)long可以表示2^63 -1個(gè)數(shù)字的存在情況。
使用場(chǎng)景,如手機(jī)號(hào)重復(fù)校驗(yàn),數(shù)字id重復(fù)校驗(yàn),QQ號(hào)重復(fù)校驗(yàn)等大量防重的場(chǎng)景。
存在與否是精確的,說(shuō)不存在絕對(duì)不存在,說(shuō)存在絕對(duì)存在,不像布隆過(guò)濾器。
1.bitset的內(nèi)部實(shí)現(xiàn)是long數(shù)組,因?yàn)橐粋€(gè)long位數(shù)不夠表示時(shí),會(huì)擴(kuò)展到多個(gè)long
2.set中每一個(gè)位的默認(rèn)值為false(0)
3.bitset長(zhǎng)度按需增長(zhǎng)
4.bitset非線程安全
public static void bitSetDemo() { /** BitSet,用于表示一個(gè)int是否在集合中,通過(guò)get方法來(lái)判斷是否存在。 底層使用一個(gè)long來(lái)表示數(shù)據(jù), 可以把long看成64位的01二進(jìn)制,第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í)際位數(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可以說(shuō)是一個(gè)多位二進(jìn)制數(shù),每八位占用一個(gè)字節(jié),因?yàn)橹С只镜奈贿\(yùn)算,所以可用于狀態(tài)壓縮,n位bitset執(zhí)行一次位運(yùn)算的時(shí)間復(fù)雜度可視為n/32.
基本操作
1.定義:
bitset< n > s;
表示一個(gè)n位的二進(jìn)制數(shù),<>中填寫位數(shù);
2.位運(yùn)算操作符:
~s
: 返回對(duì)s每一位取反后的結(jié)果;&,|,^
:返回對(duì)兩個(gè)位數(shù)相同的bitset執(zhí)行按位與、或、異或運(yùn)算的結(jié)果;<<, >>
:返回把一個(gè)bitset左移,右移若干位的結(jié)果.(補(bǔ)零);==,!=
:比較兩個(gè)位數(shù)相同的bitset代表的二進(jìn)制數(shù)是否相等;
3.[ ]操作符:
s[k]
:表示s的第k位,即可取值也可賦值,編號(hào)從0開(kāi)始;
4.count:
s.count()
返回二進(jìn)制串中有多少個(gè)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;
題目
可達(dá)性統(tǒng)計(jì)(AcWing164)
思路:
遍歷一遍圖,在回溯時(shí)將子節(jié)點(diǎn)狀態(tài)加入節(jié)點(diǎn)狀態(tài)中,用一個(gè)n長(zhǎng)度的二進(jìn)制bitset串記錄狀態(tài)第i位為1表示i節(jié)點(diǎn)從該節(jié)點(diǎn)可達(dá),最后輸出每個(gè)節(jié)點(diǎn)狀態(tài)中1的個(gè)數(shù)即可。遍歷時(shí)從入度為1的節(jié)點(diǎn)開(kāi)始.
代碼:
#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()); } }
以上為個(gè)人經(jīng)驗(yàn),希望能給大家一個(gè)參考,也希望大家多多支持腳本之家。
相關(guān)文章
Spring配置中transactionAttributes的使用方法介紹
這篇文章主要介紹了Spring配置中transactionAttributes的使用方法介紹的相關(guān)內(nèi)容,具有一定參考價(jià)值,需要的朋友可以了解下。2017-09-09平衡二叉樹(shù)的左右旋以及雙旋轉(zhuǎn)的圖文詳解
今天小編就為大家分享一篇關(guān)于平衡二叉樹(shù)的左右旋以及雙旋轉(zhuǎn)的圖文詳解,小編覺(jué)得內(nèi)容挺不錯(cuò)的,現(xiàn)在分享給大家,具有很好的參考價(jià)值,需要的朋友一起跟隨小編來(lái)看看吧2019-01-01深入了解SpringAOP中的jdk動(dòng)態(tài)代理與CGlib
這篇文章主要介紹了深入了解SpringAOP中的jdk動(dòng)態(tài)代理與CGlib,一般我們編寫程序的思想是縱向的,也就是一個(gè)方法代碼從該方法第一行開(kāi)始往下一步一步走,直到走完最后一行代碼,也就是說(shuō)很多業(yè)務(wù)都需要的比如用戶鑒權(quán),資源釋放等,需要的朋友可以參考下2023-12-12java中Hibernate面試知識(shí)點(diǎn)整理
在本篇文章里小編給大家整理的是一篇關(guān)于java中Hibernate面試知識(shí)點(diǎn)整理內(nèi)容,有興趣的朋友們可以學(xué)習(xí)參考下。2021-01-01MyBatis 自動(dòng)更新時(shí)間的方法實(shí)現(xiàn)
本文主要介紹了MyBatis 自動(dòng)更新時(shí)間的方法實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2024-06-06基于Java8 Stream API實(shí)現(xiàn)數(shù)據(jù)抽取收集
這篇文章主要介紹了基于Java8 Stream API實(shí)現(xiàn)數(shù)據(jù)抽取收集,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-03-03