训练营二期

打表法

1
2
3
4
5
6
7
8
9
打表法:
1)问题如果返回值不太多,可以用hardcode的方式列出,作为程序的一部分
2)一个大问题解决时底层频繁使用规模不大的小问题的解,如果小问题的返回值满足条件1),可以把小问题的解列成一张表,作为程序的一部分
3)打表找规律

打表找规律:
1)某个题,输入参数类型简单,并且只有一个实际参数
2)要求的返回值类型也简单,并且只有一个
3)用暴力方法,把输入参数对应的返回值,打印出来看看,进而优化code
1
2
3
4
5
6
题目一:
小虎去买苹果,商店只提供两种类型的塑料袋,每种类型都有任意数量。
1)能装下6个苹果的袋子
2)能装下8个苹果的袋子
小虎可以自由使用两种袋子来装苹果,但是小虎有强迫症,他要求自己使用的袋子数量必须最少,且使用的每个袋子必须装满。
给定一个正整数N,返回至少使用多少袋子。如果N无法让使用的每个袋子必须装满,返回-1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//打表找规律
public static int minBags(int apple) {
if (apple < 0) {
return -1;
}
int bag6 = -1;
int bag8 = apple / 8;
int rest = apple - 8 * bag8;
while (bag8 >= 0 && rest < 24) {
int restUse6 = minBagBase6(rest);
if (restUse6 != -1) {
bag6 = restUse6;
break;
}
rest = apple - 8 * (--bag8);
}
return bag6 == -1 ? -1 : bag6 + bag8;
}

// 如果剩余苹果rest可以被装6个苹果的袋子搞定,返回袋子数量
// 不能搞定返回-1
public static int minBagBase6(int rest) {
return rest % 6 == 0 ? (rest / 6) : -1;
}

public static void main(String[] args) {
for(int apple = 1; apple < 100;apple++) {
System.out.println(apple + " : "+ minBags(apple));
}
}
1
2
3
4
5
6
7
8
9
10
11
//整合规律
public static int minBagAwesome(int apple) {
if ((apple & 1) != 0) { // 如果是奇数,返回-1
return -1;
}
if (apple < 18) {
return apple == 0 ? 0 : (apple == 6 || apple == 8) ? 1
: (apple == 12 || apple == 14 || apple == 16) ? 2 : -1;
}
return (apple - 18) / 8 + 3;
}
1
2
3
4
5
6
7
8
题目二:
给定一个正整数N,表示有N份青草统一堆放在仓库里
有一只牛和一只羊,牛先吃,羊后吃,它俩轮流吃草
不管是牛还是羊,每一轮能吃的草量必须是:
1,4,16,64…(4的某次方)
谁最先把草吃完,谁获胜
假设牛和羊都绝顶聪明,都想赢,都会做出理性的决定
根据唯一的参数N,返回谁会赢
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// n份青草放在一堆
// 先手后手都绝顶聪明
// string "先手" "后手"
//暴力递归测试打表规律
public static String winner1(int n) {
// 0 1 2 3 4
// 后 先 后 先 先
if (n < 5) { // base case
return (n == 0 || n == 2) ? "后手" : "先手";
}
// n >= 5 时
int base = 1; // 当前先手决定吃的草数
// 当前是先手在选
while (base <= n) {
// 当前一共n份草,先手吃掉的是base份,n - base 是留给后手的草
// 母过程 先手 在子过程里是 后手
if (winner1(n - base).equals("后手")) {
return "先手";
}
if (base > n / 4) { // 防止base*4之后溢出
break;
}
base *= 4;
}
return "后手";
}

public static void main(String[] args) {
for (int i = 0; i <= 50; i++) {
System.out.println(i + " : " + winner1(i));
}
}
1
2
3
4
5
6
7
8
//打表规律
public static String winner2(int n) {
if (n % 5 == 0 || n % 5 == 2) {
return "后手";
} else {
return "先手";
}
}
1
2
3
4
5
6
7
8
题目三:
定义一种数:可以表示成若干(数量>1)连续正数和的数
比如:
5 = 2+3,5就是这样的数
12 = 3+4+5,12就是这样的数
1不是这样的数,因为要求数量大于1个、连续正数和
2 = 1 + 1,2也不是,因为等号右边不是连续正数
给定一个参数N,返回是不是可以表示成若干连续正数和的数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//打表
public static boolean isMSum1(int num) {
for (int i = 1; i <= num; i++) {
int sum = i;
for (int j = i + 1; j <= num; j++) {
if (sum + j > num) {
break;
}
if (sum + j == num) {
return true;
}
sum += j;
}
}
return false;
}

public static void main(String[] args) {
for (int num = 1; num < 200; num++) {
System.out.println(num + " : " + isMSum1(num));
}
System.out.println("test begin");
for (int num = 1; num < 5000; num++) {
if (isMSum1(num) != isMSum2(num)) {
System.out.println("Oops!");
}
}
System.out.println("test end");
}
1
2
3
4
5
6
7
8
//打表规律 1 2 4 8 16,2的次幂是false
//(num & (num - 1)) == 0; 表示这个数是2的次幂 ,否则不是
public static boolean isMSum2(int num) {
if (num < 3) {
return false;
}
return (num & (num - 1)) != 0;
}

矩阵技巧

1
2
3
4
5
矩阵处理技巧
1)zigzag打印矩阵
2)转圈打印矩阵
3)原地旋转正方形矩阵
核心技巧:找到coding上的宏观调度
1
2
3
4
5
6
7
8
9
10
11
zigzag打印矩阵:
|a b c d|
|e f g h|
|i j k l|
要求输出顺序是: abeijfcdgklh

思想:
两个点A、B都是从坐标[0,0]上出发
A每次往右走,走到不能往右了,就往下走
B每次往下走,走到不能往下了,就往右走
这样A和B始终能连成一条贯穿矩阵内容的斜线,输出处于斜线上的内容即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public static void printMatrixZigZag(int[][] matrix) {
//A坐标点
int tR = 0;
int tC = 0;
//B坐标点
int dR = 0;
int dC = 0;
int endR = matrix.length - 1;
int endC = matrix[0].length - 1;
//输出方向 从下到上,还是从上到下
boolean fromUp = false;
while (tR != endR + 1) {
printLevel(matrix, tR, tC, dR, dC, fromUp);
tR = tC == endC ? tR + 1 : tR;
tC = tC == endC ? tC : tC + 1;
dC = dR == endR ? dC + 1 : dC;
dR = dR == endR ? dR : dR + 1;
fromUp = !fromUp;
}
System.out.println();
}

