算法数据结构体系

1、复杂度、对数器、二分法

二分法

在一个有序数组中，找某个数是否存在
在一个有序数组中，找>=某个数最左侧的位置
在一个有序数组中，找<=某个数最右侧的位置
局部最小值问题

4、基础数据结构

单向链表

public class Node {
  public int data;
  public Node next;
  public Node(int data) {
    this.data = data;
  }
}

双向链表

public class DoubleNode {
  public int data;
  public DoubleNode last;
  public DoubleNode next;
  public Node(int data) {
    this.data = data;
  }
}

链表简单问题

反转链表
删除给定值

队列和栈

逻辑概念

队列：先进先出犹如排队
栈：先进后出好似弹夹

常见问题

双链表实现
数组实现
实现栈 getMin 方法，时间复杂度O(1)
用栈实现队列
两个栈倒来倒去
用队列实现栈

递归

Master 公式

形如 T(N) = a * T(N/b) + O(N^d)（ a、b、d都是常数）的递归函数可以通过 Master 公式确定时间复杂度 Log(b,a) < d ---> O(N^d) Log(b,a) > d ---> O(N^log(b,a)) Log(b,a) == d ---> O(N^d * logN)

5、归并排序

时间复杂度：O(n * logN)

流程：sort left, sort right, merge left and right(双指针merge)

题目

归并排序的递归和非递归实现

在一个数组中，一个数左边比它小的数的总和，叫该数的小和所有数的小和累加起来，叫数组小和

在一个数组中，任何一个前面的数a，和任何一个后面的数b，如果(a,b)是降序的，就称为降序对给定一个数组arr，求数组的降序对总数量

Leetcode[327] 区间和的个数在一个数组中，对于任何一个数num，求有多少个(后面的数*2)依然<num，返回总个数比如：[3,1,7,0,2] 3的后面有：1，0 1的后面有：0 7的后面有：0，2 0的后面没有 2的后面没有所以总共有5个

7、堆和排序

比较器

比较器的实质就是重载比较运算
比较器可以很好的应用在特殊标准的排序上
比较器可以很好的应用在根据特殊标准排序的结构上
写代码变得异常容易，还用于范型编程

// 任何比较器：
// 时间复杂度：O(N * log(N))
// compare 方法中遵循统一规范：
// 返回负数第一个参数在前
// 返回正数第二个参数在前
// 返回0无所谓谁在前
public class Age implements Comparator<Student> {
  @Override
  public int compare(Student s1, Student s2) {
    if(s1.age < s2.age) {
      return -1;
    } else if (s1.age > s2.age) {
      return 1;
    } else {
      return 0;
    }
    
    // return s1.age - s2.age;
  }
}

堆结构

堆结构就是用数组现实的完全二叉树结构
完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
完全二叉树中如果每棵子树的最小值都在顶部就是小根堆
堆结构的 heapInsert 与 heapify 操作
堆结构的增大和减小
优先级队列结构，就是堆结构

完全二叉树：只允许最后一层不满，且从左到右排列

大根堆

heapInsert

private void heapInert(int arr[], int index) {
  while (arr[index] > arr[(index - 1) / 2]) {
    swap(arr[index] > arr[(index - 1) / 2]);
    index = (index - 1) / 2;
  }
}

heapify

private void heapify(int arr[], int index, int heapSize) {
  int left = index * 2 + 1;
  while (left < heapSize) {
    int leargest = left + 1 < heapSize && arr[left + 1] > arr[left] ? arr[left + 1] : left;
    if (arr[largest] <= arr[index]) {
      break;
    }
    swap(arr, index, largest);
    index = largest;
    left = index * 2 + 1;
  }
}

当堆中一个位置发生改变，在改变位置调用 heapInsert 和 heapify 会调整位置至正确。

加强堆

最大线段重合问题（堆实现）

给定很多线段，每个线段都有两个数组[start, end],

