好未来8.29号技术岗的笔试题（附答案）

1、求二进制中1的个数。

对于一个字节（8bit）的变量，求其二进制表示中“1”的个数，要求算法的执行效率尽可能地高。

2、求子数组的最大和

题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。

因为是O(N)的复杂度，因此需采用的DP的思想，记录下当前元素之和（为其最优状态，既最大），将其与目前所得的最大和比较，若大于则更新，否则继续。状态的累加遵循这个过程：如果当前和小于0，则放弃该状态，将其归零。

答案：

3.关于数组中最长递增子序列，题目如下：
写一个时间复杂度尽可能低的程序，求一个一维数组(N个元素)中最长递增子序列的长度。
例如在序列1,-1,2,-3,4,-5,6,-7中，其最长的递增子序列的长度为4（如1,2,4,6），从该书给的例子我们可以知道的是其最长的递增子序列可以不连续的。

解法一：
根据无后效性的定义，各阶段按照一定的次序排列好之后，对于某个给定阶段的状态来说，它以前各阶段的状态无法直接影响它未来的决策，而只能间接地通过当前状态来影响，如以下目标串：
1，-1，2，-3，4，-5，6，-7
当i=1时，显然，最长的递增序列为(1),序列长度为1.
当i=2时，由于-1<1,因此，必须丢弃第一个值然后重新建立串，当前的递增序列为(-1),长度为1.
当i=3时，由于2>1,2>-1,因此，最长的递增序列为(1,2),(-1,2),长度为2，在这里，2前面是1还是-1对求出后面的递增序列没有直接影响。
假设在目标数组array[]的前i个元素中，最长递增子序列的长度为LIS[i],那么用动态规划可以推出以下公式：
LIS[i+1]=max{1,LIS[k]+1},array[i+1]>array[k],for any k<=i
即如果array[i+1]大于array[k],那么第k+1个元素可以接在LIS[k]长的子序列后面构成一个更长的子序列，同时array[i+1]本身至少可以构成一个长度为1的子序列。
从作者的分析角度，我们可以用树的结构来分析，如图：

代码实现：

#include <iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
int  Max(int *a,int len)
{
int max=1;
for(int i=0;i<len;i++)
if(max<a[i])
max=a[i];
return max;
}
int LIS(int *a,int len)
{
int *LISAry=new int[len];
for(int i=0;i<len;i++)
{
LISAry[i]=1;
//遍历寻找最长递增序列，找到后若比当前i的最长递增序列大，就更改
for(int j=i-1;j>=0;j--)
if(a[i]>a[j]&&LISAry[i]<LISAry[j]+1)
LISAry[i]=LISAry[j]+1;
}
return Max(LISAry,len);
}
int main()
{
int a[8]={1,-1,2,-3,4,-5,6,-7};
int len=sizeof(a)/sizeof(int);
cout <<LIS(a,len)<< endl;
//随机测试
for(int i=0;i<len;i++)
{
for(int j=0;j<len;j++)
{
a[j]=rand()%100+1;
cout<<a[j]<<"\t";
}
cout<<endl<<"result:  "<<LIS(a,len)<<endl;
}
return 0;
}
整个算法的时间复杂度为O(N2N2+N)=O(N2N2).
解法二：
第二种解法：
对于前面i个元素的任何一个递增子序列，如果这个子序列的最大元素比array[i+1]小，那么就可以将array[i+1]加载这个子序列后面构成一个新的递增子序列，假设在数组的前i个元素中，以array[i]为最大元素的最长递增子序列的长度为LIS[i]，同时假设：
长度为1的递增子序列最大元素的最小值为MaxV[1].
长度为2的递增子序列最大元素的最小值为MaxV[2].
………
长度为LIS[i]的递增子序列最大元素的最小值为MaxV[LIS[i]].
根据作者分析可以得到如下的公式：
LIS[i+1]=max{1,K+1},array[i+1]>MaxV[k],k<=maxLISlen,其中maxLISlen表示当前状态最长递增序列的长度
MaxV[len]=min{array[i1i1],array[i2i2],……,array[ikik]}，其中ikik<=N,并且满足LIS[i1i1]=LIS[i2i2]=……..=LIS[ikik]=len.
代码实现：
#include <iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
int Min(int *a,int len)
{
int min=0;
for(int i=0;i<len;i++)
if(a[i]<min)
min=a[i];
}
int LIS(int *a,int len)
{
//存储对应递增序列长度的最大值的最小元素
int *MaxV=new int[len+1];
MaxV[1]=a[0];//数组中的第一值，边界值
MaxV[0]=Min(a,len)-1;//数组中的最小边界值
//存储对应索引的序列长度
int *LISAry=new int[len];
for(int i=0;i<len;i++)
LISAry[i]=1;
int nMaxILS=1;//数组最长递增序列的长度
for(int i=1;i<len;i++)
{
int j;
//利用穷举从后向前寻找第一个小于a[i]元素的索引
for(j=nMaxILS;j>=0;j--)
if(a[i]>MaxV[j])
{
LISAry[i]=j+1;
break;
}
//如果当前递增序列大于最长的递增序列，则更新最长序列
if(LISAry[i]>nMaxILS)
{
nMaxILS=LISAry[i];
MaxV[LISAry[i]]=a[i];
}
//改变该递增序长度的最大元素的值，使其在满足
//同样的递增序列长度情况下，挑选最小元素为最大元素
else if(MaxV[j]<a[i]&&a[i]<MaxV[j+1])
{
MaxV[j+1]=a[i];
}
}
return nMaxILS;
}
int main()
{
int a[8]={1,-1,2,-3,4,-5,6,-7};
int len=sizeof(a)/sizeof(int);
cout <<LIS(a,len)<< endl;
for(int i=0;i<len;i++)
{
for(int j=0;j<len;j++)
{
a[j]=rand()%100+1;
cout<<a[j]<<"\t";
}
cout<<endl<<"result:  "<<LIS(a,len)<<endl;
}
return 0;
}
整个算法过程中也是O(N2N2).
第三种解法：
根据上面的第二种解法思路，可以得到以下推论：
在递增序列，如果i
#include <iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
int Min(int *a,int len)
{
int min=0;
for(int i=0;i<len;i++)
if(a[i]<min)
min=a[i];
}
int LIS(int *a,int len)
{
//存储对应递增序列长度的最大值的最小元素
int *MaxV=new int[len+1];
MaxV[1]=a[0];//数组中的第一值，边界值
MaxV[0]=Min(a,len)-1;//数组中的最小边界值
//存储对应索引的序列长度
int *LISAry=new int[len];
for(int i=0;i<len;i++)
LISAry[i]=1;
int nMaxILS=1;//数组最长递增序列的长度
for(int i=1;i<len;i++)
{
if(a[i]>MaxV[nMaxILS])
{
nMaxILS++;
MaxV[nMaxILS]=a[i];
LISAry[i]=nMaxILS;
}
else
{
int low=1,height=nMaxILS;
//利用二分法寻找从前向后第一个大于a[i]元素的索引
while(low<=height)
{
int mid=low+(height-low)/2;
if(a[i]>=MaxV[mid])
{
low=mid+1;
}
else
{
height=mid-1;
}
}
LISAry[i]=low;
//更新递增序列长度为low其最大元素改为更小的a[i]
MaxV[low]=a[i];
}
}
return nMaxILS;
}
int main()
{
int a[8]={1,-1,2,-3,4,-5,6,-7};
int len=sizeof(a)/sizeof(int);
cout <<LIS(a,len)<< endl;
for(int i=0;i<len;i++)
{
for(int j=0;j<len;j++)
{
a[j]=rand()%100+1;
cout<<a[j]<<"\t";
}
cout<<endl<<"result:  "<<LIS(a,len)<<endl;
}
return 0;
}
整个算法过程时间复杂度是O(N*log2log2N).

