学步园

89.神州数码、华为、东软笔试题
1.2005 年 11 月 15 日华为软件研发笔试题。实现一单链表的逆转。
2.编码实现字符串转整型的函数（实现函数 atoi 的功能），据说是神州数码笔试题。如将字
符串  ”+123”123,  ”-0123”- 123,  “123CS45”123,  “123.45CS”123,  “CS123.45”
0
3.快速排序（东软喜欢考类似的算法填空题，又如堆排序的算法等）
4.删除字符串中的数字并压缩字符串。
如字符串”abc123de4fg56”处理后变为”abcdefg”。注意空间和效率。
（下面的算法只需要一次遍历，不需要开辟新空间，时间复杂度为 O(N)）
5.求两个串中的第一个最长子串（神州数码以前试题）。 

如"abractyeyt","dgdsaeactyey"的最大子串为"actyet"。

1.2005 年 11 月 15 日华为软件研发笔试题。实现一单链表的逆转。

已实现：同24 ：http://blog.csdn.net/u012605629/article/details/39377099

2.编码实现字符串转整型的函数（实现函数 atoi 的功能），据说是神州数码笔试题。如将字
符串  ”+123”123,  ”-0123”- 123,  “123CS45”123,  “123.45CS”123,  “CS123.45”
0

/*
89.神州数码、华为、东软笔试题
2.编码实现字符串转整型的函数（实现函数 atoi  的功能），据说是神州数码笔试题。如将字
符串”+123”123,  ”- 0123”-123,  “123CS45”123,  “123.45CS”123,  “CS123.45”0

整型 用int 题目简单 
*/
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

int atoi(char* a) 
{
	if (*a=='+')
		return atoi(a+1);
	else if(*a=='-') 
		return -atoi(a+1);
		
	char *p=a;
	int ans=0;
	while(*p>='0'&&*p<='9') 
	{
		ans=ans*10+(*p-'0');
		p++;
	}
	return ans;
}
int main()
{
	
	char a[]={"+123"};
	printf("%s:符串转整型为：%d\n",a,atoi(a)); 
	
	char b[]={"-123"};
	printf("%s:符串转整型为：%d\n",b,atoi(b)); 
	
	char c[]={"123CS45"};
	printf("%s:符串转整型为：%d\n",c,atoi(c)); 
	
	char d[]={"123.45CS"};
	printf("%s:符串转整型为：%d\n",d,atoi(d)); 
	
	char e[]={"CS123.45"};
	printf("%s:符串转整型为：%d\n",e,atoi(e));
	return 0;
} 

3.快速排序（东软喜欢考类似的算法填空题，又如堆排序的算法等）

已实现：http://blog.csdn.net/u012605629/article/details/39457021

4.删除字符串中的数字并压缩字符串。
如字符串”abc123de4fg56”处理后变为”abcdefg”。注意空间和效率。
（下面的算法只需要一次遍历，不需要开辟新空间，时间复杂度为 O(N)）

/*
4.删除字符串中的数字并压缩字符串。如字符串” abc123de4fg56”处理后变为” abcdefg”。
注意空间和效率。（下面的算法只需要一次遍历，不需要开辟新空间，时间复杂度为 O(N)）

so easy
*/
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

char* partition(char* str) 
{
	char *i=str; 
	char *j=str;
	while (*i!='\0') 
	{
		if (*i>'9'||*i<'0')//非数字 
			*j++=*i++;
		else 
			*i++;	
	}
	*j ='\0';
	return str;
}

int main()
{
	char a[]={"abc123de4fg56"};
	printf("%s",a); 
	printf("压缩后为：%s\n",partition(a)); 
	return 0;
} 

5.求两个串中的第一个最长子串（神州数码以前试题）。 

如"abractyeyt","dgdsaeactyey"的最大子串为"actyet"。

/*
5.求两个串中的第一个最长子串（神州数码以前试题）。
如"abractyeyt","dgdsaeactyey"的最大子串为"actyet"。

看到有说用后缀树解决 最长公共子串 后缀的最长前缀
但是 这里暴力解决了一下 
*/
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;

char* MaxSubString(char *str1, char *str2) 
{
	int i,j,k,index,max=0;
	for(i=0;str1[i];i++)
		for(j=0;str2[j]; j++) 
		{
			for(k=0;str1[i+k]==str2[j+k]&&(str2[i+k]||str1[i+k]);k++);
				if(k>max) 
				{  
					index=j;
					max=k;
				}
		}
	char *strResult=(char*)calloc(sizeof(char),max+1);
	for(i=0;i<max;i++)  
		strResult[i]=str2[index++];
	return strResult;
}

int main()
{
	char str1[]="abractyeyt";
	char str2[]="dgdsaeactyey";
	char *strResult=MaxSubString(str1,str2);
	printf("str1=%s \nstr2=%s\nMaxSubString=%s\n",str1,str2,strResult);
}