华为机试题-2014校园招聘

时间：2022-08-01 18:54:00

1、通过键盘输入一串小写字母(a~z)组成的字符串。请编写一个字符串过滤程序，若字符串中出现多个相同的字符，将非首次出现的字符过滤掉。比如字符串“abacacde”过滤结果为“abcde”。

要求实现函数格式：void stringFilter(const char *pInputStr, long lInputLen, char *pOutputStr);

pOutputStr： 输出字符串，空间已经开辟好，与输入字符串等长;

使用长度为26的bool数组标记字母的出现

void stringFilter(const char *pInputStr, long lInputLen, char *pOutputStr)
{
	bool flag[26] = {0};
	int i,j=0;

	if(pInputStr==NULL)
		return;

	for(i=0;i<lInputLen;i++)
	{
		int tmp = pInputStr[i]-'a';
		if(tmp>26 || tmp<0)
			return;

		if(flag[tmp]==0)
		{
			flag[tmp] = 1;
			pOutputStr[j] = pInputStr[i];
			j++;
		}
	}
}
void test_huawei()
{
	char pInputStr[50];
	char pOutputStr[50] = "";
	cout<<"请输入待过滤字符串\n"<<endl;
	cin>>pInputStr;
//	cout<<pInputStr<<endl;
	int len = strlen(pInputStr);

	stringFilter(pInputStr,len,pOutputStr);
	cout<<"过滤后字符串："<<pOutputStr<<endl;
}



2、通过键盘输入一串小写字母(a~z)组成的字符串。请编写一个字符串压缩程序，将字符串中连续出席的重复字母进行压缩，并输出压缩后的字符串（重复次数+字母）。

函数格式：void stringZip(const char *pInputStr, long lInputLen, char *pOutputStr);

void stringZip(const char *pInputStr, long lInputLen, char *pOutputStr)
{
	if(pInputStr==NULL)
		return;

	int count = 1, i, j = 0;
	for(i=0;i<lInputLen-1;i++)
	{
		int tmp = pInputStr[i]-'a';
		if(tmp>26 || tmp<0)
			return;

		if(pInputStr[i+1]==pInputStr[i])
		{
			++count;
		}
		else
		{
			if(count>1)
			{
				pOutputStr[j] = '0'+count;
				pOutputStr[j+1] = pInputStr[i];
				j += 2;
				count = 1;
			}
			else
			{
				pOutputStr[j] = pInputStr[i];
				j++;
			}
		}
	}
	pOutputStr[j] = pInputStr[i];
}
void test2()
{
	char pInputStr[50];
	char pOutputStr[50] = "";
	cout<<"请输入待压缩字符串\n"<<endl;
	cin>>pInputStr;
	int len = strlen(pInputStr);

	stringZip(pInputStr,len,pOutputStr);
	cout<<"压缩后字符串输出："<<pOutputStr<<endl;
}


3、通过键盘输入100以内正整数的加、减运算式，请编写一个程序输出运算结果字符串。输入字符串的格式为：“操作数1 运算符 操作数2”，“操作数”与“运算符”之间以一个空格隔开。如果输入格式错误，则输出0

函数格式：void arithmetic(const char *pInputStr, long lInputLen, char *pOutputStr);

void arithmetic(const char *pInputStr, long lInputLen, char *pOutputStr)
{
	if(pInputStr==NULL)
		return;

	//实现数字和字符的分离，并存储
	int i, j=0, number1=0, number2=0,len=strlen(pInputStr);
	int flag1 = 0;   //区分两个整数和符号
	int flag2 = 0;   //区分‘+’、‘-’
	int flag3 = 0;   //记录运算符号出现的次数
	for(i=0;i<len;i++)
	{
		if(pInputStr[i]!=' ')
		{
			if(flag1==0)   //分离出第一个正整数
			{
				int tmp = pInputStr[i]-'0';
				if(tmp>9 || tmp<0)   //格式检查
				{
					pOutputStr[j] = '0';
					return;
				}
				number1 = 10*number1+tmp;
			}
			if(flag1==1)   //分离出“+ -”号
			{
				if(flag3==0)   //格式检查，第一次出现运算符
				{
					if(pInputStr[i]=='+')
						flag2 = 1;
					if(pInputStr[i]=='-')
						flag2 = 2;
					if(flag2==0)   //输入格式检查
					{
						pOutputStr[i] = '0';
						return;
					}
					flag3++;
				}
				else   //出现多个运算符
				{
					pOutputStr[j] = '0';
					return;
				}

			}
			if(flag1==2)
			{
				if(flag2!=0)   //格式检查，保证已经出现运算符
				{
					int tmp = pInputStr[i]-'0';
					if(tmp>9 || tmp<0)   //格式检查
					{
						pOutputStr[j] = '0';
						return;
					}
					number2 = 10*number2+tmp;
				}
				else  //格式检查
				{
					pOutputStr[j] = '0';
					return;
				}
			}
		}
		else   //记录空格出现
		{
			flag1++;
		}
	}

	//计算
	int result = 0;
	if(flag2==1)
	{
		result = number1+number2;
	}
	if(flag2==2)
	{
		result = number1-number2;
	}

	while(result)
	{
		pOutputStr[j] = '0'+result%10;
		result /= 10;
		j++;
	}
}
void test3()
{
	char pInputStr[10];
	char pOutputStr[5] = "";
	cout<<"请输入待运算表达式\n"<<endl;
//	cin>>pInputStr;   //cin不能录空格
	cin.getline(pInputStr,10);
	int lInputLen = strlen(pInputStr);

	arithmetic(pInputStr,lInputLen,pOutputStr);

	cout<<pInputStr<<"=";
	long len1 = strlen(pOutputStr);
	for(int i=len1-1;i>=0;i--)
	{
		cout<<pOutputStr[i];
	}
	cout<<endl;
}


