ARTS-第15周

发表于

ARTS （第15周）

触类旁通。

很多结构都是另一个结构引申和优化出来的。

本周：

AC自动机、SUNDAY算法、贪心算法小练习。

Algorithm 算法

AC自动机

基于trie树构建一个类似KMP算法失效函数的失效指针，当进行树结构的匹配失败的时候，就通过失效指针进行快速跳转。

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
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
package search;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Random;

/**
 * @description
 * 
 * @author lfy
 */

public class Ac {
	static int err = 0;
	public static void main(String[] args) {
		for (int i = 0; i < 100000; i++) {
			test();
		}
		System.out.println("err:"+err);
	}

	private static void test() {
		
		
		String[] p = new String[2];
		//String text = generateString(10);
		//使用固定并且不同字符的字符串 
		//因为indexof是匹配首个 而ac是匹配全部 防止重复
		String text = "abcdefg";
		Ac ac = new Ac();
		ArrayList<Integer> r1 = new ArrayList<Integer>();
		ArrayList<Integer> r2 = null;
		System.out.println("test:" + text);

		System.out.print("match:");
		// 固定生成2个字符的 固定生成2个
		//因为indexof是匹配首个 而ac是匹配全部 防止重复
		for (int j = 0; j < 2; j++) {
			p[j] = generateString(2);
			if(j==1){
				while(p[0].equals(p[1])){
					try {
						Thread.sleep(8);
					} catch (InterruptedException e) {
					}
					p[j] = generateString(2);
					
				}
			}
			
			System.out.print(p[j] + ",");
			ac.insert(p[j]);
			Integer io = Integer.valueOf(text.indexOf(p[j]));
			// 匹配到了
			if (!io.equals(Integer.valueOf(-1)))
				r1.add(io);

		}
		System.out.println();
		ac.build();
		r2 = ac.match2test(text);

		Collections.sort(r1);
		Collections.sort(r2);
		System.out.println("io_r:" + r1);
		System.out.println("ac_r:" + r2);
		if (r1.size() != r2.size()) {
			System.out.println("err1");
			System.exit(0);
			err++;
		} else {
			for (int i = 0; i < r1.size(); i++) {
				Integer i1 = r1.get(i);
				Integer i2 = r2.get(i);
				if (i1 != i2) {
					System.out.println("err2");
					System.exit(0);
					err++;
				}
			}

		}
	}

	// "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
	private static final String CHARS = "abcdefg";//// 随机字符串池

	/**
	 * 随机字符串
	 * 
	 * @author lfy
	 * @param length
	 * @return
	 */
	public static String generateString(int length) {
		StringBuffer sb = new StringBuffer();
		Random random = new Random();
		for (int i = 0; i < length; i++) {
			sb.append(CHARS.charAt(random.nextInt(CHARS.length())));
		}
		return sb.toString();
	}

	private static final int MAX_SIZE = 7;// 只匹配26个字符的情况

	Node root = new Node('/');// 根节点

	public void insert(String s) {
		insert(s.toCharArray());
	}

	public ArrayList<Integer> match2test(String s) {
		return match2test(s.toCharArray());

	}

	public void match(String s) {
		match(s.toCharArray());

	}

	public void build() {
		// 从根节点开始生成
		Queue<Node> queue = new LinkedList<>();
		root.f = null;// root匹配 方便后面进行跳出
		for (int i = 0; i < MAX_SIZE; i++) {
			Node cn = root.n[i];
			if (cn != null) {
				// 从第二级开始
				queue.add(cn);
				cn.f = root;// 第一级子节点失败全部指向root
			}
		}

		while (!queue.isEmpty()) {
			// 取出元素 父级节点
			Node p = queue.remove();
			for (int i = 0; i < MAX_SIZE; i++) {
				Node c = p.n[i];// 子节点
				if (c == null)
					continue;
				// 按层遍历 放入下一层遍历的对象
				// 循环最前面放进去和最后放进去 没有差别
				queue.add(c);
				
				int index = c.v - 'a';// 当前值的索引
				Node f = p.f;// 父节点的fail节点
				while (f != null) {
					Node node = f.n[index];
					if (node != null) {
						// 父节点的失败节点里查找子节点
						// 找到就可以跳出了
						c.f = node;
						break;
					}
					// 找不到 就找失败节点的失败节点
					f = f.f;
					//
					// 即更短后缀的词 如父节点是abc当前是x
					// 存在bc 和 c
					// 那么如果abcx找不到就找bc下找x节点 即找bcx节点
					// 再找不到去c节点下找x节点，即找cx节点
					// 再没有就去找root节点
					// 如果root都没有就跳出 跳出后赋值为root
				}
				if (f == null) {
					c.f = root;
				}

			}

		}

	}