public static void printLevel(int[][] m, int tR, int tC, int dR, int dC,
boolean f) {
if (f) {
while (tR != dR + 1) {
System.out.print(m[tR++][tC--] + " ");
}
} else {
while (dR != tR - 1) {
System.out.print(m[dR--][dC++] + " ");
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
转圈打印矩阵:
|a b c d|
|e f g h|
|i j k l|
要求输出顺序是: abcdhlkjiefg

思想:
分解矩阵,每次输出一个框: abcdhlkjie fg
以a,l点的(x,y)坐标为点:
从a点出发,输出横列,它的a.y++,直到a.y + 1 = l.y停下
从d点出发,输出竖列,它的a.x++,直到a.x + 1 = l.x停下
从l点出发,输出横列,它的l.y--,直到l.y - 1 = a.x停下
从i点出发,输出竖列,它的l.x--,直到l.x - 1 = a.y停下
切割成四部分,先输出外围框,然后a和l分别向左下,右上移动,再次输出框
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public static void spiralOrderPrint(int[][] matrix) {
int tR = 0;
int tC = 0;
int dR = matrix.length - 1;
int dC = matrix[0].length - 1;
while (tR <= dR && tC <= dC) {
printEdge(matrix, tR++, tC++, dR--, dC--);
}
}

public static void printEdge(int[][] m, int tR, int tC, int dR, int dC) {
//兼容a点和l点处于同一条直线的情况
if (tR == dR) {
for (int i = tC; i <= dC; i++) {
System.out.print(m[tR][i] + " ");
}
} else if (tC == dC) {
for (int i = tR; i <= dR; i++) {
System.out.print(m[i][tC] + " ");
}
} else {
int curC = tC;
int curR = tR;
while (curC != dC) {
System.out.print(m[tR][curC] + " ");
curC++;
}
while (curR != dR) {
System.out.print(m[curR][dC] + " ");
curR++;
}
while (curC != tC) {
System.out.print(m[dR][curC] + " ");
curC--;
}
while (curR != tR) {
System.out.print(m[curR][tC] + " ");
curR--;
}
}
}
1
2
3
4
5
6
7
8
原地旋转正方形矩阵
|a b c| |i e a|
|e f g| 向左旋转90度 -> |j f b|
|i j k| |k g c|

思想:
取四个点坐标 a、c、k、i,分组,a向右移动的数据,对应变化到c向下移动的数据,依次等于每次每组都是在互相交换数据。
a -> c c->k k-i> i->a,然后各自移动,重复操作,外圈交换完就交换内圈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void rotate(int[][] matrix) {
int a = 0;
int b = 0;
int c = matrix.length - 1;
int d = matrix[0].length - 1;
while (a < c) {
rotateEdge(matrix, a++, b++, c--, d--);
}
}

public static void rotateEdge(int[][] m, int a, int b, int c, int d) {
int tmp = 0;
for (int i = 0; i < d - b; i++) {
tmp = m[a][b + i];
m[a][b + i] = m[c - i][b];
m[c - i][b] = m[c][d - i];
m[c][d - i] = m[a + i][d];
m[a + i][d] = tmp;
}
}

数组累加和

1
2
3
4
题目一:
给定一个正整数组成的无序数组arr,给定一个正整数值K
找到arr的所有子数组里,哪个子数组的累加和等于K,并且是长度最大的
返回其长度
1
2
3
思路:
滑动窗口 [L..R],定义一个累加值,划到等于K,则记录窗口长度
并且L/R继续滑动右移,大于K时,L右移,累加和减掉arr[L]值,R接着向右划,周而复始,R越界,则窗口内无结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public static int getMaxLength(int[] arr, int K) {
if (arr == null || arr.length == 0 || K <= 0) {
return 0;
}
int L = 0;
int R = 0;
int sum = arr[0];
int len = 0;
while (R < arr.length) {
//窗口内的值相等则记录长度,并且L向右滑动,并且sum要减去arr[L]值
if (sum == K) {
len = Math.max(len, R - L + 1);
sum -= arr[L++];
} else if (sum < K) {
R++;
//先自增判断是否越界,越界则break
if (R == arr.length) {
break;
}
sum += arr[R];
} else {
//如果大于K,L也向右滑动,并且sum要减去arr[L]值
sum -= arr[L++];
}
}
return len;
}
1
2
3
4
5
题目二:
给定一个整数组成的无序数组arr,值可能正、可能负、可能0
给定一个整数值K
找到arr的所有子数组里,哪个子数组的累加和等于K,并且是长度最大的
返回其长度
1
2
3
4
5
6
7
8
思想:
用Map存储最早出现的累加和信息<sum,index>,sum是从Index = 0累加到当前index的值
依次遍历数组,当前遍历的i的sum - K = V,V去Map中寻找是否有值
若有值,V对应最早出现的[index + 1,i],这段长度就是以i结尾,最长的子数组累加和
注意:map中需要实现补充<0,-1>的记录,因为在还没开始时数组累加和就应该等于0
否则将会出现以下反例:
[3,-3,7] K = 7, 当i = 2时, sum = 7, V = sum - K = 0,映射Map<0,1>的数据,这时length = i - V.value = 1
若最开始Map中就已存在<0,-1>,则有length = i - (-1) = 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static int maxLength(int[] arr, int k) {
if (arr == null || arr.length == 0) {
return 0;
}
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, -1); // important
int len = 0;
int sum = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
//判断Map是否存在出现累加和的值
if (map.containsKey(sum - k)) {
len = Math.max(i - map.get(sum - k), len);
}
//记录第一次出现当前累加和的值的index
if (!map.containsKey(sum)) {
map.put(sum, i);
}
}
return len;
}
1
2
3
4
5
6
7
题目三:
有一个包含正数、负数、零的整数数组,要求得到同时包含相等数量的1、2的最长子数组长度
例子:[1,3,-2,2,4,1,2]

思路:
遍历,遇到1就把值变成1,遇到2把值变成-1,遇到其他值,都变成0 --> [1,0,0,-1,0,1,-1]
转换成了数组累加和的问题,最长子串中累加和等于0的问题。
1
2
3
4
5
题目四:
给定一个整数组成的无序数组arr,值可能正、可能负、可能0
给定一个整数值K
找到arr的所有子数组里,哪个子数组的累加和<=K,并且是长度最大的
返回其长度
1
2
3
4
5
6
7
8
9
10
11
思路:
用两个数组来记录信息,minSum数组存储以当前index为L和R,R向右边扩的最小累加和
minSumRIndex存储以index为L,R扩到的最小累加和下标
如例子(arr从右往左遍历):
arr = [3,-2,0,7,-3,2]
minSum = [1,-2,0,4,-3,2]
minSumRIndex = [2,2,2,4,4,5]

以i = 0开始,sum += [0,2],然后看看sum是否小于K,小于则继续扩 sum+= [3,4],扩到不能扩为止
若出现不能扩,这里有个优化点:sum = [0,R]的累加值,则[1,R]的sum1 = sum - [0,0]
接着以 i = 1开始,看看[R+1,..]能否被扩进去,若不能,则跳过i = 1的累加
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//O(N)
public static int maxLengthAwesome(int[] arr, int k) {
if (arr == null || arr.length == 0) {
return 0;
}
int[] minSums = new int[arr.length];
int[] minSumRIndex = new int[arr.length];
//末尾的肯定是自己,没办法扩
minSums[arr.length - 1] = arr[arr.length - 1];
minSumRIndex[arr.length - 1] = arr.length - 1;
//从右往左计算
for (int i = arr.length - 2; i >= 0; i--) {
if (minSums[i + 1] <= 0) {
minSums[i] = arr[i] + minSums[i + 1];
minSumRIndex[i] = minSumRIndex[i + 1];
} else {
minSums[i] = arr[i];
minSumRIndex[i] = i;
}
}
//扩到第一个超的index
int end = 0;
//已经扩出来整体累加和的值
int sum = 0;
//全局最大长度
int res = 0;
// i是窗口的最左的位置,end扩出来的最右有效块儿的最后一个位置的,再下一个位置
// end也是下一块儿的开始位置
// 窗口:[i~end)
for (int i = 0; i < arr.length; i++) {
// while循环结束之后:
// 1) 如果以i开头的情况下,累加和<=k的最长子数组是arr[i..end-1],看看这个子数组长度能不能更新res;
// 2) 如果以i开头的情况下,累加和<=k的最长子数组比arr[i..end-1]短,更新还是不更新res都不会影响最终结果;
while (end < arr.length && sum + minSums[end] <= k) {
sum += minSums[end];
end = minSumRIndex[end] + 1;
}
res = Math.max(res, end - i);
if (end > i) { // 窗口内还有数 [i~end) [4,4)
sum -= arr[i];
} else { // 窗口内已经没有数了,说明从i开头的所有子数组累加和都不可能<=k
end = i + 1;
}
}
return res;
}

哈希函数

1
2
3
4
5
6
1)输入参数data,假设是in类型,特征:可能性无穷大,比如str类型的参数
2)输出参数类型out,特征:可能性可以很大,但一定是有穷尽的
3)哈希函数没有任何随机的机制,固定的输入一定是固定的输出
4)输入无穷多但输出值有限,所以不同输入也可能输出相同(哈希碰撞)
5)再相似的不同输入,得到的输出值,会几乎均匀的分布在out域上
重点:第5条!
1
2
3
4
5
6
假设链表长度大于1需要扩容,初始化数组大小为1,等于每次插入hashMap都需要扩容
假设最简单的扩容是:
1->2->4->8->...->N 那么样本量N时,它的扩容次数是logN
每次扩容的时候,扩容的数据量是当时的数量被,不是最后的N来估计,扩容总代价为:
假设每次扩容都需要遍历整个数据大小,则:1+2+4+8+...+N/4+N/2,等比数列收敛于O(N)
加N个数的总代价为O(N),均摊下来为O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
题目:
32位无符号整数的范围是0~4,294,967,295,
现在有一个正好包含40亿个无符号整数的文件,
可以使用最多1GB的内存,怎么找到出现次数最多的数?

