高级数据结构及应用 —— 使用 bitmap 进行字符串去重
2024-08-26 19:35:19
bitmap 即为由单个元素为 boolean(0/1, 0 表示未出现,1 表示已经出现过)的数组。
如果C/C++ 没有原生的 boolean 类型,可以用 int 或 char 来作为 bitmap 使用,如果我们要判断某字符(char)是否出现过,
- 使用 int 作为 bitmap 的底层数据结构,bitmap 即为 int 数组,一个 int 长度为 32 个 bit 位,
- c / 32 ⇒ bitmap 中的第几个 int
- c % 32 ⇒ bitmap 中的某 int 中的第几个 bit 位;
- 使用 char 作为 bitmap 的底层数据结构,bitmap 即为 char 数组,一个 char 长度为 8 个 bit 位;
- c / 8 ⇒ bitmap 中的第几个 char
- c % 8 ⇒ bitmap 中某 char 中的第几个 bit 位;
ASCII
- A-Z:65-90
- a-z:97-122
如果使用 char 作为 bitmap 的替代底层数据结构,为了实现字符串的去重需要 char 的长度为多少呢?122/8+1 ⇒ 16。如果使用 int 作为 bitmap 的底层实现,则需要 int 数组的长度为 122/32 + 1 ⇒ 4
1. int 作为底层数据结构
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 作为底层数据结构
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';
}
最新文章
- JS实现页面打印
- 使用Fluent API 配置/映射属性和类型
- mybatis 使用动态SQL
- Java关于队列的自我实现
- 全文检索引擎Solr系列—–全文检索基本原理
- Struts Convention Plugin 流程 (2.1.6+)
- sql waitfor 延时执行
- SDUT2087离散事件模拟-银行管理
- asp.net MVC日志插件Log4Net学习笔记一:保存日志到本地
- 九度OJ 1373 整数中1出现的次数(从1到n整数中1出现的次数)
- MySQL源码 information_schema新增表
- R语言 多元线性回归分析
- 1‘b0 什么意思
- 怎样在iis中发布asp.net网站
- (转)Spark JAVA RDD API
- BZOj 4540: [Hnoi2016]序列 [莫队 st表 预处理]
- Maven将中央仓库修改为阿里云的仓库地址
- 高效获得Linux函数调用栈/backtrace的方法【转】
- PC端的鼠标拖拽滑动
- nginx Access-Control-Allow-Origin css跨域