4、
给定两个字符串 s1 和 s2, 要求判定 s2 是否能够被通过 s1 作循环移位 ( rotate )得到的字符串包含. 例如, 给定 s1 = AABCD 和 s2 = CDAA, 返回 true; 给定s1 = ABCD 和 s2 = ACBD, 返回 false.
书的作者该出了两种思路：
第一种解法：
用暴力穷举法，穷举s1(如ABCD)做循坏移位所能得到的所有字符串，看其结果是否与s2相等，整个算法过程的时间复杂度为O(N*N*(O(B)))(N为s1的长度，而O(B)为s1匹配子串s2的时间复杂度。)若字符串的长度N比较大，效率很低。
第二种解法：
以S1 = ABCD为例，先分析对S1进行循环移位之后的结果，如下所示：
ABCD—>BCDA—->CDAB—->DABC—->ABCD
假设我们把前面的移走的数据进行保留，会发现有如下的规律：
ABCD—>ABCDA—->ABCDAB—->ABCDABC—->ABCDABCD
因此，可以看出对S1做循环移位所得到的字符串都将是字符串S1S1的子字符串。如果S2可以由S1循环移位得到，那么S2一定在S1S1上，这样时间复杂度就降低了。
代码实现：

#include <iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string>
using namespace std;
int rotateSubString(char *src,char *dec)
{
int len1=strlen(src);
char *c=(char*)malloc(sizeof(char)*2*len1);
//拷贝数据
strcpy(c,src);
//拷贝数据
strcpy(&c[len1],src);
//子串模式匹配
if(strstr(c,dec))
return 1;
else
return 0;
}
void resultPrintf(int result)
{
if(result)
cout << "TURE" << endl;
else
cout << "FALSE" << endl;
}
int main()
{
char *s1="AABCD";
char *s2="CDAA";
resultPrintf(rotateSubString(s1,s2));
s1="ABCD";
s2="ACBD";
resultPrintf(rotateSubString(s1,s2));
return 0;
}
整个算法过程牺牲了空间复杂度来减少时间的复杂度，其时间的复杂度为(O(A)+O(B))(O(A)为拷贝数据的时间，O(B)为字串模式匹配的时间)。

5、给定一棵二叉树的前序遍历和中序遍历，实现一个算法构建这棵二叉树，并打印其后序遍历。