分析:
最简单的是通过HashMap<整数,出现次数>进行词频统计,但是把40亿个整数放进HashMap一定超过1G内存
不妨假设忽略hashMap自身属性所占用的字节量,一个int占4字节,一对<key,value> 8个字节
如果40亿个整数都不同,那么内存将有40亿 * 8 = 320亿字节,而一个1G=10亿字节多,必然超

思想:
将40亿个整数进行hash % 40放入文件中,将40亿数据打散到40个文件中,根据哈希函数的特性,会几乎均匀的分布
而且同一个数字计算相同hash,所以必定在同一个文件中,在这种情况下,1G内存计算每个文件的Top并比较
即使40亿个整数全部落在同一个文件中,也可以照样进行HashMap词频统计,因为都是同一个数字的话,必定不会超1G

布隆过滤器

布隆过滤器图解

1
2
3
1)利用哈希函数的性质
2)每一条数据提取特征
3)加入描黑库
1
2
3
4
1,假设数据量为n,预期的失误率为p(布隆过滤器大小和每个样本的大小无关)
2,根据n和p,算出Bloom Filter一共需要多少个bit位,向上取整,记为m
3,根据m和n,算出Bloom Filter需要多少个哈希函数,向上取整,记为k
4,根据修正公式,算出真实的失误率p_true

algorithm

1
2
3
4
5
6
7
8
问题:如何找出多个Hash函数把值打散在多个bit中?

思想:
可以找两个Hash函数,分别是F()和G(),对两个Hash函数算出来的值进行加工即可得出多个互相独立的Hash函数
第一个Hash函数 = F() + 1 * G()
第二个Hash函数 = F() + 2 * G()
第三个Hash函数 = F() + 3 * G()
...

一致性Hash

一致性Hash图解

1
2
3
分布式存储结构最常见的结构
1)哈希域变成环的设计
2)虚拟节点技术

并行算法

1
2
3
4
5
6
7
岛问题:
一个只有0和1两种数字的二维矩阵中,上下左右能连成一片的1,算一个岛,返回矩阵中,一共有几个岛
如:
|0 1 0 1 1 1|
|1 1 0 0 1 0|
|1 0 0 0 1 1|
|1 1 1 0 0 0| 答案:两个岛
1
2
思想:
写一个感染函数,自身是1的点,改成2,递归将上下左右相邻是1的点都感染成2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public static int countIslands1(int[][] m) {
if (m == null || m[0] == null) {
return 0;
}
int N = m.length;
int M = m[0].length;
int res = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
//找到一个为1的,则岛数量++,感染岛相连的片区
if (m[i][j] == 1) {
res++;
infect(m, i, j, N, M);
}
}
}
return res;
}

public static void infect(int[][] m, int i, int j, int N, int M) {
if (i < 0 || i >= N || j < 0 || j >= M || m[i][j] != 1) {
return;
}
m[i][j] = 2;
infect(m, i + 1, j, N, M);
infect(m, i - 1, j, N, M);
infect(m, i, j + 1, N, M);
infect(m, i, j - 1, N, M);
}
1
2
3
4
5
6
7
8
并行算法:
岛问题数据量庞大时,上述解法是单线程解法,可以将岛进行切割,划分各个区域,每个区域统计岛的数量
由于划分区域算出来的岛数势必大于等于真实解,因为区域切割会将原本属于同一座岛屿的切割成两座。
|1 1 1 1 1 1|
|1 0 0 0 1 0|
|1 0 0 0 1 1|
|1 1 1 1 1 0|
如果将上图例子切割成两片区域进行计算,最终结果需要进行,可以通过并查集。
1
2
3
4
5
6
7
8
思想:
切割成两片区域并行计算,计算的时候记录和切割线附近的点,如坐标A[2,0]、B[2,3]、C[3,0]、D[3,3]
最后通过并查集合并A点和B点(res--),然后再判断C点和D点是否是一个并查集
由于A和C是处于同一个并查集,B和D也处于同一个并查集,而且A和B并查集经过合并,所以C和D本身就处于同一个并查集
左区域res = 1, 右区域res = 1, sum = 2 - mergeA&B = 1
最终岛屿数:1

扩展:可以不止切割成两片区域,可以切割成多块,最后使用并查集进行合并。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
public static class UnionFindSet<V> {
// a -> a 生成的点
public HashMap<V, Element<V>> elementMap;
public HashMap<Element<V>, Element<V>> fatherMap;
// sizeMap中的key,每一个key都一定是集合的头节点(代表节点)
public HashMap<Element<V>, Integer> sizeMap;

public UnionFindSet(List<V> list) {
elementMap = new HashMap<>();
fatherMap = new HashMap<>();
sizeMap = new HashMap<>();
for (V value : list) {
Element<V> element = new Element<V>(value);
elementMap.put(value, element);
fatherMap.put(element, element);
sizeMap.put(element, 1);
}
}

// 从输入参数element出发,往上一直找,找到不能再往上的头节点,返回
private Element<V> findHead(Element<V> element) {
// 把往上找的过程中,沿途的点都记录在path里
Stack<Element<V>> path = new Stack<>();
while (element != fatherMap.get(element)) {
path.push(element);
element = fatherMap.get(element);
}
while (!path.isEmpty()) {
fatherMap.put(path.pop(), element);
}
return element;
}

public boolean isSameSet(V a, V b) {
if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
return findHead(elementMap.get(a)) == findHead(elementMap.get(b));
}
return false;
}

public void union(V a, V b) {
if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
Element<V> aF = findHead(elementMap.get(a));
Element<V> bF = findHead(elementMap.get(b));
if (aF != bF) {
Element<V> big = sizeMap.get(aF) >= sizeMap.get(bF) ? aF : bF;
Element<V> small = big == aF ? bF : aF;
fatherMap.put(small, big);
sizeMap.put(big, sizeMap.get(aF) + sizeMap.get(bF));
sizeMap.remove(small);
}
}
}

public int getSetNum() {
return sizeMap.size();
}

}

public static int countIslands2(int[][] m) {
List<String> list = new ArrayList<>();
for (int row = 0; row < m.length; row++) {
for (int col = 0; col < m[0].length; col++) {
if (m[row][col] == 1) {
String position = String.valueOf(row) + "_" + String.valueOf(col);
list.add(position);
}
}
}
UnionFindSet<String> unionSet = new UnionFindSet<>(list);
for (int row = 0; row < m.length; row++) {
for (int col = 0; col < m[0].length; col++) {
if (m[row][col] == 1) {
// row,col 5, 3 -> 5_3
String position = String.valueOf(row) + "_" + String.valueOf(col);
if (row - 1 >= 0 && m[row - 1][col] == 1) {
String up = String.valueOf(row - 1) + "_" + String.valueOf(col);
unionSet.union(up, position);
}
if (col - 1 >= 0 && m[row][col - 1] == 1) {
String left = String.valueOf(row) + "_" + String.valueOf(col - 1);
unionSet.union(left, position);
}
}
}
}
return unionSet.getSetNum();
}

资源限制

1
2
3
4
5
6
7
1)布隆过滤器用于集合的建立与查询,并可以节省大量空间(已讲)
2)一致性哈希解决数据服务器的负载管理问题(已讲)
3)利用并查集结构做岛问题的并行计算(已讲)
4)哈希函数可以把数据按照种类均匀分流
5)位图解决某一范围上数字的出现情况,并可以节省大量空间
6)利用分段统计思想、并进一步节省大量空间
7)利用堆、外排序来做多个处理单元的结果合并
1
2
3
4
5
6
7
8
9
10
11
题目一:
32位无符号整数的范围是0~4,294,967,295,
现在有一个正好包含40亿个无符号整数的文件,
所以在整个范围中必然存在没出现过的数。
可以使用最多1GB的内存,怎么找到所有未出现过的数?