	public ArrayList<Integer> match2test(char[] text) { // text 是主串
		ArrayList<Integer> r = new ArrayList<Integer>();//
		int len = text.length;
		// 带头指针
		// 即当前匹配字符的前一个字符
		Node p = root;
		for (int i = 0; i < len; i++) {
			int idx = text[i] - 'a';// 当前值的索引
			// 当前带头指针的后一个字符和当前值不相等
			// 就去找失败指针重新进行匹配 直到找不到 或者root为止
			// 当p.n[idx] 的值为null的时候 就代表着当前词缀不符合的主串
			// 那么就应该重新迭代 寻找失效指针 找最长相同后缀
			// p!=root的判断是为了判断是否到了root节点
			// 我这里的写法 root的失效指针指向了root
			// 如果root的失效指针为null 那这部的写法应该是p != null
			while (p != root && p.n[idx] == null) {//
				p = p.f;
			}
			// 匹配的话 p就前进一个节点
			// 如果不匹配 p就会变成null 在下面的循环里就会被重设为root
			p = p.n[idx];
			// 找不到匹配值的时候 重设为root
			if (p == null) {
				p = root;
			}
			// 遍历节点和当前节点的失效指针
			// 判断是否是结束节点
			Node temp = p;
			while (temp != root) {
				if (temp.isEnd == true) {
					// 这里不进行输出了记录数组下标位置 以便做测试
					int pos = i - temp.len + 1;
					r.add(pos);
					/*
					 * int pos = i - temp.len + 1; // 偏移量和长度 String str = new
					 * String(text, pos, p.len); System.out.println("符合值为:" +
					 * str);
					 */
				}

				temp = temp.f;// 重设设失效指针，即相同后缀的指针 判断isEnd值
			}
		}
		return r;
	}

	/**
	 * 匹配
	 */
	public void match(char[] text) { // text 是主串

		int len = text.length;
		// 带头指针
		// 即当前匹配字符的前一个字符
		Node p = root;
		for (int i = 0; i < len; i++) {
			int idx = text[i] - 'a';// 当前值的索引
			// 当前带头指针的后一个字符和当前值不相等
			// 就去找失败指针重新进行匹配 直到找不到 或者root为止
			// 当p.n[idx] 的值为null的时候 就代表着当前词缀不符合的主串
			// 那么就应该重新迭代 寻找失效指针 找最长相同后缀
			// p!=root的判断是为了判断是否到了root节点
			// 我这里的写法 root的失效指针指向了root
			// 如果root的失效指针为null 那这部的写法应该是p != null
			while (p != root && p.n[idx] == null) {//
				p = p.f;
			}
			// 匹配的话 p就前进一个节点
			// 如果不匹配 p就会变成null 在下面的循环里就会被重设为root
			p = p.n[idx];
			// 找不到匹配值的时候 重设为root
			if (p == null) {
				p = root;
			}
			// 遍历节点和当前节点的失效指针
			// 判断是否是结束节点
			Node temp = p;
			while (temp != root) {
				if (temp.isEnd == true) {

					int pos = i - temp.len + 1;
					// 偏移量和长度
					String str = new String(text, pos, p.len);
					System.out.println("符合值为:" + str);
				}

				temp = temp.f;// 重设设失效指针，即相同后缀的指针 判断isEnd值
			}
		}

	}

	public void insert(char[] text) {
		Node p = root;
		for (int i = 0; i < text.length; ++i) {
			int index = text[i] - 'a';
			if (p.n[index] == null) {
				Node newNode = new Node(text[i]);
				p.n[index] = newNode;
			}
			p = p.n[index];
			p.len = i + 1;// 深度
		}
		//
		p.isEnd = true;
		p.len = text.length;
	}

	// trie树的节点
	class Node {

		char v;// 值

		Node[] n = new Node[MAX_SIZE];// 下一个节点