高级题

已知2条地铁线路，其中A为环线，B为东西向线路，线路都是双向的。经过的站点名分别如下，两条线交叉的换乘点用T1、T2表示。编写程序，任意输入两个站点名称，输出乘坐地铁最少需要经过的车站数量（含输入的起点和终点，换乘站点只计算一次）。
地铁线A（环线）经过车站：a1 a2 a3 a4 a5 a6 a7 a8 a9 t1 a10 a11 a12 a13 t2 a14 a15 a16 a17 a18

地铁线A（直线）经过车站：b1 b2 b3 b4 b5 b1 b6 b7 b8 b9 b10 t2 b11 b12 b13 b14 b15

#include<cstring>
#include<iostream>
#include<string>

using namespace std;
const int inf = 0x5F5F5F5F;
struct Graph
{
	char point[35][4];
	int edges[35][35];
};

char s1[21][4] = {"a1","a2","a3","a4","a5","a6","a7","a8","a9","t1","a10","a11","a12","a13","t2","a14","a15","a16","a17","a18","a1"};
char s2[17][4] = {"b1","b2","b3","b4","b5","t1","b6","b7","b8","b9","b10","t2","b11","b12","b13","b14","b15"};
char v[35][4] = {"a1","a2","a3","a4","a5","a6","a7","a8","a9","t1","a10","a11","a12","a13","t2","a14","a15","a16","a17","a18","b1","b2","b3","b4","b5","b6","b7","b8","b9","b10","b11","b12","b13","b14","b15"};

//void *memcpy(void *dest, const void *src, size_t n);
//需要#include<cstring>或#include<string.h>
void CreateGraph(Graph * &G)
{
	int i,j,k;
	for(i=0;i<35;i++)
	{
		memcpy(G->point[i],v[i],sizeof(v[i]));
	}
	for(i=0;i<35;i++)
	{
		for(j=0;j<35;j++)
		{
			G->edges[i][j] = inf;
		}
	}
	for(k=0;k<20;k++)
	{
		for(i=0;strcmp(s1[k],G->point[i])!=0;i++);
		for(j=0;strcmp(s1[k+1],G->point[j])!=0;j++);
		G->edges[i][j] = 1;
		G->edges[j][i] = 1;
	}
	for(k=0;k<16;k++)
	{
		for(i=0;strcmp(s2[k],G->point[i])!=0;i++);
		for(j=0;strcmp(s2[k+1],G->point[j])!=0;j++);
		G->edges[i][j] = 1;
		G->edges[j][i] = 1;
	}
}
//Floyd-Warshall算法的时间复杂度为O(N^3)，空间复杂度为O(N^2)
void Floyed(Graph * &G)
{
	int i,j,k;
	for(k=0;k<35;k++)
	{
		for(i=0;i<35;i++)
		{
			for(j=0;j<35;j++)
			{
				if(G->edges[i][k]+G->edges[k][j]<G->edges[i][j])
					G->edges[i][j] = G->edges[i][k]+G->edges[k][j];
			}
		}	
	}		
}

void query(Graph *G)  
{  
    char s1[4],s2[4];  
    int i,j;  
    cout<<"请输入起点站与终点站"<<endl;  
    cin>>s1>>s2;  
    for (i = 0;strcmp(s1,G->point[i])!=0;i++);                              
    for (j = 0;strcmp(s2,G->point[j])!=0;j++);  
    cout<<G->edges[i][j]<<endl;  
} 


int main()
{
	Graph *G = new Graph;
	CreateGraph(G);
	Floyed(G);
	while(1)
	{
		query(G);
	}
	system("pause");
	return 0;
}


标签：

相关文章