新建 文本文档.txt

一份迅雷的笔试题

今天在家看碟，突然接到迅雷一个电话让我去笔试。遇到两个很有意思的题目，现有奖征集第一题的答案：B1套餐一份。
    1.<征集答案>给你10台机器，每个机器2个cpu，2g内存，现在已知在10亿条记录的数据库里执行一次查询需要5秒，问用什么方法能让90%的查询能在100毫秒以内返回结果。
    2.一个长度为10000的字符串，写一个算法，找出最长的重复子串，如abczzacbca,结果是bc。最后就做出这一道题目，时间复杂度为O(n!), 空间复杂度为O(n)。如果有更好的算法，还请指教。




第二题的另一种解法：
char* straddr[10000];
straddr[i] = &str[i];//0<=i<=9999
for (i=0; i<9999; i++)
  for (j=i+1; j<9999; j++)
  {
    tcomlen = comlen (stradddr[i], stradddr[j]);
    if(maxcomlen<tcomlen)
       maxcomlen = tcomlen;
   }
return maxcomlen;
O(n^2)
 














迅雷笔试题
/*定义循环左移函数(我没有用左移函数)*/
{
int i,j;
char temp=str[0];
for (i=0;i<m;i++) str[i]=str[i+1];
str[i]=temp;
}
void pai(char str[],int m,int n) /*定义全排列函数*/
{
int k;
void chang(char str[],int m);
if (m<n) /* 定 义 递 归 调 用 出 口 */
{
for (k=0;k<=m;k++)
{
pai(str,m+1,n); /*递归调用*/
chang(str,m); /*调用左移函数*/
}
}
else printf("%s\t",str);
}
#include "stdio.h"
main()
{char str[]="ABCD";
/*全排列字符,可以任意多个(相应的下面排列函数中参数"4"改成全排列字符的个数)*/
clrscr();
pai(str,0,4);
/*这里参数0(下标)表示从第一个元素开始,4表示元素个数(不是下标)*/
getch(); 转贴请注明：www.pghome.net 志远工作室
}
/*********************************************/
下面我来解释一下,我花了近1天的时间,找到这样一个规律如下:
┏ ABCD
┣ BCDA
┏ ABCD ━┫
┃ ┣ CDAB
┏ ABCD ━╋ BCAD ┗ DABC
┃ ┃ .
┃ ┗ CABD .
ABCD ━┫ .
┃ ┏ BACD .
┃ ┃ .
┗ BACD ━╋ ACBD ┏ CBAD
┃ ┣ BADC
┗ CBAD ━┫
┣ ADCB
┗ DCBA
简化图如下所示 ==>
┏ ABCD
┣ BCDA
┏ ABC ━┫
┃ ┣ CDAB
┏ AB ━╋ BCA ┗ DABC
┃ ┃ .
┃ ┗ CAB .
A ━┫ .
┃ ┏ BAC .
┃ ┃ .
┗ BA ━╋ ACB ┏ CBAD
┃ ┣ BADC
┗ CBA ━┫
┣ ADCB
┗ DCBA

┏ ABCD
┣ BCDA
┏ ABCD ━┫
┃ ┣ CDAB
┏ ABCD ━╋ BCAD ┗ DABC
┃ ┃ .
┃ ┗ CABD .
ABCD ━┫ .
┃ ┏ BACD .
┃ ┃ .
┗ BACD ━╋ ACBD ┏ CBAD
┃ ┣ BADC
┗ CBAD ━┫
┣ ADCB
┗ DCBA
简化图如下所示 ==>
┏ ABCD
┣ BCDA
┏ ABC ━┫
┃ ┣ CDAB
┏ AB ━╋ BCA ┗ DABC
┃ ┃ .
┃ ┗ CAB .
A ━┫ .
┃ ┏ BAC .
┃ ┃ .
┗ BA ━╋ ACB ┏ CBAD
┃ ┣ BADC
┗ CBA ━┫
┣ ADCB
┗ DCBA
#include <stdio.h>
#include <stdlib.h>
char used[20]={0};
int number[20], len, i, p[20];
void output()
{
printf("\n");
for(i=0; i<len; ++i)
printf("%d ", number[p[i]]);
}
int pailie(int n)
{
int ii;
if(n==len)
output( );
for(ii=0; ii<len; ++ii)
if(!used[ii]){
used[ii] = 1;
p[n] = ii;
pailie(n+1);
used[ii] = 0;
}
return 0;
}
int main(int argc, char *argv[])
{
int index = 0;
scanf("%d", &len);
while(index<len)
scanf("%d", &number[index++]);
pailie(0);
return 0;
}
=====================================================================
#include <stdio.h>
#include <stdlib.h>
int number[20], len, temp;
void output()
{
int i;
printf("\n");
for(i=0; i<len; ++i)
printf("%d ", number[i]);
}
int pailie(int n)
{
int ii;
if(n==len)
output( );
for(ii=n; ii<len; ++ii){
temp = number[ii]; number[ii] = number[n]; number[n] = temp;
pailie(n+1);
temp = number[ii]; number[ii] = number[n]; number[n] = temp;
}
return 0;
}
int main(int argc, char *argv[])
{
int index = 0;
scanf("%d", &len);
while(index<len)
scanf("%d", &number[index++]);
pailie(0);
return 0;
}
=====================================================================
#include<stdio.h>
const int maxlen=9;
int num[9]={1,2,3,4,5,6,7,8,9};
void pailie()
{
int fenjie,i,j,k=maxlen-1,t;
char bb=1;
while(bb)
{
i=0;
while(i<=k)
printf("%d", num[i++]);
putchar('\n');
fenjie=k;
while(fenjie>0 && num[fenjie-1]>num[fenjie])
fenjie--;
if(fenjie)
{
j=k;
while(num[j]<num[fenjie-1])
j--;
i=num[j]; num[j]=num[fenjie-1]; num[fenjie-1]=i;
i=fenjie+k;
for(j=fenjie; j<=i/2; j++){
t=num[j];
num[j]=num[i-j];
num[i-j]=t;
}
}
else
bb=0;
}
}
==========================================================================
#include <stdio.h>
int num[]={12,12,14,14};
int main( void)
{
int fenjie, i, j, t, maxlen=4, k=maxlen-1;
char bb=1;
while(bb)
{
i=0;
while(i<k)
printf("%d ", num[i++]);
printf("%d\n", num[i++]);
fenjie=k;
while(fenjie>0 && num[fenjie-1] >= num[fenjie])
fenjie--;
if(fenjie){
j=k;
while(num[j]<=num[fenjie-1])
j--;
i=num[j]; num[j]=num[fenjie-1]; num[fenjie-1]=i;
i=fenjie+k;
for(j=fenjie;j<=i/2;j++){
t=num[j];
num[j]=num[i-j];
num[i-j]=t;
}
}
else
bb=0;
} 转摘请注明：www.pghome.net
}
=========================================================================
其实STL的排列算法不错的