		Node f;// 失败指针

		boolean isEnd = false;// 是否最后一个词缀

		int len = -1;// 从根到这里的长度

		public Node(char v) {
			this.v = v;
		}

		@Override
		public String toString() {
			if (f != this)
				return "Node [v=" + v + ", f=" + f + "]";
			return "Node [v=" + v + ", f= root]";
		}

	}
}

SUNDAY字符串搜索算法

和BM KMP等算法类似，都是先构建出一些辅助的数组来加块匹配，

这个算法的简易来说就是将主串和模式串对齐，从前开始匹配到最后 如果不匹配，就取主串后面的那个字符。

去辅助数组里查找对应字符是否存在，存在则进行相应的跳跃。不存在则跳过模式串长度+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
package search;

import java.util.Random;


public class SundaySearch {

	////////////////////////////////////////
	// 这部分为测试部分，70行往下才是BM算法
	////////////////////////////////////////

	public static void main(String[] args) {
		// test() ;
		// System.out.println(2<<15);
		int max = 100000;
		int err = 0;
		BMSearch bms = new BMSearch();
		System.out.println("========test=========");
		for (int i = 0; i < max; i++) {
			String pattern = generateString(3);
			String text = generateString(20);
			char[] t = text.toCharArray();
			char[] p = pattern.toCharArray();
			// 创建随机字符串
			// 用BM算法和string类的indexof得出的结果进行比对
			int bm = bms.bm(t, p);
			int sd = sunday(t, p);
			if (bm != sd) {
				System.err.println(i + ":" + text + ":" + pattern + ":fail:-->" + bm + ":" + sd);
				// System.exit(0);
				err++;
			} else {
				System.out.println(i + ":" + text + ":" + pattern + ":ok:-->" + bm + ":" + sd);
			}
		}
		System.out.println("err:" + err);
	}

	// "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
	private static final String CHARS = "abcdefg";//// 随机字符串池

	/**
	 * 随机字符串
	 * 
	 * @author lfy
	 * @param length
	 * @return
	 */
	public static String generateString(int length) {
		StringBuffer sb = new StringBuffer();
		Random random = new Random();
		for (int i = 0; i < length; i++) {
			sb.append(CHARS.charAt(random.nextInt(CHARS.length())));
		}
		return sb.toString();
	}

	static final int ASCII_SIZE = 126;

	public static int sunday(char[] t, char[] p) {
		int n = t.length;
		int m = p.length;
		int[] move = new int[ASCII_SIZE];
		// 初始化
		for (int i = 0; i < ASCII_SIZE; i++) {
			// 默认移动长度 代表在模式串中不存在该字符串的情况
			// 默认值为数组长度+1
			move[i] = m + 1;
		}
		// 从后往前 保证后面的会覆盖前面的 保证后面的优先级
		for (int i = 0; i < m; i++) {
			int index = p[i];// 模式串字符的ascii码 当作move数组的索引
			move[index] = m - i;
		}
		int pos = 0;// 偏移量
		while (pos + m <= n) {
			int i = 0;// 模式串指针
			while (t[i + pos] == p[i]) {
				i++;
				// 匹配
				if (i == m) {
					return pos;
				}
			}
			// 防止索引溢出
			if (pos + m >= n) {
				break;
			}
			// 主串的下一个字符串
			char idx = t[pos + m];
			// 应该移动的位置
			pos = pos + move[idx];
		}
		return -1;
	}
}

贪心算法小练习题

这是算法专栏里作者提供的3道小练习题。

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
package greed;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

/**
 * 贪心算法
 */
public class GreedTest {
	static Random rd = new Random();

	public static void main(String[] args) {
		LinkedList<Integer> candy = new LinkedList<Integer>();
		LinkedList<Integer> child = new LinkedList<Integer>();
		for (int i = 0; i < 5; i++) {
			candy.add(rd.nextInt(10) + 1);
			child.add(rd.nextInt(10) + 1);
		}
		getCandy(candy, child);
		int[] nums = new int[7];
		for (int i = 0; i < 7; i++) {
			nums[i] = (int) (Math.random() * 10);
		}
		// int[] nums2 = {0,0,0,0,0,0,1110};
		getMoney2((int) (Math.random() * 1000));
		getMoney((int) (Math.random() * 1000), nums);
		List<Integer[]> list = new ArrayList<>();
		for (int i = 0; i < 8; i++) {
			int a = (int) (Math.random() * 7);
			int b = (int) (Math.random() * 5) + a + 1;
			Integer[] is = { a, b };
			list.add(is);
		}
		region(list);
		region2(list);
	}

