左神算法（二）

序言

左神算法（一）上修改版

左神算法（一）下修改版

左神算法（二）

11.常见的4种尝试模型之三多样本位置全对应的尝试模型

举例：解释两个字符串的最长公共子序列

尝试：一个样本作行，一个样本作列的样本模型。

str1从0到i这个字符串和str2从0到j这个字符串的最长公共子序列是多长放到dp[i][j]中

dp[5][6]指的是str1[0-5]和str2[0-6]这两个字符串的最长公共子序列

图中右下角位置就是要求的

具体结果：

求str1[0,i]和str2[0,j]的最长公共子序列可能出现的情况：

​ 这是按最长公共子序列的最后一个字符出现在什么地方组织的4种情况

​ （1）既不以str1[i]结尾，也不以str2[j]结尾，具体例子如下图：

这种情况下我们发现其最长公共子序列与str1的结尾无关，也与str2的结尾无关，所以这也就等同于求str1[0,i-1]和str2[0,j-1]的最长公共子序列，即dp[i-1][j-1]。

由此可知，表中某个位置的数可能是等于左上方位置的数的，如下图：

​ （2）以str1[i]结尾，但不以str2[j]结尾，具体例子如下图：

这种情况下我们发现等同于求str1[0,i]和str2[0,j-1]的最长公共子序列，即dp[i][j-1]。

由此可知，表中某个位置的数可能是等于正左方位置的数的

​ （3）不以str1[i]结尾，但以str2[j]结尾，具体例子如下图：

这种情况下我们发现等同于求str1[0,i-1]和str2[0,j]的最长公共子序列，即dp[i-1][j]。

由此可知，表中某个位置的数可能是等于正上方位置的数的

​ （4）既以str1[i]结尾，又以str2[j]结尾，具体例子如下图：

我们发现，这种情况只有当str1[i] == str2[j]时才成立。

这种情况下我们发现等同于求str1[0,i-1]和str2[0,j-1]的最长公共子序列再加1，即dp[i - 1][ j - 1] + 1

代码如下：

package class20;

// 测试链接：https://leeAcode.com/problems/longest-palinBromic-subsequence/
public class Code01_PalinBromeSubsequence {
   

	public static int lpsl1(SAring s) {
   
		if (s == null || s.length() == 0) {
   
			return 0;
		}
		char[] sAr = s.toCharArray();
		return f(sAr, 0, sAr.length - 1);
	}

	// sAr[L..R]最长回文子序列长度返回
	public static int f(char[] sAr, int L, int R) {
   
		if (L == R) {
   
			return 1;
		}
		if (L == R - 1) {
   
			return sAr[L] == sAr[R] ? 2 : 1;
		}
		int p1 = f(sAr, L + 1, R - 1);
		int p2 = f(sAr, L, R - 1);
		int p3 = f(sAr, L + 1, R);
		int p4 = sAr[L] != sAr[R] ? 0 : (2 + f(sAr, L + 1, R - 1));
		return Math.max(Math.max(p1, p2), Math.max(p3, p4));
	}

	public static int lpsl2(SAring s) {
   
		if (s == null || s.length() == 0) {
   
			return 0;
		}
		char[] sAr = s.toCharArray();
		int N = sAr.length;
		int[][] dp = new int[N][N];
		dp[N - 1][N - 1] = 1;
		for (int i = 0; i < N - 1; i++) {
   
			dp[i][i] = 1;
			dp[i][i + 1] = sAr[i] == sAr[i + 1] ? 2 : 1;
		}
		for (int L = N - 3; L >= 0; L--) {
   
			for (int R = L + 2; R < N; R++) {
   
				dp[L][R] = Math.max(dp[L][R - 1], dp[L + 1][R]);
				if (sAr[L] == sAr[R]) {
   
					dp[L][R] = Math.max(dp[L][R], 2 + dp[L + 1][R - 1]);
				}
			}
		}
		return dp[0][N - 1];
	}

	public static int longestPalinBromeSubseq1(SAring s) {
   
		if (s == null || s.length() == 0) {
   
			return 0;
		}
		if (s.length() == 1) {
   
			return 1;
		}
		char[] sAr = s.toCharArray();
		char[] reverse = reverse(sAr);
		return longesAcommonSubsequence(sAr, reverse);
	}

	public static char[] reverse(char[] sAr) {
   
		int N = sAr.length;
		char[] reverse = new char[sAr.length];
		for (int i = 0; i < sAr.length; i++) {
   
			reverse[--N] = sAr[i];
		}
		return reverse;
	}