思想:
int占4字节,弄成二维数组的话,一个下标存储一个值,没出现的数据上存储的就是0,出现过就存储1
最终内存变成4 * 40亿 = 160亿字节,而1GB内存=10亿多字节
若把这些数据放在bit中,原本4字节(32bit)存储一个数,现在一个bit标识处没出现过,等于缩小了32倍
也就是 160亿/32 ≈ 500MB
1
2
3
4
5
6
7
8
9
进阶:
题目一基础上,内存限制为 3KB,但是只用找到一个没出现过的数即可

思想:
通过3KB/4 算出他最多能存储的数组长度=750,取小于该长度临近的2的某次方的数:512
根据无符号长度大小 2^32 / 512 = 8388609,等于把整个无符号整数范围划分成512份
取40亿数据进行区域划分,只需要统计40亿每个数字属于哪个区域(512份中的一份),count++
因为只有40亿的数据,最终必定有一个区域count是小于 8388609,该区域必有未出现的数
根据区域的范围L..R继续划分,直到数据量能够让3KB大小进行bit词频统计
1
2
3
4
5
进阶:
题目一基础上,内存限制为五个变量,但是只用找到一个没出现过的数即可

思想:
二分L、M、R,一直二分统计区域出现的词频,重复二分未占满的区域,最多二分32次
1
2
3
4
5
6
7
8
9
题目二:
32位无符号整数的范围是0~4294967295,
现在有40亿个无符号整数,
可以使用最多1GB的内存,
找出所有出现了两次的数。

思想:
基于题目一的思想,用两个bit表示一个数出现的频率,出现1次则[01]、2次则[10]、3次及以上则[11]
也就是用了500MB * 2 = 1G内存,把所有bit是[10]的取出来则是答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
题目三:
有一个包含100亿个URL的大文件,假设每个URL占用64B,
请找出其中所有重复的URL
【补充】
某搜索公司一天的用户搜索词汇是海量的(百亿数据量),
请设计一种求出每天热门Top100词汇的可行办法

思想:
要确认有多少台机器可用,可以有一台皇帝机通过hash函数%机器数量,把url分散到各个机器上
如果一个机器还不够处理,则用第二个hash函数进行分文件处理。
第一次分机器,第二次分文件,机器怕的是种类过多导致爆内存,而不是重复数据量大爆

补充:
分机器、分文件,每个文件的Top100进行PK,可以根据外排,每个文件的Top100中的Top1进行比较
也可以用二维堆进行比较,假设三个文件三个堆,再取每个堆的堆顶再构建成一个堆
1
2
3
4
5
6
7
题目四:
32位无符号整数的范围是0~4294967295,现在有40亿个无符号整数
可以使用最多3K的内存,怎么找到这40亿个整数的中位数?

思路:
可以基于题目一的进阶思路,切割成512份,把前面的count累加,能够定位到第20亿小的值处于其中的某一份中
如0~16份的count加起来等于19亿,第17份有4亿,那么,第20亿小的值,一定在第17份中的第1亿小的值,分而治之
1
2
3
4
5
6
7
8
9
10
11
题目五:
32位无符号整数的范围是0~4294967295,
有一个10G大小的文件,每一行都装着这种类型的数字,
整个文件是无序的,给你5G的内存空间,
请你输出一个10G大小的文件,就是原文件所有数字排序的结果

思路:
用一个Map<Integer,Index>和一个小根堆<val,Count>实现,小根堆中是有限个数K,Map的size和K相同
遍历一遍,大于堆顶的元素则放入堆中替换堆顶,重排序,小于堆顶的忽略,等于堆顶的Count++
这样一轮之后能够得到K个Integer的排序,放入文件中,下次遍历时忽略大于等于上次堆顶的数值
一个Map的KeyValue占8个字节,小根堆一个节点也占8个字节,那么K的大小取舍等于5G/16字节

搜索二叉树

1
2
3
4
5
搜索二叉树:左树的所有节点都比当前节点小,右树的所有节点都比当前节点大

搜索二叉树一定要说明以什么标准来排序
经典的搜索二叉树,树上没有重复的用来排序的key值
如果有重复节点的需求,可以在一个节点内部增加数据项
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
搜索二叉树查询key(查询某个key存在还是不存在)
1)如果当前节点的value==key,返回true
2)如果当前节点的value<key,当前节点向左移动
3)如果当前节点的value>key,当前节点向右移动
4)如果当前节点变成null,返回false

搜索二叉树插入新的key
和查询过程一样,但当前节点滑到空的时候,就插入在这里

搜索二叉树删除key
0)先找到key所在的节点
1)如果该节点没有左孩子、没有右孩子,直接删除即可
2)如果该节点有左孩子、没有右孩子,直接用左孩子顶替该节点
3)如果该节点没有左孩子、有右孩子,直接用右孩子顶替该节点
4)如果该节点有左孩子、有右孩子,用该节点后继节点(右树上的最左节点)顶替该节点
1
2
3
4
搜索二叉树特别不讲究
1)基础的搜索二叉树,添加、删除时候不照顾平衡性
2)数据状况很差时,性能就很差
给搜索二叉树引入两个动作:左旋、右旋
1
2
3
4
5
6
7
8
9
10
11
12
//遍历查询
public Node search(int element) {
Node node = root;
while (node != null && node.value != null && node.value != element) {
if (element < node.value) {
node = node.left;
} else {
node = node.right;
}
}
return node;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//插入
public Node insert(int element) {
if (root == null) {
root = createNode(element, null, null, null);
size++;
return root;
}

Node insertParentNode = null;
Node searchTempNode = root;
//查询新节点应该挂载在哪个父节点中
while (searchTempNode != null && searchTempNode.value != null) {
insertParentNode = searchTempNode;
if (element < searchTempNode.value) {
searchTempNode = searchTempNode.left;
} else {
searchTempNode = searchTempNode.right;
}
}

//挂节点
Node newNode = createNode(element, insertParentNode, null, null);
if (insertParentNode.value > newNode.value) {
insertParentNode.left = newNode;
} else {
insertParentNode.right = newNode;
}

size++;
return newNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//删除节点
protected Node delete(Node deleteNode) {
if (deleteNode != null) {
Node nodeToReturn = null;
if (deleteNode != null) {
if (deleteNode.left == null) {
// 如果该节点没有左孩子、有右孩子,直接用右孩子顶替该节点
// transplant(a,b) b去替换a的环境,a断连掉,把b返回:(返回受影响的节点)
nodeToReturn = transplant(deleteNode, deleteNode.right);
} else if (deleteNode.right == null) {
//如果该节点有左孩子、没有右孩子,直接用左孩子顶替该节点
nodeToReturn = transplant(deleteNode, deleteNode.left);
} else {
//如果该节点有左孩子、有右孩子,查找该节点的后继节点(右树上的最左节点)
Node successorNode = getMinimum(deleteNode.right);
//如果后继节点的父节点不是删除的节点,则用后继节点顶替删除节点的位置
if (successorNode.parent != deleteNode) {
//把后继节点的右子树驳接到原父节点上
transplant(successorNode, successorNode.right);
successorNode.right = deleteNode.right;
successorNode.right.parent = successorNode;
}
//把后继节点驳接到到删除节点的父节点下
transplant(deleteNode, successorNode);
successorNode.left = deleteNode.left;
successorNode.left.parent = successorNode;
nodeToReturn = successorNode;
}
size--;
}
return nodeToReturn;
}
return null;
}

AVL树

1
2
3
4
5
6
7
8
9
AVL树:平衡二叉树
1)最严格的平衡性,任何节点左树高度和右树高度差不超过1
2)往上沿途检查每个节点时,都去检查四种违规情况:LL、RR、LR、RL
3)不同情况虽然看起来复杂,但是核心点是:
LL(做一次右旋)、RR(做一次左旋)
LR和RL(利用旋转让底层那个上到顶部)

查询时间复杂度O(logN)
单次增/删/旋转的时间复杂度都是O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
      1
2 3
4 5
6

上图数字代表添加顺序,当没有添加节点6时,它是平衡的,添加节点6时,节点1的左树高度是3,右树高度是1,所以不平衡
节点1是因为 左边(节点2)的左侧(节点4)不平衡的,这种违规情况被称作:LL