	// 分糖果
	/*
	 * 我们有 m 个糖果和 n 个孩子。我们现在要把糖果分给这些孩子吃，但是糖果少，孩子多（m<n），所以糖果只能分配给一部分孩子。
	 * 
	 * 每个糖果的大小不等，这 m 个糖果的大小分别是
	 * s1，s2，s3，……，sm。除此之外，每个孩子对糖果大小的需求也是不一样的，只有糖果的大小大于等于孩子的对糖果大小的需求的时候，孩子才得到满足。
	 * 假设这 n 个孩子对糖果大小的需求分别是 g1，g2，g3，……，gn。
	 * 
	 * 我的问题是，如何分配糖果，能尽可能满足最多数量的孩子？
	 */
	// 极客时间版权所有: https://time.geekbang.org/column/article/73188
	private static void getCandy(LinkedList<Integer> candy, LinkedList<Integer> child) {
		System.out.println("======贪心算法思路-分糖果=======");
		Collections.sort(child);
		Collections.sort(candy);
		System.out.println("糖果大小:" + candy);
		System.out.println("小孩需求:" + child);
		// 小孩和糖果从小到大排序
		// 从最小需求的小孩匹配最小的糖果
		// 符合就删除
		int count = 0;
		for (int i = 0; i < child.size(); i++) {
			for (int j = 0; j < candy.size(); j++) {
				if (child.get(i).intValue() <= candy.get(j).intValue()) {
					System.out.println(i + "号小孩，拿了" + (j + count) + "号糖果,需求-糖果大小:" + child.get(i) + "-" + candy.get(j));
					count++;
					candy.remove(j);
					break;//
				}

			}
		}
		System.out.println("count:" + count);

	}

	// 钱币找零
	/*
	 * 这个问题在我们的日常生活中更加普遍。假设我们有 1 元、2 元、5 元、10 元、20 元、50 元、100 元这些面额的纸币， 它们的张数分别是
	 * c1、c2、c5、c10、c20、c50、c100。我们现在要用这些钱来支付 K 元，最少要用多少张纸币呢？
	 * 
	 */
	// 极客时间版权所有: https://time.geekbang.org/column/article/73188
	private static void getMoney(int n, int[] nums) {
		System.out.println("=====贪心算法思路-钱币找零-有数量限制======");
		System.out.println("初始金额:" + n);
		System.out.println("零钱数量:");
		int[] moneys = { 100, 50, 20, 10, 5, 2, 1 };
		for (int i = 0; i < nums.length; i++) {
			System.out.print(moneys[i] + "元:" + nums[i] + "张,");
		}
		System.out.println();
		LinkedList<Integer> r = new LinkedList<>();
		for (int i = 0; i < moneys.length; i++) {
			if (n >= moneys[i] && nums[i] > 0) {
				n -= moneys[i];
				nums[i]--;
				r.add(moneys[i]);
				i--;// 符合就在当前继续
			}
		}

		System.out.println();
		System.out.println("结果:" + r);
		int idx = 0;
		int count = 0;
		System.out.print("张数:");
		for (int i = 0; i < r.size(); i++) {
			if (r.get(i) == moneys[idx]) {
				count++;
			} else {
				if (count != 0)
					System.out.print(moneys[idx] + "元:" + count + "张,");
				idx++;
				i--;// 符合就在当前继续
				count = 0;
			}
		}
		if (count != 0)
			System.out.print(moneys[idx] + "元:" + count + "张,");
		System.out.println();
		if (n > 0) {
			System.err.println("钱不够,还剩余:" + n);
		}
	}

