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

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

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

分析：

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

解题：

int version1(int *array, int length) {
/**
* record记录每个元素位置之前的LIS数
* */
int *record=new int[length];
for(int i=;i<length;i++) {
/**
* 将当前元素的LIS初始化为1
* */
record[i]=;
for(int j=;j<i;j++) {
/**
* 遍历元素i之前的所有元素j，判断j与i是否组成递增序列
* 如果是，则比较对应的record[j]是否比record[i]大1
* 如果是，则更新record[i]的值为record[j]+1
* 这样的策略则总能保证，record[i]的值是0到i区间最大
* 的LIS
* */
if(array[i]>array[j] && record[j]+>record[i]) {
record[i]=record[j]+;
}
}
} /**
* 从record中找出最大的LIS
* */
int max=record[];
for(int i=;i<length;i++) {
if(max<record[i])
max=record[i];
} return max;
} int main() {
int array[]={,-,,-,,-,,-,-};
printf("%d\n",version1(array, ));
return ;
}

出题：给定两个字符串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)，其实与上述方法策略相同；

解题：

/**
* 翻转字符串，注意length为字符串长度，
* 而不是字符索引
* */
void Reverse(char *s, int length) {
char temp;
for(int i=;i<length/;i++) {
temp=s[i];
s[i]=s[length-i-];
s[length-i-]=temp;
}
}
/**
* 下面的方法实现以s2为分界的旋转，比如
* 字符串abcdef，s1指向a，s2指向d
* 则经过方法处理之后为defabc
* */
void HalfReverse(char *s1, char *s2) {
char *t=s1;
char length=, halflength=;
while(*t!='\0') {
if(*t==*s2)
halflength=length;
length++;
t++;
}
Reverse(s1,halflength);
Reverse(s2,length-halflength);
Reverse(s1,length);
};
/**
* 将s1作为循环主体，每一个字符作为比较的开始字符；
* s2平行在s1上移动比较
* s1仅可以进行一次旋转
* */
bool RotateContain(char *s1, char *s2, bool isRotate) {
char *s1t=s1, *s2t=s2; while(*s1t) {
char *s1tt=s1t;
char *s2tt=s2t; while(*s1tt!='\0' && *s2tt!='\0') {
if(*s1tt!=*s2tt)
break;
s1tt++;s2tt++;
}
/**
* 当s2到达末尾，表示成功匹配，返回true
* */
if(*s2tt=='\0')
return true;
/**
* 当s1到达末尾，有两种情况
* 如果isRotate为false，则可以进行一次旋转
* 如果isRotate为true，说明已经进行了一次旋转
* */
if(*s1tt=='\0') {
if(isRotate)
return false;
else {
isRotate=true;
HalfReverse(s1, s1t);
return RotateContain(s1,s2,isRotate);
}
}
s1t++;
}
return false;
} int main() { char s1[]="abcdefg";
char s2[]="defgabc";
bool isRotate=false;
if(RotateContain(s1,s2,isRotate))
printf("true");
else
printf("false");
return ;
}

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

