首页 > 代码库 > 笔试算法题(35):最长递增子序列 & 判定一个字符串是否可由另一个字符串旋转得到

笔试算法题(35):最长递增子序列 & 判定一个字符串是否可由另一个字符串旋转得到

出题:求数组中最长递增子序列的长度(递增子序列的元素可以不相连);

分析:

  • 解法1:应用DP之前需要确定当前问题是否具有无后效性,也就是每个状态都是对之前状态的一个总结,之后的状态仅会受到前一个状态的影响;对于递增子序列 而言,可以首先确定前面k个元素的最长子序列,然后计算增加一个元素之后的最长子序列。由于每个位置i都会与0-i的每个位置之前的LIS进行比较,并选 择保持递增的一个序列,所以总能找到LIS,但是时间复杂度为O(N^2),空间复杂度为O(N);
  • 此解法的性能的瓶颈在于对于位置为i+1的元素,都会遍历0到i内的每一个元素,比较元素本身,以及其位置上的record值;但问题的核心是找到一个最长的LIS,并且其序列中最后一个元素的值比array[i+1]小就可以;

解题:

 1 int version1(int *array, int length) {
 2         /**
 3          * record记录每个元素位置之前的LIS数
 4          * */
 5         int *record=new int[length];
 6         for(int i=0;i<length;i++) {
 7                 /**
 8                  * 将当前元素的LIS初始化为1
 9                  * */
10                 record[i]=1;
11                 for(int j=0;j<i;j++) {
12                         /**
13                          * 遍历元素i之前的所有元素j,判断j与i是否组成递增序列
14                          * 如果是,则比较对应的record[j]是否比record[i]大1
15                          * 如果是,则更新record[i]的值为record[j]+1
16                          * 这样的策略则总能保证,record[i]的值是0到i区间最大
17                          * 的LIS
18                          * */
19                         if(array[i]>array[j] && record[j]+1>record[i]) {
20                                 record[i]=record[j]+1;
21                         }
22                 }
23         }
24 
25         /**
26          * 从record中找出最大的LIS
27          * */
28         int max=record[0];
29         for(int i=0;i<length;i++) {
30                 if(max<record[i])
31                         max=record[i];
32         }
33 
34         return max;
35 }
36 
37 int main() {
38         int array[]={1,-8,2,-7,4,-5,6,-4,-3};
39         printf("%d\n",version1(array, 9));
40         return 1;
41 }

 

出题:给定两个字符串S1和S2,要求判定S2是否可以通过S1做循环移位(rotate)得到的新字符串包含。(S1=AABCD和S2=CDAA,就是包含;S1=ABCD和S2=ACBD,不包含);

分析:

  • S2是移位之后的字符串,则S2的第一个字符对应到S1中的字符位置之前的字符肯定已经被rotate到后面;可以首先从S1中查找S2,如果某个字符不 相同,则跳到下一个可能的查找位置;如果S1到达末尾,则rotate前面的字符,继续对比;如果S2到达末尾,则说明包含;如果rotate之后对比的 字符不同,则不包含。此方法时间复杂度为O(MN);
  • 另外一个解法为将S1转变为SS1=AABCDAABCD,这样子在SS1上寻找S2,时间复杂度仍旧为O(MN),其实与上述方法策略相同;

解题:

 1 /**
 2  * 翻转字符串,注意length为字符串长度,
 3  * 而不是字符索引
 4  * */
 5 void Reverse(char *s, int length) {
 6         char temp;
 7         for(int i=0;i<length/2;i++) {
 8                 temp=s[i];
 9                 s[i]=s[length-i-1];
10                 s[length-i-1]=temp;
11         }
12 }
13 /**
14  * 下面的方法实现以s2为分界的旋转,比如
15  * 字符串abcdef,s1指向a,s2指向d
16  * 则经过方法处理之后为defabc
17  * */
18 void HalfReverse(char *s1, char *s2) {
19         char *t=s1;
20         char length=0, halflength=0;
21         while(*t!=\0) {
22                 if(*t==*s2)
23                         halflength=length;
24                 length++;
25                 t++;
26         }
27         Reverse(s1,halflength);
28         Reverse(s2,length-halflength);
29         Reverse(s1,length);
30 };
31 /**
32  * 将s1作为循环主体,每一个字符作为比较的开始字符;
33  * s2平行在s1上移动比较
34  * s1仅可以进行一次旋转
35  * */
36 bool RotateContain(char *s1, char *s2, bool isRotate) {
37         char *s1t=s1, *s2t=s2;
38 
39         while(*s1t) {
40                 char *s1tt=s1t;
41                 char *s2tt=s2t;
42 
43                 while(*s1tt!=\0 && *s2tt!=\0) {
44                         if(*s1tt!=*s2tt)
45                                 break;
46                         s1tt++;s2tt++;
47                 }
48                 /**
49                  * 当s2到达末尾,表示成功匹配,返回true
50                  * */
51                 if(*s2tt==\0)
52                         return true;
53                 /**
54                  * 当s1到达末尾,有两种情况
55                  * 如果isRotate为false,则可以进行一次旋转
56                  * 如果isRotate为true,说明已经进行了一次旋转
57                  * */
58                 if(*s1tt==\0) {
59                         if(isRotate)
60                                 return false;
61                         else {
62                                 isRotate=true;
63                                 HalfReverse(s1, s1t);
64                                 return RotateContain(s1,s2,isRotate);
65                         }
66                 }
67                 s1t++;
68         }
69         return false;
70 }
71 
72 int main() {
73 
74         char s1[]="abcdefg";
75         char s2[]="defgabc";
76         bool isRotate=false;
77         if(RotateContain(s1,s2,isRotate))
78                 printf("true");
79         else
80                 printf("false");
81         return 0;
82 }