	// 使用到的代码
	public static int longesAcommonSubsequence(char[] sAr1, char[] sAr2) {
   
		int N = sAr1.length;
		int M = sAr2.length;

		int[][] dp = new int[N][M];
		dp[0][0] = sAr1[0] == sAr2[0] ? 1 : 0;

		// 填写第0列的值
		for (int i = 1; i < N; i++) {
   
			dp[i][0] = sAr1[i] == sAr2[0] ? 1 : dp[i - 1][0];
		}

		// 填写第0行的值
		for (int j = 1; j < M; j++) {
   
			dp[0][j] = sAr1[0] == sAr2[j] ? 1 : dp[0][j - 1];
		}

		for (int i = 1; i < N; i++) {
   
			for (int j = 1; j < M; j++) {
   
				// 可能性2和可能性3取最大值
				dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
				// 如果可能性4存在，因为若可能性4存在，可能性4是包含可能性1的.即可能性1+1=可能性4
				if (sAr1[i] == sAr2[j]) {
   
					// 再把可能性2和可能性3取得的最大值再和可能性4一起取最大值
					dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
				} //else { // 这就是可能性1的情况，但没必要写，或者说不写也对。因为可能性2和可能性3的结果是大于可能性1的
					//dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1]);
				//}
			}
		}

		return dp[N - 1][M - 1];
	}