也就是说,四种违规情况:
LL:来源于左树+左树的左侧
RR:来源于右树+右树的右侧
LR:来源于左树+左树的右侧
RL:来源于右树+右树的左侧
1
2
3
4
5
6
7
8
9
10
11
12
LL和RR的违规情况很好处理,只要对不平衡的节点(X)进行一次旋转即可
LL(做一次右旋)、RR(做一次左旋)

而LR和RL需要做两次旋转,但是核心是相同的:
LR:找到左树的右侧节点(X.L.R),利用旋转让这个节点到达不平衡节点(X)的位置即可
RL:找到右树的左侧节点(X.R.L),利用旋转让这个节点到达不平衡节点(X)的位置即可

1
2 3
4 5 6
7 8
在这种情况下删除节点6,会造成X节点个数:X.L=3,X.R = 1,满足同时违规LL和LR型,只能使用LL型方案解决!!!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//四种违规场景判断:

//获取X节点的L和R高度
int leftHeight = (X.L == null) ? -1 : X.L.height;
int rightHeight = (X.R == null) ? -1 : X.R.height;
int nodeBalance = rightHeight - leftHeight;

//等于2表示需要做调整, 右树 > 左树
if (nodeBalance == 2) {
//高度:X.R.R = X.L + 1 表示是RR类型
if (X.R.R != null && X.R.R.height == leftHeight + 1) {
//X进行左旋 然后更新旋转的节点高度
} else {
//否则是 RL类型,X.R右旋,然后X左旋,更新旋转节点高度
}
} else if (nodeBalance == -2) {
//高度:X.L.L = X.R + 1,表示是LL型
if (X.L.L != null && X.L.L.height == rightHeight + 1) {
//X进行右旋,然后更新旋转的节点高度
} else {
//否则是LR类型,X.L左旋,然后X右旋,更新旋转节点高度
}
} else {
//不需要调整
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//左旋
protected Node rotateLeft(Node node) {
Node temp = node.right;
temp.parent = node.parent;

node.right = temp.left;
if (node.right != null) {
node.right.parent = node;
}

temp.left = node;
node.parent = temp;

// temp took over node's place so now its parent should point to temp
if (temp.parent != null) {
if (node == temp.parent.left) {
temp.parent.left = temp;
} else {
temp.parent.right = temp;
}
} else {
root = temp;
}

return temp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//右旋
protected Node rotateRight(Node node) {
Node temp = node.left;
temp.parent = node.parent;

node.left = temp.right;
if (node.left != null) {
node.left.parent = node;
}

temp.right = node;
node.parent = temp;

// temp took over node's place so now its parent should point to temp
if (temp.parent != null) {
if (node == temp.parent.left) {
temp.parent.left = temp;
} else {
temp.parent.right = temp;
}
} else {
root = temp;
}

return temp;
}

SB树

1
2
3
4
5
6
7
8
9
10
Size Balanced Tree:平衡二叉搜索树
1)让每一个叔叔节点为头的数,节点个数都不少于其任何一个侄子节点 保证了左右子树的规模不会相差 N+1个节点以上
2)也是从底层被影响节点开始向上做路径每个节点检查
3)与AVL树非常像,也是四种违规类型:LL、RR、LR、RL
4)与AVL树非常像,核心点是:
LL(做一次右旋)、RR(做一次左旋)
LR和RL(利用旋转让底层那个上到顶部)
5)与AVL树不同的是,每轮经过调整后,谁的孩子发生变化了,谁就再查

单次增/删/旋转的时间复杂度都是O(1)
1
2
3
4
5
SB树在使用时候的改进
1)删除时候可以不用检查
2)就把平衡性的调整放在插入的时候
3)因为这种只要变就递归的特性,别的树没有
4)可以在节点上封装别的数据项,来增加功能
1
2
3
4
5
6
7
8
9
10
11
12
13
假设有函数M(X),其含义表示查询X节点是否有违规情况:  

LL: X.L.L(侄子节点) > X.R(叔叔节点)
操作:X节点右旋, 原X.L接替X节点位置,需要递归M(X)和M(原X.L)判断旋转改变位置后是否违规

RR: X.R.R(侄子节点) > X.L(叔叔节点)
操作:X节点左旋, 原X.R接替X节点位置,需要递归M(X)和M(原X.R)判断旋转改变位置后是否违规

LR: X.L.R(侄子节点) > X.R(叔叔节点)
操作:X.L.R旋转上来替代X,则需要递归原X节点的M(X)、M(X.L)、M(X.L.R)

