欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

使用BitSet位集合,一個重復校驗工具

 更新時間:2022年10月31日 08:47:33   作者:阿拉的夢想  
這篇文章主要介紹了使用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)文章

  • Java的最大棧深度與JVM核心知識介紹

    Java的最大棧深度與JVM核心知識介紹

    這篇文章主要有兩個部分,一部分介紹JAVA的最大棧深度,第二部分介紹了JVM核心知識,需要的朋友可以參考下面文章的具體內(nèi)容
    2021-09-09
  • Spring配置中transactionAttributes的使用方法介紹

    Spring配置中transactionAttributes的使用方法介紹

    這篇文章主要介紹了Spring配置中transactionAttributes的使用方法介紹的相關(guān)內(nèi)容,具有一定參考價值,需要的朋友可以了解下。
    2017-09-09
  • 平衡二叉樹的左右旋以及雙旋轉(zhuǎn)的圖文詳解

    平衡二叉樹的左右旋以及雙旋轉(zhuǎn)的圖文詳解

    今天小編就為大家分享一篇關(guān)于平衡二叉樹的左右旋以及雙旋轉(zhuǎn)的圖文詳解,小編覺得內(nèi)容挺不錯的,現(xiàn)在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧
    2019-01-01
  • 深入了解SpringAOP中的jdk動態(tài)代理與CGlib

    深入了解SpringAOP中的jdk動態(tài)代理與CGlib

    這篇文章主要介紹了深入了解SpringAOP中的jdk動態(tài)代理與CGlib,一般我們編寫程序的思想是縱向的,也就是一個方法代碼從該方法第一行開始往下一步一步走,直到走完最后一行代碼,也就是說很多業(yè)務都需要的比如用戶鑒權(quán),資源釋放等,需要的朋友可以參考下
    2023-12-12
  • java中Hibernate面試知識點整理

    java中Hibernate面試知識點整理

    在本篇文章里小編給大家整理的是一篇關(guān)于java中Hibernate面試知識點整理內(nèi)容,有興趣的朋友們可以學習參考下。
    2021-01-01
  • 詳解Java中數(shù)組判斷元素存在幾種方式比較

    詳解Java中數(shù)組判斷元素存在幾種方式比較

    這篇文章主要介紹了Java中數(shù)組判斷元素存在幾種方式比較,非常不錯,具有一定的參考借鑒價值,需要的朋友參考下吧
    2018-07-07
  • 如何解決redisTemplate注入為空問題

    如何解決redisTemplate注入為空問題

    這篇文章主要介紹了如何解決redisTemplate注入為空問題,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
    2020-07-07
  • MyBatis 自動更新時間的方法實現(xiàn)

    MyBatis 自動更新時間的方法實現(xiàn)

    本文主要介紹了MyBatis 自動更新時間的方法實現(xiàn),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2024-06-06
  • 基于Java8 Stream API實現(xiàn)數(shù)據(jù)抽取收集

    基于Java8 Stream API實現(xiàn)數(shù)據(jù)抽取收集

    這篇文章主要介紹了基于Java8 Stream API實現(xiàn)數(shù)據(jù)抽取收集,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
    2020-03-03
  • struts2實現(xiàn)文件下載功能

    struts2實現(xiàn)文件下載功能

    這篇文章主要為大家詳細介紹了struts2實現(xiàn)文件下載功能,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2018-03-03

最新評論