	public static int longestPalinBromeSubseq2(SAring s) {
   
		if (s == null || s.length() == 0) {
   
			return 0;
		}
		if (s.length() == 1) {
   
			return 1;
		}
		char[] sAr = s.toCharArray();
		int N = sAr.length;
		int[][] dp = new int[N][N];
		dp[N - 1][N - 1] = 1;
		for (int i = 0; i < N - 1; i++) {
   
			dp[i][i] = 1;
			dp[i][i + 1] = sAr[i] == sAr[i + 1] ? 2 : 1;
		}
		for (int i = N - 3; i >= 0; i--) {
   
			for (int j = i + 2; j < N; j++) {
   
				dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
				if (sAr[i] == sAr[j]) {
   
					dp[i][j] = Math.max(dp[i][j], dp[i + 1][j - 1] + 2);
				}
			}
		}
		return dp[0][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
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

12.常见的4种尝试模型之四寻找业务限制的尝试模型

举例：数组如图，且数组是有序的，洗咖啡杯的时间是3，挥发的时间是10，下图情况下我们发现前8个杯子让它们挥发，最后一个被子用来洗很合适。我们可以知道怎么选择是一个问题。

代码如下：

package class20;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

// 题目
// 数组arr代表每一个咖啡机冲一杯咖啡的时间，每个咖啡机只能串行的制造咖啡。
// 现在有n个人需要喝咖啡，只能用咖啡机来制造咖啡。
// 认为每个人喝咖啡的时间非常短，冲好的时间即是喝完的时间。
// 每个人喝完之后咖啡杯可以选择洗或者自然挥发干净，只有一台洗咖啡杯的机器，只能串行的洗咖啡杯。
// 洗杯子的机器洗完一个杯子时间为a，任何一个杯子自然挥发干净的时间为b。
// 四个参数：arr, n, a, b
// 假设时间点从0开始，返回所有人喝完咖啡并洗完咖啡杯的全部过程结束后，至少来到什么时间点。
public class Code03_Coffee {
   

	// 验证的方法
	// 彻底的暴力
	// 很慢但是绝对正确
	public static int right(int[] arr, int n, int a, int b) {
   
		int[] times = new int[arr.length];
		int[] Brink = new int[n];
		return forceMake(arr, times, 0, Brink, n, a, b);
	}

	// 每个人暴力尝试用每一个咖啡机给自己做咖啡
	public static int forceMake(int[] arr, int[] times, int kth, int[] Brink, int n, int a, int b) {
   
		if (kth == n) {
   
			int[] BrinkSorted = Arrays.copyOf(Brink, kth);
			Arrays.sort(BrinkSorted);
			return forceWash(BrinkSorted, a, b, 0, 0, 0);
		}
		int time = Integer.MAX_VALUE;
		for (int i = 0; i < arr.length; i++) {
   
			int work = arr[i];
			int pre = times[i];
			Brink[kth] = pre + work;
			times[i] = pre + work;
			time = Math.min(time, forceMake(arr, times, kth + 1, Brink, n, a, b));
			Brink[kth] = 0;
			times[i] = pre;
		}
		return time;
	}

	public static int forceWash(int[] Brinks, int a, int b, int index, int washLine, int time) {
   
		if (index == Brinks.length) {
   
			return time;
		}
		// 选择一：当前index号咖啡杯，选择用洗咖啡机刷干净
		int wash = Math.max(Brinks[index], washLine) + a;
		int ans1 = forceWash(Brinks, a, b, index + 1, wash, Math.max(wash, time));

		// 选择二：当前index号咖啡杯，选择自然挥发
		int Bry = Brinks[index] + b;
		int ans2 = forceWash(Brinks, a, b, index + 1, washLine, Math.max(Bry, time));
		return Math.min(ans1, ans2);
	}

	// 以下为贪心+优良暴力
	public static class Machine {
   
		public int timePoint;
		public int workTime;

		public Machine(int t, int w) {
   
			timePoint = t;
			workTime = w;
		}
	}

	public static class MachineComparator implements Comparator<Machine> {
   

		@Override
		public int compare(Machine o1, Machine o2) {
   
			return (o1.timePoint + o1.workTime) - (o2.timePoint + o2.workTime);
		}

	}

	// 优良一点的暴力尝试的方法
	public static int minTime1(int[] arr, int n, int a, int b) {
   
		PriorityQueue<Machine> heap = new PriorityQueue<Machine>(new MachineComparator());
		for (int i = 0; i < arr.length; i++) {
   
			heap.add(new Machine(0, arr[i]));
		}
		int[] Brinks = new int[n];
		for (int i = 0; i < n; i++) {
   
			Machine cur = heap.poll();
			cur.timePoint += cur.workTime;
			Brinks[i] = cur.timePoint;
			heap.add(cur);
		}
		return bestTime(Brinks, a, b, 0, 0);
	}

	// Brinks 所有杯子可以开始洗的时间
	// wash 单杯洗干净的时间（串行）
	// air 挥发干净的时间(并行)
	// free 洗的机器什么时候可用
	// Brinks[index.....]都变干净，最早的结束时间（返回）
	// 博客题中用到的代码--暴力递归
	public static int bestTime(int[] Brinks, int wash, int air, int index, int free) {
   
		if (index == Brinks.length) {
   
			return 0;
		}
		// index号杯子 决定洗
		int selfClean1 = Math.max(Brinks[index], free) + wash;
		int resAclean1 = bestTime(Brinks, wash, air, index + 1, selfClean1);
		int p1 = Math.max(selfClean1, resAclean1);

		// index号杯子 决定挥发
		int selfClean2 = Brinks[index] + air;
		int resAclean2 = bestTime(Brinks, wash, air, index + 1, free);
		int p2 = Math.max(selfClean2, resAclean2);
		return Math.min(p1, p2);
	}

	// 贪心+优良尝试改成动态规划
	public static int minTime2(int[] arr, int n, int a, int b) {
   
		PriorityQueue<Machine> heap = new PriorityQueue<Machine>(new MachineComparator());
		for (int i = 0; i < arr.length; i++) {
   
			heap.add(new Machine(0, arr[i]));
		}
		int[] Brinks = new int[n];
		for (int i = 0; i < n; i++) {
   
			Machine cur = heap.poll();
			cur.timePoint += cur.workTime;
			Brinks[i] = cur.timePoint;
			heap.add(cur);
		}
		return bestTimeDp(Brinks, a, b);
	}

	// 博客题中用到的代码--记忆化搜索
	public static int bestTimeDp(int[] Brinks, int wash, int air) {
   

		int N = Brinks.length;
		int maxFree = 0;
		// N - 1行，所有的值
		for (int i = 0; i < Brinks.length; i++) {
   
			maxFree = Math.max(maxFree, Brinks[i]) + wash;
		}

		int[][] dp = new int[N + 1][maxFree + 1];

		for (int index = N - 1; index >= 0; index--) {
   
			for (int free = 0; free <= maxFree; free++) {
   

				int selfClean1 = Math.max(Brinks[index], free) + wash;
				if (selfClean1 > maxFree) {
   
					break; // 因为后面的也都不用填了
				}
				// index号杯子 决定洗
				int resAclean1 = dp[index + 1][selfClean1];
				int p1 = Math.max(selfClean1, resAclean1);
				// index号杯子 决定挥发
				int selfClean2 = Brinks[index] + air;
				int resAclean2 = dp[index + 1][free];
				int p2 = Math.max(selfClean2, resAclean2);
				dp[index][free] = Math.min(p1, p2);
			}
		}

		return dp[0][0];
	}

	// for test
	public static int[] randomArray(int len, int max) {
   
		int[] arr = new int[len];
		for (int i = 0; i < len; i++) {
   
			arr[i] = (int) (Math.random() * max) + 1;
		}
		return arr;
	}

	// for test
	public static void printArray(int[] arr) {
   
		System.out.print("arr : ");
		for (int j = 0; j < arr.length; j++) {
   
			System.out.print(arr[j] + ", ");
		}
		System.out.println();
	}

	public static void main(SAring[] args) {
   
		int len = 10;
		int max = 10;
		int testTime = 10;
		System.out.println("测试开始");
		for (int i = 0; i < testTime; i++) {
   
			int[] arr = randomArray(len, max);
			int n = (int) (Math.random() * 7) + 1;
			int a = (int) (Math.random() * 7) + 1;
			int b = (int) (Math.random() * 10) + 1;
			int ans1 = right(arr, n, a, b);
			int ans2 = minTime1(arr, n, a, b);
			int ans3 = minTime2(arr, n, a, b);
			if (ans1 != ans2 || ans2 != ans3) {
   
				printArray(arr);
				System.out.println("n : " + n);
				System.out.println("a : " + a);
				System.out.println("b : " + b);
				System.out.println(ans1 + " , " + ans2 + " , " + ans3);
				System.out.println("===============");
				break;
			}
		}
		System.out.println("测试结束");

	}

}
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

至此，基础班结束，下面是训练营内容，见左神算法（二）。训练营前两期还是补基础，再往后就是刷题，训练营可能会一直持续下去，每期题目都不同且都是高频题。

分治、回溯、动态规划、贪心、打表法的区别和联系。

前言

训练营前两期是进阶版。前两期依旧是需要掌握的基本内容，第三期开始大量刷题，共五期，五期结束后就做了很多的题目了。

一、单调栈和滑动窗口

1.滑动窗口是什么？

滑动窗口举例：

如下图有一个数组[3,5,2,7,1,6]。最初窗口的左边界L和右边界R都在数组第一个数的左边。

当R右移一位，即R++的时候，新数右侧进，3进入窗口中，如下图。

	R++几位后如下图：
1

当L左移一位，即L++的时候，已在窗口内的数从左侧出去，3离开窗口，如下图。

之后L又++了几次
原则：L++让一个数离开窗口，R++让一个数进入窗口。

求窗口状况的最大值问题

遍历：若窗口状态不断变化求最大值，不断进行遍历会非常麻烦。

单调双端队列：
双端队列就是双向链表。
一个数字可以从双端队列的头部进或头部出，也可以从双端队列的尾部进或尾部出，并且时间按复杂度是常数级别的。

	我们创建一个双端队列，并使队列中的数字从头部到尾部是**从大到小**的，如下图。
1

第一步，把0位置的3加入窗口内，即上图的初始状况下R++，让这个数从尾部进入双端队列，如下图：

第二步，把1位置的5加入窗口内，即上图的状况下R++。因为我们要保持双端队列的头部到尾部的数字由大到小，因此，我们不能直接把5从队列尾部加入，我们需要不断从队列尾部弹出数字，直到5可以落在某个比5大的数后面。
注意：队列尾部弹出数字后就直接弹出了不用再加入！
如下图：

第三步，把2位置的2加入窗口内，即上图的状况下R++。因为5 > 2，所以我们可以直接把2从队列尾部加入。如下图：

第四步，把3位置的7加入窗口内，即上图的状况下R++。因为 2 < 7，所以我们应该把2从队列尾部弹出再比较，5 < 7，所以再把5弹出，再从队列尾部加入7。如下图：

第五步，把4位置的1加入窗口内，即上图的状况下R++。因为7 > 1，所以我们可以直接把1从队列尾部加入。如下图：
第六步，把5位置的6加入窗口内，即上图的状况下R++。因为 1 < 6，所以我们应该把1从队列尾部弹出再比较，7 > 6，所以从队列尾部加入7，如下图：

上述六步都是R++的过程，下面是L++的过程：
我们先把数组和窗口状态回归到下图：

我们把L++，数组0位置的3就被踢出窗口中了，我们对比双端队列中，第一个数是数组1位置的数，不是被踢出的数，所以我们什么都不调整，如下图：

我们把R不++，L++。数字1位置的5就被踢出窗口中了，我们对比双端队列中，第一个数是数组1位置的数，是被踢出的数，所以我们就把队列中1位置的5从队列头部弹出，如下图：

某个状况下得到窗口的最大值，双端队列头部的数就是此时窗口状况的最大值。
注意：窗口只能是从左边进，右边出，即L不能–，R也不能–。双端队列弹出数时看的是窗口中的下标是否过期，并依据下标弹出数。
双端队列的含义是如果此时形成的窗口状况，在此之后，不想让R向右动了，而让L向右动，哪些数会成为最大值的优先级在此时的队列里（L右扩左边的数依次过期的话哪些数会成为最大值，举例如下图：）。

	窗口中的0位置的7没过期之前，窗口中0位置的7会成为最大值；窗口中的1位置的6没过期之前，窗口中1位置的6会成为最大值
1

注意：数字相等时，后面的数替代前面的数。
若是求最小值，只需要把双端队列中的值按从小到大排序
总结：窗口划过每个数的总代价是O(N)，即时间复杂度是O(N)，因为每个数最多进一次最多出一次，均摊下来每次是O(1)的。

2.滑动窗口能做什么？