	// 无数量限制
	private static void getMoney2(int n) {
		System.out.println("=====贪心算法思路-钱币找零-无数量限制======");
		System.out.println("初始金额:" + n);
		int[] moneys = { 100, 50, 20, 10, 5, 2, 1 };
		LinkedList<Integer> r = new LinkedList<>();
		for (int i = 0; i < moneys.length; i++) {
			if (n >= moneys[i]) {
				n -= moneys[i];
				r.add(moneys[i]);
				i--;// 符合就在当前继续
			}
		}
		System.out.println("结果:" + r);
		int idx = 0;
		int count = 0;
		System.out.print("张数:");
		for (int i = 0; i < r.size(); i++) {
			if (r.get(i) == moneys[idx]) {
				count++;
			} else {
				if (count != 0)
					System.out.print(moneys[idx] + "元:" + count + "张,");
				idx++;
				i--;// 符合就在当前继续
				count = 0;
			}
		}
		if (count != 0)
			System.out.print(moneys[idx] + ":" + count + "张,");
		System.out.println();
	}

	// 区间覆盖
	/*
	 * 假设我们有 n 个区间，区间的起始端点和结束端点分别是 [l1, r1]，[l2, r2]，[l3, r3]，……，[ln, rn]。 我们从这
	 * n 个区间中选出一部分区间，这部分区间满足两两不相交（端点相交的情况不算相交），最多能选出多少个区间呢？
	 */
	// 极客时间版权所有: https://time.geekbang.org/column/article/73188
	// 根据右边索引
	public static void region(List<Integer[]> a) {
		System.out.println("====贪心算法思路-区间覆盖-根据右边索引======");
		System.out.println("原始:");
		for (Integer[] integers : a) {
			System.out.print(Arrays.toString(integers));
		}
		System.out.println();
		// 找最小
		List<Integer[]> r = new LinkedList<>();
		int min = a.get(0)[0];// 有最小索引的
		for (int i = 0; i < a.size(); i++) {
			Integer[] b = a.get(i);
			if (min > b[0]) {
				min = b[0];
			}
		}

		while (true) {
			int idx = -1;
			int rIdx = -1;
			for (int i = 0; i < a.size(); i++) {
				Integer[] b = a.get(i);
				// 在最小节点的右边
				// 长度比当前最小长度要小 或者未赋值过
				// 右边更小
				if (b[0] >= min && (b[1] < rIdx || rIdx == -1)) {
					rIdx = b[1];
					idx = i;
				}
			}
			if (idx == -1)
				break;
			Integer[] arr = a.get(idx);
			r.add(arr);
			min = rIdx;
		}
		System.out.println("结果：");
		for (Integer[] integers : r) {
			System.out.print(Arrays.toString(integers));
		}
		System.out.println();
	}

	// 根据长度
	public static void region2(List<Integer[]> a) {
		System.out.println("====贪心算法思路-区间覆盖-根据区间长度======");
		System.out.println("原始:");
		for (Integer[] integers : a) {
			System.out.print(Arrays.toString(integers));
		}
		System.out.println();
		// 找最小
		List<Integer[]> r = new LinkedList<>();
		int min = a.get(0)[0];// 有最小索引的
		for (int i = 0; i < a.size(); i++) {
			Integer[] b = a.get(i);
			if (min > b[0]) {
				min = b[0];
			}
		}

		while (true) {
			int idx = -1;
			int len = -1;
			for (int i = 0; i < a.size(); i++) {
				Integer[] b = a.get(i);
				int bl = b[1] - b[0];
				// 在最小节点的右边
				// 长度比当前最小长度要小 或者未赋值过
				// 右边更小
				if (b[0] >= min && (bl < len || len == -1)) {
					len = bl;
					idx = i;
				}
			}
			//
			if (idx == -1)
				break;
			Integer[] arr = a.get(idx);
			r.add(arr);
			min = arr[1];
		}
		System.out.println("结果：");
		for (Integer[] integers : r) {
			System.out.print(Arrays.toString(integers));
		}
		System.out.println();
	}
}

Review 英文文章

http://kafka.apache.org/intro

kafka的介绍（引导）

Tip 技巧

极客时间的专栏《数据结构与算法之美》

本周学习了该专栏中的35-37篇

内容如下：

TRIE树：又称单词查找树，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

AC自动机：基于trie树构建一个类似KMP算法失效函数的失效指针，当进行树结构的匹配失败的时候，就通过失效指针进行快速跳转。

贪心算法：贪心算法的核心思想就是每次选择都选择对于当前来说是最好的选择。但是这样选择的最终结果不一定是最好的。

Share 分享

https://www.jianshu.com/p/2e6eb7386cd3
SUNDAY 算法