左右都是闭区间

规定：

线段开始和结束位置一定为整数
线段重合区域长度>=1

返回线段最多重合区域中，包含了几条线段

手动改写堆题目练习

给定一个整型数组和一个布尔类型数组，int[] arr; boolean[] op;

两数组等长，长度为 N，arr[i] 表示客户编号，op[i] 表示客户操作

arr = [3, 3, 1, 2, 1, 2, 5 ...]

op = [T, T, T, T, F, T, F ... ]

依次表示：3 用户购买了一件商品，3 用户购买了一件商品，1 用户购买了一件商品，2 用户购买了一件商品，5 用户退货了一件商品...

得奖系统规则：

如果某个用户购买商品数为 0，发生了退货事件，认为该事件无效，得奖名单和之前事件一致
某用户发生购买事件，购买商品数+1，退货事件，购买商品数-1
每次都是最多K个用户的奖，K也为传入的参数
如果根据全部规则，得奖人数不够K，就以实际情况输出结果
得奖系统分为得奖区和候选区，任何用户只要购买数量>0，一定在两个区域中的一个
购买数量最大的前K名用户进入得奖区，在最初时如果得奖区没有达到K个用户，新来的用户直接进入得奖区
如果购买数量不足以进入得奖区，进入候选区
如果候选区购买数最多的用户，已经足以进入得奖区
替换得奖区中购买数最少的用户（大于才能替换）
如果得奖区购买数量最少的用户有多个，替换最早进入得奖区的用户
如果候选区购买数量最多的用户有多个，机会会给最早进入候选区的用户
候选区和得奖区是两套时间，
因用户只会在其中一个区域，所以只会有一个区域的时间，另一个没有从得奖区出来进入候选区的用户，得奖区时间删除，
进入候选区的时间就是当前事件的时间（可以理解为arr[i]和op[i]中的i）
从候选区出来进入得奖区的用户，候选区时间删除
进入得奖区的时间就是当前事件的时间（可以理解为arr[i]和op[i]中的i）
如果某用户购买数==0，离开区域，区域时间删除
下次再购买，时间重记

13、贪心算法

给定一个由字符串组成的数组strs，必须把所有的字符串拼接起来，返回所有可能的拼接结果中，字典序最小的结果

16、并查集及其相关题目

547、省份数量

岛问题

给定一个二维数组 matrix，里面的值非1即0，上下左右相邻的1认为是一片岛，返回岛数量

18、经典递归

汉诺塔

打印n层汉诺塔从最左边移动到最右边的全部过程

打印子序列

打印一个字符串的全部子序列

class Solution {
  public void print(String s) {
  	
	}
  
  public void process(char[] str,int index,List<String> ans,String path) {
    if (index == str.length) {
      ans.add(path);
      return;
    }
    // 不要当前的
    process(str, index + 1, ans, path);
    // 要当前的
    process(str, index + 1, ans, path + String.valueOf(str[index]));
  }
}

打印一个字符串的全部子序列不要重复

使用 set

所有字符串的组合

逆序栈

给你一个栈，请逆序栈

不能申请额外的数据结构，只能使用递归函数。

32、IndexTree & AC 自动机

IndexTree

IndexTree 可以根据自身规律很方便的求累加和

1 2 3 4 5 6 7 8 9 10 11 12
--------------------------- index 管理的范围（只能管理自己以自己之前的）
1 2 3 4 5 6 7 8 9 10 11 12
  1   3   5   7    9    11
      2       6         10
      1       5          9
              4
              3
              2
              1

某一 index 影响的范围：二进制最右侧 1 消除后加 1

# 比如 “8” 影响的范围 1~8
1000 -> 0001
# 比如 “12” 影响的范围 9~12
1100 -> 1001

时间复杂度：O(logN)