Libre 6005 「网络流 24 题」最长递增子序列 / Luogu 2766 最长递增子序列问题（网络流，最大流）
Libre 6005 「网络流 24 题」最长递增子序列 / Luogu 2766 最长递增子序列问题(网络流,最大流) Description 问题描述: 给定正整数序列x1,...,xn . (1 ...
【刷题】LOJ 6005 「网络流 24 题」最长递增子序列
题目描述给定正整数序列 \(x_1 \sim x_n\) ,以下递增子序列均为非严格递增. 计算其最长递增子序列的长度 \(s\) . 计算从给定的序列中最多可取出多少个长度为 \(s\) 的递增子 ...
算法之动态规划(最长递增子序列——LIS）
最长递增子序列是动态规划中最经典的问题之一,我们从讨论这个问题开始,循序渐进的了解动态规划的相关知识要点. 在一个已知的序列 {a1, a 2,...an}中,取出若干数组成新的序列{ai1, ai ...
【PowerOJ1741&amp&semi;网络流24题】最长递增子序列问题（最大流）
题意: 思路: [问题分析] 第一问时LIS,动态规划求解,第二问和第三问用网络最大流解决. [建模方法] 首先动态规划求出F[i],表示以第i位为开头的最长上升序列的长度,求出最长上升序列长度K. ...
[cogs731] [网络流24题&num;6] 最长递增子序列 [网络流，最大流]
[转hzwer]第一问是LIS,动态规划求解,第二问和第三问用网络最大流解决.首先动态规划求出F[i],表示以第i位为开头的最长上升序列的长度,求出最长上升序列长度K.1.把序列每位i拆成两个点&lt ...
最长公共子序列（LCS）和最长递增子序列（LIS）的求解
一.最长公共子序列经典的动态规划问题,大概的陈述如下: 给定两个序列a1,a2,a3,a4,a5,a6......和b1,b2,b3,b4,b5,b6.......,要求这样的序列使得c同时是这两个 ...
C++ 求最长递增子序列（动态规划）
i 0 1 2 3 4 5 6 7 8 a[i] 1 4 7 2 5 8 3 6 9 lis[i] 1 2 3 2 3 4 3 4 5 时间复杂度为n^2的算法: //求最长递增子序列 //2019/ ...
Cogs 731&period; [网络流24题] 最长递增子序列(最大流)
[网络流24题] 最长递增子序列 ★★★☆ 输入文件:alis.in 输出文件:alis.out 简单对比时间限制:1 s 内存限制:128 MB «问题描述: 给定正整数序列x1,-, xn. ( ...
（转载）最长递增子序列 O(NlogN)算法
原博文:传送门最长递增子序列(Longest Increasing Subsequence) 下面我们简记为 LIS. 定义d[k]:长度为k的上升子序列的最末元素,若有多个长度为k的上升子序列,则 ...

随机推荐

windows批处理的介绍
扩展名是bat(在nt/2000/xp/2003下也可以是cmd)的文件就是批处理文件. 首先批处理文件是一个文本文件,这个文件的每一行都是一条DOS命令(大部分时候就好象我们在DOS提示符下执行的命 ...
zookeeper学习系列：四、Paxos算法和zookeeper的关系
一.问题起源淘宝搜索的博客 http://www.searchtb.com/2011/01/zookeeper-research.html 提到Paxos是zookeeper的灵魂有一篇文章标题 ...
UpdatePane中弹出框
ScriptManager.RegisterClientScriptBlock(this.UpdatePanel21, typeof(UpdatePanel), "提示",&quo ...
SQL的多表操作
多表更新: 假定我们有两张表,一张表为Product表存放产品信息,其中有产品价格列Price:另外一张表是ProductPrice表,我们要将ProductPrice表中的价格字段Price更新为P ...
centos7安装VLC播放器
centos7安装VLC播放器 1.安装eple 下载地址:https://dl.fedoraproject.org/pub/epel/7/x86_64/e/epel-release-7-5.noar ...
智齿客服网页端接入文档V2&period;3
产品介绍智齿客服网页端接入提供以下两种部署方式. 一.网页组件(推荐) 通过智齿客服网站咨询组件,企业的用户可快捷联系到企业客服获取帮助.智齿客服网页组件提供强大的用户行为采集能力和系统对接能力,支 ...
JavaWeb基础-servlet
Servlet简介 Sun公司在其API中提供了一个servlet接口,用户若想用发一个动态web资源(即开发一个Java程序向浏览器输出数据),需要完成以下2个步骤: 1.编写一个Java类,实现s ...
（原）PyTorch中使用指定的GPU
转载请注明出处: http://www.cnblogs.com/darkknightzh/p/6836568.html PyTorch默认使用从0开始的GPU,如果GPU0正在运行程序,需要指定其他G ...
对象不能从 DBNull 转换为其他类型
SQL语句:select sum (datediff(second,Begin_Time,End_Time)) as 总时长 from 数据表这是我开始的程序:int 总时长=0;总时长 =Conve ...
jQuery2&period;0应用开发&colon;SSH框架整合jQuery2&period;0实战OA办公自己主动化(VSS、operamasks-UI框架)
我的qq是2059055336,对这个课程有兴趣的能够加我qq联系. 一.本课程是怎么样的一门课程(全面介绍) 1.1.课程的背景 jQuery 2.0 正式版公布.不在支持 IE 6/7/8 ...