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

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

2024-07-06 01:15:42   216人阅读

出题：求数组中最长递增子序列的长度（递增子序列的元素可以不相连）；

分析：

  • 解法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 }

 


联系
我们