class IndexTree {
  public int[] tree;
  public int N;
  public IndexTree(int[] arr) {
    N = arr.size;
    tree = new index[N + 1]; // 默认下标从 1 开始，0 不用
  }
  public int sum(int index) {
    int res = 0;
    while (index > 0) {
      res += tree[index];
      index -= index & -index;
    }
    return res;
  }
  public void add(int index, int d) {
    while (index <= N) {
      tree[index] += d;
      index += index & -index
    }
  }
}

AC 自动机

34、与 hash 函数有关的结构

常见 hash 函数：SHA-1、SHA-256、SHA-512、MD5-256

哈希函数的作用：可以把数据根据不同值，几乎均匀的分开

哈希表的设计

哈希表有一个初始桶区域，假设17

如何挂数据？

求出数据哈希值，%17（因为大小为 17），放入桶中

桶中数据通过单链表连接

因为 hash 函数具有均匀性，所以桶中数据一定均匀增长

为什么 hash 表的查询和修改时间复杂度是 O(1)？

因为 hash 表具有扩容操作

当一个单链表到达一定长度（假设 7）因为 hash 函数均匀增长，所以其他链表也几乎逼近7。直接翻倍扩容，hash 表中每一个数据重新%计算，所有链表长度几乎减为一半。

布隆过滤器

利用哈希函数的性质
每一条数据提取特征
加入描黑库

使用字节数组存储，数据通过三个哈希函数计算后%（数组长度 * 8），三个值对应的位描黑

查询的时候只要有一个没有描黑说明未被标记黑名单

所以布隆过滤器有可能拦截非黑名单数据

布隆过滤器开多大和 1. 样本量 2. 失误率有关系

样本量固定，数组长度越大失误率越小

三个重要公式

假设数据量为 n，预期的失误率为 p（布隆过滤器大小和每个样本的大小无关）
根据 n 和 p，算出 Boolm Filter 一共需要多少个 bit 位，向上取整记为 m $$ m=-\frac{n\times\ln p}{(\ln{2})^2} $$
根据 m 和 n，算出 Boolm Filter 需要多少个哈希函数，向上取整，记为 k $$ K=\ln{2}\times\frac{m}{n}=0.7\times\frac{m}{n} $$ 插一句，上哪找这么多哈希函数？
只要有两个基础哈希函数即可向下推导几乎独立
```
1 * f1() + f2()
2 * f1() + f2()
3 * f1() + f2()
... ...
K * f1() + f2()
```
1
2
3
4
5
根据修正公式，算出真实的失误率 p_true $$ \Big(1-e^{-\frac{nk}{m}}\Big)^k $$

一致性哈希

分布式存储结构最常见的结构

哈希域变成环的设计
虚拟节点技术

35、资源限制类题目

布隆过滤器用于集合的建立与查询，并可以节省大量空间
一致性哈希解决数据服务器的负载管理问题
利用并查集结构做岛问题的并行计算
哈希函数可以把数据按照种类均匀分流
位图解决某一范围上数字的出现情况，并可以节省大量空间
利用分段统计思想、并进一步节省大量空间
利用堆、外排序来做多个处理单元的结果合并

题目一哈希函数

32 位无符号整数的范围是 0～4294967295，现有一个正好包含40亿个无符号整数的文件，可以使用最多1GB的内存，怎么找到出现次数最多的数？

40亿 * 4(int size) = 160亿 Byte

思路：因为数据量太大，所以可以利用了哈希函数的均匀性按照种类均匀分流

计算出1GB可以存多少数字，将整数文件分为多个（每个数据量都在1GB以内）

分法：文件中的数字求哈希值%文件个数，就能保证相同数字在一个文件

题目二位图

32 位无符号整数的范围是 0～4294967295，现有一个正好包含40亿个无符号整数的文件，可以使用最多1GB的内存，怎么找到未出现过的数？

【进阶】内存限制为 10MB，怎么找到一个没出现过的数

【进阶2】假设只能申请有限几个变量，怎么找到一个没出现过的数