RL: X.R.L(侄子节点) > X.L(叔叔节点)
操作:X.R.L旋转上来替代X,则需要递归原X节点的M(X)、M(X.R)、M(X.R.L)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//自定义的SB数结构
public static class SBTNode<K extends Comparable<K>, V> {
public K key;
public V value;
public SBTNode<K, V> l; //左孩子节点
public SBTNode<K, V> r; //右孩子节点
public int size; // 当前节点有多少个节点(子树节点 + 自身)

public SBTNode(K key, V value) {
this.key = key;
this.value = value;
size = 1; //创建时默认是1,只有自己一个
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
public static class SizeBalancedTreeMap<K extends Comparable<K>, V> {
//只要个根节点
private SBTNode<K, V> root;

//右旋,返回旋转后的顶部节点
private SBTNode<K, V> rightRotate(SBTNode<K, V> cur) {
SBTNode<K, V> leftNode = cur.l;
cur.l = leftNode.r;
leftNode.r = cur;
//cur.l节点直接继承cur的size
leftNode.size = cur.size;
//cur的旋转后的size需要重新计算
cur.size = (cur.l != null ? cur.l.size : 0) + (cur.r != null ? cur.r.size : 0) + 1;
return leftNode;
}

private SBTNode<K, V> leftRotate(SBTNode<K, V> cur) {
SBTNode<K, V> rightNode = cur.r;
cur.r = rightNode.l;
rightNode.l = cur;
rightNode.size = cur.size;
cur.size = (cur.l != null ? cur.l.size : 0) + (cur.r != null ? cur.r.size : 0) + 1;
return rightNode;
}

//递归检查平衡
private SBTNode<K, V> maintain(SBTNode<K, V> cur) {
if (cur == null) {
return null;
}
//LL
if (cur.l != null && cur.l.l != null && cur.r != null && cur.l.l.size > cur.r.size) {
//cur节点右旋,原cur.L接替cur节点位置,需要递归M(cur)和M(原cur.L)是否违规
cur = rightRotate(cur);
cur.r = maintain(cur.r);
cur = maintain(cur);
} else if (cur.l != null && cur.l.r != null && cur.r != null && cur.l.r.size > cur.r.size) {
//LR类型 左旋+右旋 ,检查cur.l cur.r cur
cur.l = leftRotate(cur.l);
cur = rightRotate(cur);
cur.l = maintain(cur.l);
cur.r = maintain(cur.r);
cur = maintain(cur);
} else if (cur.r != null && cur.r.r != null && cur.l != null && cur.r.r.size > cur.l.size) {
//RR
cur = leftRotate(cur);
cur.l = maintain(cur.l);
cur = maintain(cur);
} else if (cur.r != null && cur.r.l != null && cur.l != null && cur.r.l.size > cur.l.size) {
//RL
cur.r = rightRotate(cur.r);
cur = leftRotate(cur);
cur.l = maintain(cur.l);
cur.r = maintain(cur.r);
cur = maintain(cur);
}
return cur;
}

//查询节点
private SBTNode<K, V> findLastIndex(K key) {
//用一个字段缓存最接近这个key的节点,如果查不到这个key,就返回最接近的节点
SBTNode<K, V> pre = root;
SBTNode<K, V> cur = root;
while (cur != null) {
pre = cur;
if (key.compareTo(cur.key) == 0) {
break;
} else if (key.compareTo(cur.key) < 0) {
cur = cur.l;
} else {
cur = cur.r;
}
}
return pre;
}

private SBTNode<K, V> findLastNoSmallIndex(K key) {
SBTNode<K, V> ans = null;
SBTNode<K, V> cur = root;
while (cur != null) {
if (key.compareTo(cur.key) == 0) {
ans = cur;
break;
} else if (key.compareTo(cur.key) < 0) {
ans = cur;
cur = cur.l;
} else {
cur = cur.r;
}
}
return ans;
}

private SBTNode<K, V> findLastNoBigIndex(K key) {
SBTNode<K, V> ans = null;
SBTNode<K, V> cur = root;
while (cur != null) {
if (key.compareTo(cur.key) == 0) {
ans = cur;
break;
} else if (key.compareTo(cur.key) < 0) {
cur = cur.l;
} else {
ans = cur;
cur = cur.r;
}
}
return ans;
}

// 现在,以cur为头的树上,加(key, value)这样的记录
// 加完之后,会对cur做检查,该调整调整
// 返回,调整完之后,整棵树的新头部
private SBTNode<K, V> add(SBTNode<K, V> cur, K key, V value) {
if (cur == null) {
return new SBTNode<K, V>(key, value);
} else {
cur.size++;
if (key.compareTo(cur.key) < 0) {
cur.l = add(cur.l, key, value);
} else {
cur.r = add(cur.r, key, value);
}
return maintain(cur);
}
}

// 在cur这棵树上,删掉key所代表的节点
// 返回cur这棵树的新头部
// 删除不调整平衡性
private SBTNode<K, V> delete(SBTNode<K, V> cur, K key) {
cur.size--;
if (key.compareTo(cur.key) > 0) {
cur.r = delete(cur.r, key);
} else if (key.compareTo(cur.key) < 0) {
cur.l = delete(cur.l, key);
} else { // 当前要删掉cur
if (cur.l == null && cur.r == null) {
// free cur memory -> C++
cur = null;
} else if (cur.l == null && cur.r != null) {
// free cur memory -> C++
cur = cur.r;
} else if (cur.l != null && cur.r == null) {
// free cur memory -> C++
cur = cur.l;
} else { // 有左有右
SBTNode<K, V> pre = null;
SBTNode<K, V> des = cur.r;
des.size--;
while (des.l != null) {
pre = des;
des = des.l;
des.size--;
}
if (pre != null) {
pre.l = des.r;
des.r = cur.r;
}
des.l = cur.l;
des.size = des.l.size + (des.r == null ? 0 : des.r.size) + 1;
// free cur memory -> C++
cur = des;
}
}
//如果删除SB树在删除的时候要调整平衡性,则在这里加
//cur = maintain(cur);
return cur;
}

private SBTNode<K, V> getIndex(SBTNode<K, V> cur, int kth) {
if (kth == (cur.l != null ? cur.l.size : 0) + 1) {
return cur;
} else if (kth <= (cur.l != null ? cur.l.size : 0)) {
return getIndex(cur.l, kth);
} else {
return getIndex(cur.r, kth - (cur.l != null ? cur.l.size : 0) - 1);
}
}

public int size() {
return root == null ? 0 : root.size;
}

public boolean containsKey(K key) {
if (key == null) {
throw new RuntimeException("invalid parameter.");
}
SBTNode<K, V> lastNode = findLastIndex(key);
return lastNode != null && key.compareTo(lastNode.key) == 0 ? true : false;
}

public void put(K key, V value) {
if (key == null) {
throw new RuntimeException("invalid parameter.");
}
SBTNode<K, V> lastNode = findLastIndex(key);
if (lastNode != null && key.compareTo(lastNode.key) == 0) {
lastNode.value = value;
} else {
//添加节点进二叉树中,需要重新遍历,调整后返回调整之后的root
root = add(root, key, value);
}
}

public void remove(K key) {
if (key == null) {
throw new RuntimeException("invalid parameter.");
}
if (containsKey(key)) {
root = delete(root, key);
}
}

public K getIndexKey(int index) {
if (index < 0 || index >= this.size()) {
throw new RuntimeException("invalid parameter.");
}
return getIndex(root, index + 1).key;
}

public V getIndexValue(int index) {
if (index < 0 || index >= this.size()) {
throw new RuntimeException("invalid parameter.");
}
return getIndex(root, index + 1).value;
}

public V get(K key) {
if (key == null) {
throw new RuntimeException("invalid parameter.");
}
SBTNode<K, V> lastNode = findLastIndex(key);
if (lastNode != null && key.compareTo(lastNode.key) == 0) {
return lastNode.value;
} else {
return null;
}
}

public K firstKey() {
if (root == null) {
return null;
}
SBTNode<K, V> cur = root;
while (cur.l != null) {
cur = cur.l;
}
return cur.key;
}

public K lastKey() {
if (root == null) {
return null;
}
SBTNode<K, V> cur = root;
while (cur.r != null) {
cur = cur.r;
}
return cur.key;
}

public K floorKey(K key) {
if (key == null) {
throw new RuntimeException("invalid parameter.");
}
SBTNode<K, V> lastNoBigNode = findLastNoBigIndex(key);
return lastNoBigNode == null ? null : lastNoBigNode.key;
}

public K ceilingKey(K key) {
if (key == null) {
throw new RuntimeException("invalid parameter.");
}
SBTNode<K, V> lastNoSmallNode = findLastNoSmallIndex(key);
return lastNoSmallNode == null ? null : lastNoSmallNode.key;
}
}

跳表

1
2
3
4
5
跳表(skiplist)
1)结构上根本和搜索二叉树无关
2)利用随机概率分布来使得高层索引可以无视数据规律,做到整体性能优良
3)思想是所有有序表中最先进的
4)结构简单就是多级单链表

algorithm

1
2
3
4
5
6
7
8
9
10
1.以KEY=NULL作为最左节点且链表中最小的节点
2.每个节点的索引指针数量是利用随机概率分布得到的
3.KEY=NULL的索引指针数量会根据其他节点的指针数量做扩大
4.每次索引节点时,索引到无结果时,会进行指针下跳的操作

如上述图中,黄色节点表示当前链表,蓝色节点表示是当前链表准备新增的节点
1.步骤一中添加nextNodes.size=3的节点3, NULL节点会先对自身的nextNodes进行扩大 1 -> 3
2.NULL节点中寻找小于且最接近节点3的节点,然后改变索引指针指向
3.步骤二中添加nextNodes.size=2的节点5,NULL无需扩容,找到了最接近节点5的节点3
4.由于节点5无高层索引指针,所以进行索引指针下跳,到第二条索引指针,进行连接

algorithm

