快捷導(dǎo)航

高級(jí)數(shù)據(jù)結(jié)構(gòu)及應(yīng)用之使用bitmap進(jìn)行字符串去重的方法實(shí)例

更新時(shí)間：2019年02月18日 09:00:40 作者：Inside_Zhang

今天小編就為大家分享一篇關(guān)于高級(jí)數(shù)據(jù)結(jié)構(gòu)及應(yīng)用之使用bitmap進(jìn)行字符串去重的方法實(shí)例，小編覺(jué)得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來(lái)看看吧

bitmap 即為由單個(gè)元素為 boolean（0/1, 0 表示未出現(xiàn)，1 表示已經(jīng)出現(xiàn)過(guò)）的數(shù)組。

如果C/C++ 沒(méi)有原生的 boolean 類型，可以用 int 或 char 來(lái)作為 bitmap 使用，如果我們要判斷某字符（char）是否出現(xiàn)過(guò)

使用 int 作為 bitmap 的底層數(shù)據(jù)結(jié)構(gòu)，bitmap 即為 int 數(shù)組，一個(gè) int 長(zhǎng)度為 32 個(gè) bit 位，

c / 32 ⇒ bitmap 中的第幾個(gè) int
c % 32 ⇒ bitmap 中的某 int 中的第幾個(gè) bit 位；

使用 char 作為 bitmap 的底層數(shù)據(jù)結(jié)構(gòu)，bitmap 即為 char 數(shù)組，一個(gè) char 長(zhǎng)度為 8 個(gè) bit 位；

c / 8 ⇒ bitmap 中的第幾個(gè) char
c % 8 ⇒ bitmap 中某 char 中的第幾個(gè) bit 位；

ASCII

A-Z：65-90
a-z：97-122

如果使用 char 作為 bitmap 的替代底層數(shù)據(jù)結(jié)構(gòu)，為了實(shí)現(xiàn)字符串的去重需要 char 的長(zhǎng)度為多少呢？122/8+1 ⇒ 16。如果使用 int 作為 bitmap 的底層實(shí)現(xiàn)，則需要 int 數(shù)組的長(zhǎng)度為 122/32 + 1 ⇒ 4

1. int 作為底層數(shù)據(jù)結(jié)構(gòu)

void dedup(const char* src, char* dst)
{
  unsigned int exists[4] = { 0 };
  int i = 0, j = 0;
  unsigned int mask;
  char c;
  while (src[i])
  {
    c = src[i];
    mask = 1 << (c % 32);
    if ((exists[c / 32] & mask) == 0)
    {
      dst[j++] = c;
      exists[c / 32] |= mask;
    }
    i++;
  }
  dst[j] = '\0';
}

2. 使用 char 作為底層數(shù)據(jù)結(jié)構(gòu)

void dedup(const char* src, char* dst)
{
  unsigned char exists[16] = { 0 };
  int i = 0, j = 0;
  unsigned int mask;
  char c;
  while (src[i])
  {
    c = src[i];
    mask = 1 << (c % 8);
    if ((exists[c / 8] & mask) == 0)
    {
      dst[j++] = c;
      exists[c / 8] |= mask;
    }
    i++;
  }
  dst[j] = '\0';
}

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，謝謝大家對(duì)腳本之家的支持。如果你想了解更多相關(guān)內(nèi)容請(qǐng)查看下面相關(guān)鏈接

您可能感興趣的文章:

相關(guān)文章

JVM優(yōu)先級(jí)線程池做任務(wù)隊(duì)列的實(shí)現(xiàn)方法
這篇文章主要介紹了JVM優(yōu)先級(jí)線程池做任務(wù)隊(duì)列的實(shí)現(xiàn)方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
2020-08-08
Java實(shí)現(xiàn)局域網(wǎng)聊天小程序
這篇文章主要為大家詳細(xì)介紹了Java實(shí)現(xiàn)局域網(wǎng)聊天小程序，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2022-05-05
Java調(diào)用windows系統(tǒng)的CMD命令并啟動(dòng)新程序
本文教你如何使用java程序調(diào)用windows系統(tǒng)的CMD命令啟動(dòng)新程序方法,需要的朋友可以參考下
2023-05-05
MyBatis創(chuàng)建存儲(chǔ)過(guò)程的實(shí)例代碼_動(dòng)力節(jié)點(diǎn)Java學(xué)院整理
本節(jié)需要用到的有2部分，第一部分是如何在Derby中創(chuàng)建存儲(chǔ)過(guò)程，第二部分是如何在Mybatis中調(diào)用存儲(chǔ)過(guò)程，具體實(shí)例代碼大家參考下本文吧
2017-09-09
Java連接數(shù)據(jù)庫(kù)JDBC技術(shù)之prepareStatement的詳細(xì)介紹
這篇文章主要介紹了Java連接數(shù)據(jù)庫(kù)JDBC技術(shù)之prepareStatement的詳細(xì)介紹，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
2020-07-07
一文了解mybatis的延遲加載
本文主要為大家詳細(xì)介紹下mybatis的延遲加載，從原理上介紹下怎么使用、有什么好處能規(guī)避什么問(wèn)題。感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下
2022-07-07
Java中mybatis的三種分頁(yè)方式
這篇文章主要介紹了Java中mybatis的三種分頁(yè)方式，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考一下
2022-08-08
Jmeter內(nèi)置變量vars和props的使用詳解
JMeter是一個(gè)功能強(qiáng)大的負(fù)載測(cè)試工具,它提供了許多有用的內(nèi)置變量來(lái)支持測(cè)試過(guò)程,其中最常用的變量是 vars 和 props,本文通過(guò)代碼示例詳細(xì)給大家介紹了Jmeter內(nèi)置變量vars和props的使用,需要的朋友可以參考下
2024-08-08
詳解Spring cloud使用Ribbon進(jìn)行Restful請(qǐng)求
這篇文章主要介紹了詳解Spring cloud使用Ribbon進(jìn)行Restful請(qǐng)求，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧
2018-04-04
java并查集算法帶你領(lǐng)略熱血江湖
這篇文章主要為大家介紹了java并查集算法，以大家熱愛(ài)的方式，帶你領(lǐng)略熱血江湖中的并查集算法，有需要的朋友可以借鑒參考下，希望能夠有所幫助
2021-11-11