网摘一道百度2014年9月25日面试题(题目是网上看到的，代码是自己写的)
来源：程序员人生 发布时间：2014-10-06 08:00:00 阅读次数：1905次
题目：一个char数组只包含a,b,c,d,e五种字符，设计一种算法，找出一个包含五种字符的最小区间【a,b】，数组是循环的(比如区间[9,2]也是可以的).
思路：找到所有含有abcde这五个字符的区间，取最小区间并且记录最小区间的下标。每找到一个含有abcde的区间就记录下，然后把计数数组清0，为了方便下一轮的统计区间长度。
代码如下：
#include <iostream>
#include <time.h>
using namespace std;
const n=10;
char f(int x)
{
char temp=' ';
switch(x)
{
case 1:temp='a';
break;
case 2:temp='b';
break;
case 3:temp='c';
break;
case 4:temp='d';
break;
case 5:temp='e';
break;
}
return temp;
}
void main()
{
srand(unsigned int (time(NULL)));
char a[n]={0};
int count[5]={0},Min=n,j=0,i=0,flag=0,start=0,end=0;
for (i=0;i<n;i++)
{
int x=rand()%5+1;
a[i]=f(x);
cout<<a[i]<<" ";
}
cout<<endl;
cout<<"所有包含所有abcde五个字符的区间为"<<endl;
i=0;
while(j!=n)
{
if (i==n)
{
if (j==0)
{
cout<<"该字符数组内缺少字符！"<<endl;
break;
}
else
{
i=0;
}
}
if (a[i]=='a')
{
count[0]++;
}
else if(a[i]=='b')
{
count[1]++;
}
else if (a[i]=='c')
{
count[2]++;
}
else if(a[i]=='d')
{
count[3]++;
}
else
{
count[4]++;
}
if (count[0]*count[1]*count[2]*count[3]*count[4]!=0)
{
cout<<"["<<j<<","<<i<<"]"<<" ";
if (Min>count[0]+count[1]+count[2]+count[3]+count[4])
{
Min=count[0]+count[1]+count[2]+count[3]+count[4];
start=j;
end=i;
}
count[0]=count[1]=count[2]=count[3]=count[4]=0;
i=j;
j++;
}
i++;
}
cout<<endl;
cout<<"最小区间=["<<start<<","<<end<<"]"<<endl;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