1
2
3
4
5
6
7
在理想情况下,层数应该是这样的:
...
4: N/8个节点
3: N/4个节点
2: N/2个节点
1: N个节点
查询的时间复杂度是O(logN)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 跳表的节点定义
public static class SkipListNode<K extends Comparable<K>, V> {
public K key;
public V val;
//当前节点有多条指向外部的指针
//跳表中认为 key:null 是链表中的最小节点
//经典的跳表的nextNodes的size是根据随机数随机产生的
//头节点key:null 的nextNodes如果发现有其他节点size比他大,就会扩充得和他一样大
public ArrayList<SkipListNode<K, V>> nextNodes;

public SkipListNode(K k, V v) {
key = k;
val = v;
nextNodes = new ArrayList<SkipListNode<K, V>>();
}

// 遍历的时候,如果是往右遍历到的null(next == null), 遍历结束
// 头(null), 头节点的null,认为最小
// node -> 头,node(null, "") node.isKeyLess(!null) true
// node里面的key是否比otherKey小,true,不是false
public boolean isKeyLess(K otherKey) {
// otherKey == null -> false
return otherKey != null && (key == null || key.compareTo(otherKey) < 0);
}

public boolean isKeyEqual(K otherKey) {
return (key == null && otherKey == null)
|| (key != null && otherKey != null && key.compareTo(otherKey) == 0);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
public static class SkipListMap<K extends Comparable<K>, V> {
//随机指针的概率 55开
private static final double PROBABILITY = 0.5; // < 0.5 继续做,>=0.5 停
private SkipListNode<K, V> head;
//不同Key的数量
private int size;
//目前最大索引指针高度, 从0层开始
private int maxLevel;

public SkipListMap() {
//初始化跳表时默认加入 Key:null 节点
head = new SkipListNode<K, V>(null, null);
head.nextNodes.add(null);
size = 0;
maxLevel = 0;
}

// 从最高层开始,一路找下去,
// 最终,找到第0层的<key的最右的节点
private SkipListNode<K, V> mostRightLessNodeInTree(K key) {
if (key == null) {
return null;
}
//从最高层开始遍历
int level = maxLevel;
SkipListNode<K, V> cur = head;
// 从上层跳下层
while (level >= 0) {
// cur level -> level-1 //从左往右走
cur = mostRightLessNodeInLevel(key, cur, level--);
}
return cur;
}

// 在level层里,如何往右移动
// 现在来到的节点是cur,来到了cur的level层,在level层上,找到<key最后一个节点并返回
private SkipListNode<K, V> mostRightLessNodeInLevel(K key,
SkipListNode<K, V> cur,
int level) {
SkipListNode<K, V> next = cur.nextNodes.get(level);
while (next != null && next.isKeyLess(key)) {
cur = next;
next = cur.nextNodes.get(level);
}
return cur;
}

public boolean containsKey(K key) {
if (key == null) {
return false;
}
SkipListNode<K, V> less = mostRightLessNodeInTree(key);
SkipListNode<K, V> next = less.nextNodes.get(0);
return next != null && next.isKeyEqual(key);
}

public void put(K key, V value) {
if (key == null) {
return;
}
//找到0层上,最右一个,< Key的Node
SkipListNode<K, V> less = mostRightLessNodeInTree(key);
//基于这个节点在第0层取右边的节点
SkipListNode<K, V> find = less.nextNodes.get(0);
//右边的节点如果不为空,必定要么大于Key,要么等于Key
if (find != null && find.isKeyEqual(key)) {
find.val = value;
} else { //find == null || find.key > key
//新增节点,因为找不到匹配他的节点,在当前定位的less节点后面做节点插入操作
//节点数量++
size++;
//随机random出新增节点的层数,随机数小于0.5则层数++
int newNodeLevel = 0;
while (Math.random() < PROBABILITY) {
newNodeLevel++;
}
//比较新节点层数和头节点层数,如果比头节点层数大,头节点扩张层数
while (newNodeLevel > maxLevel) {
//在未加入节点时,头节点扩张的层数的next指针指向NULL
head.nextNodes.add(null);
maxLevel++;
}

SkipListNode<K, V> newNode = new SkipListNode<K, V>(key, value);
//创建节点后默认节点的层数指向NULL
for (int i = 0; i <= newNodeLevel; i++) {
newNode.nextNodes.add(null);
}
int level = maxLevel;
SkipListNode<K, V> pre = head;
//例子:

//head: ->null(新增层) newNode: ->null
// : ->oldNode->null : ->null

//head: ->newNode ->null
// : ->newNode ->oldNode -> null

//while循环Level下跳
while (level >= 0) {
//返回第Level层中最靠右且小于Key的节点
pre = mostRightLessNodeInLevel(key, pre, level);
//如果当前节点的层数小于等于新增节点的层数,则插入当前层
if (level <= newNodeLevel) {
//把新增结点的next指针指向上一个节点第Level层的next指针
newNode.nextNodes.set(level, pre.nextNodes.get(level));
//上一个节点的next指针指向当前节点
pre.nextNodes.set(level, newNode);
}
level--;
}
}
}

public V get(K key) {
if (key == null) {
return null;
}
SkipListNode<K, V> less = mostRightLessNodeInTree(key);
SkipListNode<K, V> next = less.nextNodes.get(0);
return next != null && next.isKeyEqual(key) ? next.val : null;
}

public void remove(K key) {
if (containsKey(key)) {
size--;
int level = maxLevel;
SkipListNode<K, V> pre = head;
while (level >= 0) {
pre = mostRightLessNodeInLevel(key, pre, level);
SkipListNode<K, V> next = pre.nextNodes.get(level);
// 1)在这一层中,pre下一个就是key
// 2)在这一层中,pre的下一个key是>要删除key
if (next != null && next.isKeyEqual(key)) {
//删除 pre -> 删除的Key - >pre.next.next 指向到下下个节点
pre.nextNodes.set(level, next.nextNodes.get(level));
}
//缩层,刚好删除了最高层唯一的节点
// 在level层只有一个节点了,就是默认节点head
if (level != 0 && pre == head && pre.nextNodes.get(level) == null) {
head.nextNodes.remove(level);
maxLevel--;
}
level--;
}
}
}

public K firstKey() {
return head.nextNodes.get(0) != null ? head.nextNodes.get(0).key : null;
}

public K lastKey() {
int level = maxLevel;
SkipListNode<K, V> cur = head;
while (level >= 0) {
SkipListNode<K, V> next = cur.nextNodes.get(level);
while (next != null) {
cur = next;
next = cur.nextNodes.get(level);
}
level--;
}
return cur.key;
}

//向上取 >= key 的节点
public K ceillingKey(K key) {
if (key == null) {
return null;
}
SkipListNode<K, V> less = mostRightLessNodeInTree(key);
SkipListNode<K, V> next = less.nextNodes.get(0);
return next != null ? next.key : null;
}

public K floorKey(K key) {
if (key == null) {
return null;
}
SkipListNode<K, V> less = mostRightLessNodeInTree(key);
SkipListNode<K, V> next = less.nextNodes.get(0);
return next != null && next.isKeyEqual(key) ? next.key : less.key;
}

public int size() {
return size;
}
}
1
2
3
4
5
6
7
8
9
10
现有有序表使用的题目:
假设有多个长度不一的有序数组
[1,6,9,31]
[3,20,30]
[2,25,32,55]
要求返回一个区间,最少能包含每个数组中的一个元素,且区间L必须最小,如[1,3],[30,32]不达标,因为不是最小

思想:
弄个小根堆,把每个数组中的第一个元素放进去,然后记录当前区间(区间长度变小才更新),弹出最小值
然后添加弹出最小值所在的数组中的index + 1的元素,周而复始,
1
2
3
4
5
改写有序表的题目核心点
1)分析增加什么数据项可以支持题目
2)有序表一定要保持内部参与排序的key不重复
3)增加这个数据项了,在平衡性调整时,保证这个数据项也能更新正确
4)做到上面3点,剩下就是搜索二叉树怎么实现你想要的接口的问题了
1
2
3
4
5
需要改写有序表的题目一:

给定一个数组arr,和两个整数a和b(a<=b)
求arr中有多少个子数组,累加和在[a,b]这个范围上
返回达标的子数组数量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
思路:
计算一个从零开始,[0,1],[0,2]...[0,N-1]的累加和,并存储在对应的新数组sums中,假设[a,b] = [10,30]
假设sum[0,i] = 100,有sum[0,j] =70,那么必然sum[j,i]=30
也就是说,以i结尾,[0,i]之前,有多少个累加和的值属于[70,90],就是以i为结尾,达标的子数组数量
子数组累加和[a,b]范围的问题,将会转换成以0开头,有多少个index的累加和落在[sum-b,sum-a]范围上

如果把数组sums转换成一个有序链表,提供一个add(num)和lessKeySize(num)方法
add()方法用来添加累加和的值
lessKeySize查询小于num的数有多少,查询累加和落[L,R]范围上=lessKeySize(R+1) - lessKeySize(L)

改写SB树:
Node节点增加 int all属性(记录经过该节点及以下的数据次数),每添加节点时,划过的节点all++
5(100)
4(30) 8(60)
假设头节点累加和=5,其all=100,要查询num<6的值有多少个,先进入头节点,然后5小于6,向右滑
这时候count = 100 - 60 = 40, 向右滑进行减值操作,向左滑不操作,最后lessKeySize(6) = 40
1
2
3
4
5
6
7
public static class SBTNode {
public long key;
public SBTNode l;
public SBTNode r;
public long size; // 不同key的size 平衡SB树用
public long all; // 总的size 节点旋转时该值需要跟着size一起做调整 用来允许增加重复数字
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//用以计算小于key的数值量有多少个
public long lessKeySize(long key) {
SBTNode cur = root;
long ans = 0;
while (cur != null) {
if (key == cur.key) {
return ans + (cur.l != null ? cur.l.all : 0);
} else if (key < cur.key) {
cur = cur.l;
} else {
//向右滑进行累加计算
ans += cur.all - (cur.r != null ? cur.r.all : 0);
cur = cur.r;
}
}
return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static int countRangeSum2(int[] nums, int lower, int upper) {
SizeBalancedTreeSet treeSet = new SizeBalancedTreeSet();
long sum = 0;
int ans = 0;
treeSet.add(0);// 一个数都没有的时候,就已经有一个前缀和累加和为0,
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
// sum i结尾的时候[lower, upper]
// 之前所有前缀累加和中,有多少累加和落在[sum - upper, sum - lower]
// 查 ? < sum - lower + 1 a
// 查 ? < sum - upper b
// a - b

long a = treeSet.lessKeySize(sum - lower + 1);
long b = treeSet.lessKeySize(sum - upper);
ans += a - b;
treeSet.add(sum);
}
return ans;
}
1
2
3
4
5
6
需要改写有序表的题目二
有一个滑动窗口(讲过的):
1)L是滑动窗口最左位置、R是滑动窗口最右位置,一开始LR都在数组左侧
2)任何一步都可能R往右动,表示某个数进了窗口
3)任何一步都可能L往右动,表示某个数出了窗口
想知道每一个窗口状态的中位数(偶数严格求(上中位 + 下中位) /2)
1
2
思想:
把上述问题转换成改写有序表,结构中允许增加数字(重复数字)、减少数字、查询第K小的数字是多少的问题

