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

使用BitSet位集合,一個(gè)重復(fù)校驗(yàn)工具

 更新時(shí)間:2022年10月31日 08:47:33   作者:阿拉的夢(mèng)想  
這篇文章主要介紹了使用BitSet位集合,一個(gè)重復(fù)校驗(yàn)工具,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教

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)文章

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

    Java的最大棧深度與JVM核心知識(shí)介紹

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

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

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

    平衡二叉樹(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

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

    java中Hibernate面試知識(shí)點(diǎn)整理

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

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

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

    如何解決redisTemplate注入為空問(wèn)題

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

    MyBatis 自動(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ù)抽取收集

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

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

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

最新評(píng)論