一

1 GB = 1073741824 B = 8589934592 bit

位图：利用比特数组有值为 1，无值为 0

二

利用位图分区

三

int L, mid , R;

int count;

二分为 0～2^31 和 2^31~2^32

统计两边次数看哪边不够 2^31

最后出现0次的那个就是没出现的数

题目三分段统计

有一个包含 100 亿个 URL 的大文件，假设每个 URL 占用 64B，请找出其中重复的 URL

【补充】某搜索公司一天的用户搜索词汇是海量的（百亿数据量）

请设计一种求出每天热门 Top100 词汇的可行办法

如果允许有失误可以采用布隆过滤器
如果不允许有失误可以采取哈希来哈希去的方法进行分流

题目四位图 + 分段统计

32 位无符号整数的范围是 0~4294967295

现有 40 亿个无符号整数，最多可使用 1GB 的内存，找出所有出现了两次的数。

1 GB = 1073741824 B = 8589934592 bit

可以用两位表示一个数，40 亿个数字需要 512 MB

第一遍遍历发现是后一半范围则不进行统计

题目五

32 位无符号整数的范围是 0~4294967295

现有 40 亿个无符号整数，最多可使用 10MB 的内存，怎么找到这40亿个整数的中位数？

申请数组按范围统计（某一范围出现多少个），统计范围 20亿时的数字

// 申请数组
long[] arr = new arr[512];
// 每一份统计的范围区间为 2^32/512
int scope = 2^32/512;
int num = ...; // 文件中读取数字
arr[num/scope] += 1;
// 最终得到中间值范围后 缩小每一份scope 继续统计 直到找到中间值

题目六利用堆

32 位无符号整数的范围是 0~4294967295

有一个 10G 大小的文件，每一行都装着这种类型的数字，

整个文件是无序的，给你 5G 内存空间，

请输出一个 10G 大小的文件，就是原文件所有数字排序的结果

大根堆
利用最大空间筛选出前面的数字，多次筛选，遇到比最大的小的则抛弃最大放入最小到空间

# 算法数据结构体系

# 1、复杂度、对数器、二分法

# 二分法

# 4、基础数据结构

# 单向链表

# 双向链表

# 链表简单问题

# 队列和栈

# 递归

# 5、归并排序

# 题目

# 7、堆和排序

# 比较器

# 堆结构

# 大根堆

# 加强堆

# 最大线段重合问题（堆实现）

# 手动改写堆题目练习

# 13、贪心算法

# 16、并查集及其相关题目

# 547、省份数量

# 岛问题

# 18、经典递归

# 汉诺塔

# 打印子序列

# 所有字符串的组合

# 逆序栈

# 32、IndexTree & AC 自动机

# IndexTree

# AC 自动机

# 34、与 hash 函数有关的结构

# 哈希表的设计

# 布隆过滤器

# 三个重要公式

# 一致性哈希

# 35、资源限制类题目

# 题目一 哈希函数

# 题目二 位图

# 题目三 分段统计

# 题目四 位图 + 分段统计

# 题目五

# 题目六 利用堆

算法数据结构体系

1、复杂度、对数器、二分法

二分法

4、基础数据结构

单向链表

双向链表

链表简单问题

队列和栈

递归

5、归并排序

题目

7、堆和排序

比较器

堆结构

大根堆

加强堆

最大线段重合问题（堆实现）

手动改写堆题目练习

13、贪心算法

16、并查集及其相关题目

547、省份数量

岛问题

18、经典递归

汉诺塔

打印子序列

所有字符串的组合

逆序栈

32、IndexTree & AC 自动机

IndexTree

AC 自动机

34、与 hash 函数有关的结构

哈希表的设计

布隆过滤器

三个重要公式

一致性哈希

35、资源限制类题目

题目一哈希函数

题目二位图

题目三分段统计

题目四位图 + 分段统计

题目五

题目六利用堆