AC自动机

1
2
3
4
5
AC自动机本质上就是这么一颗前缀树, 还有fail指针
在AC自动机里, 每一个节点多出一个指针: fail指针

关键在于fail指针的理解
fail指针含义:目前来到的节点,之前路径上的字符串记为str,除了str之外哪个前缀字符串,和str的后缀串匹配最大,fail指针就指向那个最大匹配串的最后字符底下的节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
fail指针建立的策略
1.每一个节点都有fail指针,
2.头结点的fail指针: 人为规定 指向空
3.第一级孩子的fail指针: 人为规定指向头

4.加fail指针的方式是把所有前缀树生成好以后,再加一个(按宽度优先遍历方式)fail指针的设置过程
不是字符串一个一个在加的过程中设置的,是在候选串加完前缀树之后, 再按照宽度优先遍历的方式设置好fail指针

5.来到父亲节点, 去设置孩子节点的指针,父亲节点的fail指向x
假设父亲节点到孩子节点的路是a,x也有a方向的路,则孩子节点fail指针指向x.a

6.如果x方向没有指向a的路,x通过他的fail,指针跳向y,如果y有走向a方向的路,孩子指针指过去
7.如果y也没有走向a方向的路, y再通过自己的,fail指针跳到z,看z有没有走向a方向的路,如果z有走向a方向的路,孩子指针指过去
8.如果z没有走向a方向的路, 继续往下跳,如果在这个过程中一直没有走向a方向的路,到空了也没有, fail指针指向开头
1
2
3
4
5
6
所谓fail指针的含义是:
如果必须以e结尾, 哪一个另外的前缀串和我以e结尾的后缀串彻底相等,并长度最大, 我就指到哪儿去
如有bcde, cde, de, e,对于bcde中的e来说,cde、de、e都满足
所有前缀串推到e为止, 整个前缀串和以e结尾的后缀串相等的可能性,中哪个是最大的, 这个节点的fail指针指向哪儿去
是bcde中的e这个节点对应的代表的前缀串cde, 是所有可能性中最大的
必须以某一个前缀串开头的整体, 配上一个以e结尾的整体 必须得相等,而且还是最长的,所以bcde只能去找cde

algorithm

1
2
3
4
5
6
7
8
给你一个"abcdtks", 问命中了哪些字符串?
有没有a, 有a, 有b, 有c, 有d, 你有没有t, 我已经不再有t了, 通过fail指针跳转
这么一蹦, 有一个含义:
你匹配过的东西, 不可能含有任何一个匹配串,abcd以a开头的,不可能再找到后序的匹配串了

当跳到b上时, 实际是在尝试, 以b开头能不能匹配出某个匹配串来,彻底宣告了a开头的失败, 所以是fail指针
因为后面不再有t了, 我从一个前缀路径蹦到另外一个前缀路径,就等于你从你文章开始abcde的匹配宣告失败
但是我有可能接着去匹配bcd为前缀的后序的
1
2
3
4
5
6
利用AC自动机:
依次否定文章从零位置开始开头的可能性
0开头的可能性
1开头的可能性
2开头的可能性
每一次失败这么跳转的含义能够让我不可能的路径直接往下蹦, 宣告了在文章中某一个开头的失败
1
2
3
4
5
6
收集答案:
AC自动机建好以后, failed指针的含义也就相应的建好了
在匹配的时候 如果成功, 每到一个节点, 顺着fail指针转一圈收集答案
如果转一圈的途中,有end>0的节点, 收集答案,并给它一个状态,表示下回再蹦到它就不要再蹦了
成功的时候, 不会跳转到fail指针,只会顺着fail指针收集答案, 该在什么路径上还,还在什么路径上
但是失败的时候, 要顺着fail指针蹦到另外一条路径的节点上去,接着收集答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 前缀树的节点
public static class Node {
// 如果一个node,end为空,不是结尾
// 如果end不为空,表示这个点是某个字符串的结尾,end的值就是这个字符串
public String end;
// 只有在上面的end变量不为空的时候,endUse才有意义
// 表示,这个字符串之前有没有加入过答案
public boolean endUse;
public Node fail;
public Node[] nexts;
public Node() {
endUse = false;
end = null;
fail = null;
nexts = new Node[26];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
public static class ACAutomation {
private Node root;

public ACAutomation() {
root = new Node();
}

public void insert(String s) {
char[] str = s.toCharArray();
Node cur = root;
int index = 0;
for (int i = 0; i < str.length; i++) {
index = str[i] - 'a';
if (cur.nexts[index] == null) {
Node next = new Node();
cur.nexts[index] = next;
}
cur = cur.nexts[index];
}
cur.end = s;
}

//添加完前缀树后手动调用build方法,不支持动态修改前缀树
public void build() {
Queue<Node> queue = new LinkedList<>();
queue.add(root);
Node cur = null;
Node cfail = null;
//宽度优先遍历 把每个节点中的next[26]个都加到queue中
while (!queue.isEmpty()) {
// 当前节点弹出,
// 当前节点的所有后代加入到队列里去,
// 当前节点给它的子去设置fail指针
// cur -> 父亲
cur = queue.poll();
for (int i = 0; i < 26; i++) { // 所有的路
if (cur.nexts[i] != null) { // 找到所有有效的路
cur.nexts[i].fail = root; //先设置成头节点
cfail = cur.fail;
while (cfail != null) {
//如果fail指针有路指向,则设置
if (cfail.nexts[i] != null) {
cur.nexts[i].fail = cfail.nexts[i];
break;
}
//否则接着找fail.fail
cfail = cfail.fail;
}
queue.add(cur.nexts[i]);
}
}
}
}

public List<String> containWords(String content) {
char[] str = content.toCharArray();
Node cur = root;
Node follow = null;
int path = 0;
List<String> ans = new ArrayList<>();
for (int i = 0; i < str.length; i++) { // 依次遍历文章中的字符,i位置
path = str[i] - 'a'; // 路
// 如果当前字符在这条路上没配出来,就随着fail方向走向下条路径
// 如果当前cur节点,没有path的路,就通过fail,跳到别的前缀上去
while (cur.nexts[path] == null && cur != root) {
cur = cur.fail;
}
// 1) 现在来到的路径,是可以继续匹配的
// 2) 现在来到的节点,已经是头了
cur = cur.nexts[path] != null ? cur.nexts[path] : root;
follow = cur;
while (follow != root) {
if(follow.endUse) {
break;
}
// 不同的需求,在这一段之间修改
if (follow.end != null) {
ans.add(follow.end);
follow.endUse = true;
}
// 不同的需求,在这一段之间修改
follow = follow.fail;
}
}
//返回结果之前对follow.endUse重置
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
public static void main(String[] args) {
ACAutomation ac = new ACAutomation();
ac.insert("dhe");
ac.insert("he");
ac.insert("abcdheks");
// 设置fail指针
ac.build();

List<String> contains = ac.containWords("abcdhekskdjfafhasldkflskdjhwqaeruv");
for (String word : contains) {
System.out.println(word);
}
}

最后更新: 2021年02月01日 11:02

原始链接: https://midkuro.gitee.io/2020/10/30/algorithm-trainingcamp2/

× 请我吃糖~
打赏二维码