漫画算法

漫画算法

本文内容基于《漫画算法 小灰的算法之旅》，魏梦舒著。

1. Bitmap的巧用

1.1 查询

1.2 去重

1.3 Bitmap的代码实现

2. LRU算法的应用

2.1 实例问题

2.2 代码实现

3. A星寻路算法

4. 红包算法

4.1 二倍均值法

4.2 线段切割法

1. Bitmap的巧用

Bitmap算法，又叫做位图算法，这里所说的位图并不是像素图片的位图，而是内存中连续的二进制位所组成的数据结构，该算法主要用于对大量整数做去重和查询操作。

1.1 查询

举个例子，假设给出一块长度为10bit的内存空间，也就是Bitmap，想要依次插入证书4、1、2、3，需要怎么做？

• 第1步：给出一块长度为10的Bitmap，其中的每一个bit位分别对应着从0到9的整型数。此时，Bitmap的所有位都是0；
• 第2步：把整型数4