问题二
和接近0的子数组
问题描述：
给定一个长度为n的数组，求子数组之和最接近0的子数组
问题举例：
数组：-6，-4，1，5，-8，8，-7
和接近0的子数组：-8，8
思路分析：
这题可以使用前缀和的思想进行思考，因为利用前缀和能对子数组这类问题进行较好的操作，因为如果A[n]代表A数组前n个数的和，那么A[i]-Aj就代表从从j+1到i的数之和，这样就能表示各种子数组的和，而不用多次遍历进行计算。然后我们就可以对前缀和进行排序，这样排序的目的是找出差的绝对值最小的前缀和，我们记为min1，除此之外，我们还得取A中任意一个集合求元素和的最小值，记为min2，最后比较min1和min2的大小，较小的则为所求。
代码实现：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
47public class ZeroSumArray {
private int zeroSum(int[] a){
int[] prefixSum = new int[a.length];
int min1 = 0;
int min2 = 0;
prefixSum[0] = a[0];
for(int i=1;i<a.length;i++){
prefixSum[i] = prefixSum[i-1]+a[i];
}
sort(prefixSum);
int base = prefixSum[1]-prefixSum[0];
for(int i=1;i<prefixSum.length-1;i++){
min1 = prefixSum[i+1]-prefixSum[i];
if(Math.abs(min1)<Math.abs(base)){
base = min1;
}
}
min1 = base;
base = Math.abs(prefixSum[0]);
for(int i=1;i<prefixSum.length;i++){
if(Math.abs(prefixSum[i])<base){
base = Math.abs(prefixSum[i]);
}
min2 = base;
}
return min1>min2?min2:min1;
}
private void sort(int[] a){
for(int i=0;i<a.length-1;i++){
for(int j=0;j<a.length-i-1;j++){
if(a[j]>a[j+1]){
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
public static void main(String[] args) {
ZeroSumArray zsa = new ZeroSumArray();
int[] a = {-6,-4,1,5,-8,8,-7};
System.out.println(zsa.zeroSum(a));
}
}
代码分析：
上述代码主要分成了两部分，包括主逻辑以及排序部分，其中排序部分使用了较为简单的冒泡排序，如果追求更好的时间复杂度可以考虑使用快速排序。至于min1和min2的选择，前缀和代表了0、0+1、0+1+2…，所以在排序后如果有两个前缀和绝对值最小，则可以通过减法得出是哪个范围内的子数组。min2就是前缀和数组中的元素的绝对值的最小值，防止由于两数相加反而导致原本数变大的情况。
问题三：
最长公共子序列
问题描述：
最长公共子序列不同于最长公共子串，子串要求是连续的，而子序列没有连续的要求，只需要保持相对顺序即可。
问题举例：
13455和245576的最长公共子序列为455
acdfg和adfc的最长公共子序列为adf
思路分析：
1、 如果Xm=Yn（最后一个字符相同），则Xm与Yn的最长公共子序列Zk的最后一个字符必定是Xm(=Yn)，也就是Zk=Xm=Yn且容易推导出LCS(Xm,Yn)=LCS(Xm-1,Yn-1)+Xm。
2、 如果Xm≠Yn，那么要么LCS(Xm,Yn)=LCS(Xm-1,Yn)，要么LCS(Xm,Yn)=LCS(Xm,Yn-1)。所以要选出之前的最长子序列，自然是从两者中去最大值，即max{ LCS(Xm-1,Yn), LCS(Xm,Yn-1)}。
综上所述，当Xm=Yn时，LCS(Xm,Yn)=LCS(Xm-1,Yn-1)+xm;当Xm≠Yn时，LCS(Xm,Yn)=max{LCS(Xm-1,Yn), LCS(Xm,Yn-1)}，所以这个问题属于动态规划(DP)问题。
我们可以构造一个长度数组用于存储之前的最长子序列，同时可以构造一个方向数组用于判断之前的数据走向。
上图为长度数组的计算规则，简单来说就是两个序列比较的时候，如果相同则利用左上角的数据的值+1即可，若不同，则选择左方或上方较大的值进行填充，如果左方和上方的值相同则默认选择上方作为方向(左方也可)。
上面这张图在多个地方都有见到，我就以这个为例子进行说明。我们可以看到字符串X是“ABCBDAB”，字符串Y是“BDCABA”。我们先关注这张图的数字部分，可以看到第一行和第一列都是0，这是因为当X或者Y是空序列的时候，自然最长公共子序列就是空或者为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
74public class LongestCommonSubsequence {
private String LCS(String s1,String s2){
int[][] table = new int[s1.length()+1][s2.length()+1];
char[][] mark = new char[s1.length()+1][s2.length()+1];
if(s1.equals(s2)){
System.out.println(s1);
return s1;
}
for (int i=0;i<table.length;i++){
table[i][0] = 0;
}
for (int j=0;j<table[0].length;j++){
table[0][j] = 0;
}
for(int i=1;i<table.length;i++){
for(int j=1;j<table[0].length;j++){
if(s1.charAt(i-1)==s2.charAt(j-1)){
table[i][j] = table[i-1][j-1]+1;
mark[i][j]='↖';
}else{
table[i][j] = max(table[i-1][j],table[i][j-1]);
if(table[i-1][j]<table[i][j-1])
mark[i][j]='←';
else
mark[i][j]='↑';
}
}
}
for (int i=0;i<s1.length()+1;i++){
for(int j=0;j<s2.length()+1;j++){
System.out.print(table[i][j]+" ");
}
System.out.println();
}
for (int i=0;i<s1.length()+1;i++){
for(int j=0;j<s2.length()+1;j++){
System.out.print(mark[i][j]+" ");
}
System.out.println();
}
printLCS(s1,mark,table.length-1,table[0].length-1);
return null;
}
private int max(int a,int b){
return a>b?a:b;
}
private void printLCS(String s1,char[][] mark,int i,int j){
if(i==0||j==0)
return;
while(mark[i][j] == '←'||mark[i][j] =='↑'){
if(mark[i][j] == '←')
j--;
if(mark[i][j] =='↑')
i--;
}
if(mark[i][j] == '↖'){
i--;
j--;
printLCS(s1,mark,i,j);
System.out.print(s1.charAt(i)+" ");
}
}
public static void main(String[] args) {
LongestCommonSubsequence lcs = new LongestCommonSubsequence();
lcs.LCS("ABCBDAB","BDCABA");
}
}
运行结果：
可以看到有三个部分的输出，第一个就是长度数组，右下角代表了LCS的数值是4，第二个是方向数组，能够看到数据的走向，最后一个就是输出的LCS的一个解，LCS可能有多个解，但是其长度为固定的。
代码分析：
这次的代码主要分为两个部分，第一个部分是主逻辑部分，按照之前的分析，我首先定义了两个数组用于存放长度数据和方向数据，并且对两个序列完全相等的情况进行了预处理，之后就对第一行和第一列进行了初始化，设置为0。之后使用了一个双层循环实现了长度数组中有关数据求法的要求，主逻辑结束。之后一个部分就是输出部分(printLCS)，我们从长度数组的右下角出发，通过判断其是否来自于左上角，对其进行判断，如果发现其数据来自左方或上方，则进行循环，跳过这些数据，只对标记为左上角的数据进行输出，并且在输出的时候使用了递归进行，比较清晰。