高级数据结构及应用之使用bitmap进行字符串去重的方法实例

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';
}

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对我们的支持。如果你想了解更多相关内容请查看下面相关链接

赞 (0)

相关推荐

  • JavaScript常用工具方法封装

    因为工作中经常用到这些方法,所有便把这些方法进行了总结. JavaScript 1. type 类型判断 isString (o) { //是否字符串 return Object.prototype.toString.call(o).slice(8, -1) === 'String' } isNumber (o) { //是否数字 return Object.prototype.toString.call(o).slice(8, -1) === 'Number' } isBoolean (o)

  • 谈谈JavaScript中super(props)的重要性

    我听说 Hooks 最近很火.讽刺的是,我想用一些关于 class 组件的有趣故事来开始这篇文章.你觉得如何? 本文中这些坑对于你正常使用 React 并不是很重要. 但是假如你想更深入的了解它的运作方式,就会发现实际上它们很有趣. 开始第一个. 首先在我的职业生涯中写过的super(props) 自己都记不清: class Checkbox extends React.Component { constructor(props) { super(props); this.state = { i

  • JavaScript"模拟事件"的注意要点详解

    DOM中的事件模拟 三个步骤: 首先通过document.createEvent()方法创建event对象,接收一个参数,即表示要创建的事件类型的字符串: UIEvents(DOM3中的UIEvent)鼠标和键盘事件: MouseEvents(DOM3中的MouseEvent)鼠标事件: MutationEvents(DOM3中的MutationEvent)变动事件: HTMLEvents(没有DOM3中对应的事件)HTML事件: 其次在创建了event对象之后,还需要使用与事件有关的信息对其进

  • 实例讲解Java中random.nextInt()与Math.random()的基础用法

    实例讲解Java中random.nextInt()与Math.random()的基础用法

    1.来源 random.nextInt() 为 java.util.Random类中的方法: Math.random() 为 java.lang.Math 类中的静态方法. 2.用法 产生0-n的伪随机数(伪随机数参看最后注解): // 两种生成对象方式:带种子和不带种子(两种方式的区别见注解) Random random = new Random(); Integer res = random.nextInt(n); Integer res = (int)(Math.random() * n)

  • PyQt5内嵌浏览器注入JavaScript脚本实现自动化操作的代码实例

    概要 应同学邀请,演示如何使用 PyQt5 内嵌浏览器浏览网页,并注入 Javascript 脚本实现自动化操作. 下面测试的是一个廉价机票预订网站(http://www.flyscoot.com/),关键点如下 使用 QWebEngineView 加载网页,并显示进度. 在默认配置(QWebEngineProfile)中植入 Javascript 内容,这样脚本会在所有打开的网页中执行,不论跳转到哪个网址. Javascript 脚本使用网址中的路径名,判断当前网页位置,从而决定执行哪种操作.

  • Android Java调用自己C++类库的实例讲解

    Android Java 如何调用自己的 C++ 的类库 下面以 Java 调用 C++ 的加法运算函数为例,做简单说明. (使用 Android Studio 3 编译) 首先编译 c++ 类库 创建独立目录存放 c++ 文件,例如 "app/src/main/cpp/add.cpp",内容如下 #include <jni.h> extern "C" JNIEXPORT jint JNICALL Java_com_example_liyi_demo_U

  • 推荐15个最好用的JavaScript代码压缩工具

    推荐15个最好用的JavaScript代码压缩工具

    JavaScript 代码压缩是指去除源代码里的所有不必要的字符,而不改变其功能的过程.这些不必要的字符通常包括空格字符,换行字符,注释以及块分隔符等用来增加可读性的代码,但并不需要它来执行. 在这篇文章中,我们选择了15个最好用的 JavaScript 压缩工具,有简单的在线转换器,GUI工具和命令行界面等. 1. JavaScript Minifier It is a nice looking tool with an API to minify your js code. 2. JSMIn

  • JavaScript中.min.js和.js文件的区别讲解

    Q&A Q: .js和.min.js文件分别是什么? A: .js是JavaScript 源码文件, .min.js是压缩版的js文件. Q:为什么要压缩为.min.js文件? 减小体积  .min.js文件经过压缩,相对编译前的js文件体积较小,传输效率快. 防止窥视和窃取源代码  经过编码将变量和函数原命名改为毫无意义的命名,以防止他人窥视和窃取 js 源代码 Q:.js 和.min.js文件的优缺点? .js文件:   优点: 可读性较好,易于debug和更改.   缺点:体积较大,传输时

  • 海量数据去重排序bitmap(位图法)在java中实现的两种方法

    在海量数据中查找出重复出现的元素或者去除重复出现的元素是面试中常考的文图.针对此类问题,可以使用位图法来解决.例如:已知某个文件内包含若干个电话号码,要求统计不同的号码的个数,甚至在O(n)时间复杂度内对这些号码进行排序. 位图法需要的空间很少(依赖于数据分布,但是我们也可以通过一些放啊发对数据进行处理,使得数据变得密集),在数据比较密集的时候效率非常高.例如:8位整数可以表示的最大十进制数值为99999999,如果每个数组对应于一个bit位,那么把所有的八进制整数存储起来只需要:99Mbit

  • Java多线程实战之交叉打印的两种方法

    要求效果:先打印5次"printA-",再打印5次"printB-",每次打印间隔1秒,重复循环20次 方式一:使用wait()和notifyAll()方法 public class MyService { private volatile boolean flag = false; public synchronized void printA() { try { while (flag) { wait(); } for (int i = 0; i < 5;

随机推荐