还有一年就要找工作了，从现在开始找些公司的数据结构和算法的题来做一做，不定时贴出笔试面试题代码。
1.创新工场：
求一个数组的最长递减子序列比如{9，4，3，2，5，4，3，2}的最长递减子序列为{9，5，4，3，2}
算法描述:
1. 对原序列进行递减排序（选择快速排序法）；
2. 删掉重复数字；
3. 得到子序列。
C++源代码：
#include "stdafx.h"
#include <iostream>
using namespace std;
#define MAX_SIZE 20
void FastSort(int a[],int left,int right)
{
if(left< right)
{
inti = left,j = right,k;
inttemp = 0;
temp= a[left];
while(i< j)
{
while(j>i&&a[j]<temp)
j--;
a[i]= a[j];
while(i<j&&a[i]>= temp)
i++;
a[j]= a[i];
};
a[i]= temp;
FastSort(a,left,i-1);
FastSort(a,i+1,right);
}
}
void GetChildSet(int a[],int p[],intn,int& length)
{
length= 0;
intcount = 0,i,j;
inttemp[MAX_SIZE] = {0};
for(j=0;j<n;j++)
if(a[j]==a[j+1])
{
temp[j+1]=1;
count++;
}
for(i=0,j=0;i<n,j<n-count;i++)
if(0==temp[i])
{
p[j]=a[i];
j++;
}
length= n-count;
}
int main(int argc, char* argv[])
{
inta[MAX_SIZE] = {4,8,9,41,11,14,4,25,36,2,1,1,4,8,58,44,44,12,12,39};
intlength = 0;
FastSort(a,0,MAX_SIZE-1);
intp[MAX_SIZE];
GetChildSet(p,a,MAX_SIZE,length);
for(inti=0;i<length;i++)
cout<<p[i]<<endl;
return0;
}
运行结果：
2将一整数序列逆序（要求递归实现）
算法描述:
1当满足first<last时直接交换序列首位和末尾位元素；
2.递归调用(注意递归退出条件：必须是变量first大于或等于last)
C++源代码：
#include "stdafx.h"
#include <iostream>
using namespace std;
#define MAX_SIZE 10
void Conver(int a[],int first,int last)
{
inttemp = a[first];
if(first== last||first > last)
return;
elseif(first<last)
{
a[first]= a[last];
a[last]= temp;
}
Conver(a,first+1,last-1);
}
int main(int argc, char* argv[])
{
inta[MAX_SIZE] = {1,2,3,4,5,6,7,8,9,10};
Conver(a,0,9);
for(inti = 0;i < MAX_SIZE;i++)
cout<<a[i]<<endl;
}
运行结果：
3将一整数逆序后放入一数组中（要求递归实现）如：12345逆置后为54321
算法描述:
1分割出整数的每一个位，方法n%10；
2.每一次分割都是得到整数最后一个位，数组索引值要从第0开始
C++源代码：
#include "stdafx.h"
#include <stdio.h>
void convert(int *result, int n)
{
if(n>=10)
convert(result+1, n/10);
*result = n%10;
}
int main(int argc, char* argv[])
{
int n = 123456789;
int *result = new int[10];
convert(result, n);
printf("%d:", n);
for(int i=0; i<9; i++)
printf("%d", result[i]);
printf("\n");
}
运行结果：
4 递归实现回文判断（如：abcdedbca就是回文，判断一个面试者对递归理解的简单程序）
算法描述:
与求一个序列的转置类似。
C++源码
#include "stdafx.h"
#include <stdio.h>
bool Fun(char *s, int first,int last)
{
if(first< last)
if(s[first]== s[last])
{
Fun(s,first+1,last-1);
}
else
returnfalse;
elseif(first > last)
returnfalse;
else
returntrue;
}
int main(int argc, char* argv[])
{
char*s = "abcdedcba";
if(Fun(s,0,8))
printf("%sis plalindrome!",s);
else
printf("%sisn't plalindrome!",s);
printf("\n");
}
运行结果：
5 华为笔试
分解成质因数(如435234=251*17*17*3*2)
算法描述：
1 寻找一个整数的质因数方法从2开始遍历，依次查找
C++源代码：
#include "stdafx.h"
#include <stdio.h>
void Prime(int m,int n)
{
if(n<m||n==m)
{
while(m%n!=0)
n++;
m/= n;
printf("%d*",n);
Prime(m,n);
}
elsereturn;
}
int main(int argc, char* argv[])
{
intn = 1000;
printf("%d=",n);
Prime(n,2);
printf("\n");Prime(1000,2);
printf("\n");
}
运行效果：
