1字符串相关试题总结.docx

1字符串相关试题总结.docx

《1字符串相关试题总结.docx》由会员分享，可在线阅读，更多相关《1字符串相关试题总结.docx（37页珍藏版）》请在冰点文库上搜索。

1字符串相关试题总结

字符串相关试题总结

1.字符串反转

1.1char*Reverse（char*s）

{

//将q指向字符串最后一个字符

char*q=s;

while（*q++）;

q-=2;

//分配空间，存储逆序后的字符串。

char*p=newchar[sizeof（char）*（q-s+2）];

char*r=p;

//逆序存储

while（q>=s）

*p++=*q--;

*p='\0';

returnr;

}

1.2voidstrRev（char*s/*,char*out*/）

{

chartemp;

char*end=s+strlen（s）-1;//指向字符串s最后一个字符

while（end>s）

{

temp=*s;

*s=*end;

*end=temp;

--end;

++s;

}

}

编程翻转字符串，优化速度、优化空间。

解答：

这是网络流传的Microsoft的面试题目之一：

“编写反转字符串的程序，要求优化速度、优化空间”。

因为最近一直很多关注算法方面的实践和研究，因此对这个问题进行了一些思考，给出了5种实现方法（有两种解法相关性比较大）。

这是网络流传的Microsoft的面试题目之一：

“编写反转字符串的程序，要求优化速度、优化空间”。

因为最近一直很多关注算法方面的实践和研究，因此对这个问题进行了一些思考，给出了5种实现方法（有两种解法相关性比较大）。

解法一：

第一次看到这题目，想到最简单、最直觉的解法就是：

遍历字符串，将第一个字符和最后一个交换，第二个和倒数第二个交换，依次循环，即可，于是有了第一个解法：

char*strrev1（constchar*str）

{

intlen=strlen（str）;

char*tmp=newchar[len+1];

strcpy（tmp,str）;

for（inti=0;i

{

charc=tmp;

tmp=tmp[len-i-1];

tmp[len-i-1]=c;

}

returntmp;

}

这里是通过数组的下标方式访问字符串的字符，实际上用指针直接操作即可。

解法二正是基于此，实现代码为：

char*strrev2（constchar*str）

{

char*tmp=newchar[strlen（str）+1];

strcpy（tmp,str）;

char*ret=tmp;

char*p=tmp+strlen（str）-1;

while（p>tmp）

{

chart=*tmp;

*tmp=*p;

*p=t;

--p;

++tmp;

}

returnret;

}

显然上面的两个解法中没有考虑时间和空间的优化，一个典型的优化策略就是两个字符交换的算法优化，我们可以完全不使用任何外部变量即完成两个字符（或者整数）的交换，这也是一个很经典的面试题目。

特别是一些嵌入式硬件相关编程中经常要考虑寄存器的使用，因此经常有不使用任何第三个寄存器即完成两个寄存器数据的交换的题目。

一般有两个解法，对应这里的解法三和解法四。

解法三的实现代码为：

char*strrev3（constchar*str）

{

char*tmp=newchar[strlen（str）+1];

strcpy（tmp,str）;

char*ret=tmp;

char*p=tmp+strlen（str）-1;

while（p>tmp）

{

*p^=*tmp;

*tmp^=*p;

*p^=*tmp;

--p;

++tmp;

}

returnret;

}

解法四的实现代码为：

char*strrev4（constchar*str）

{

char*tmp=newchar[strlen（str）+1];

strcpy（tmp,str）;

char*ret=tmp;

char*p=tmp+strlen（str）-1;

while（p>tmp）

{

*p=*p+*tmp;

*tmp=*p-*tmp;

*p=*p-*tmp;

--p;

++tmp;

}

returnret;

}

实际上我们还可以通过递归的思想来解决这个问题，思想很简单：

每次交换首尾两个字符，中间部分则又变为和原来字符串同样的问题，因此可以通过递归的思想来解决这个问题，对应解法五的实现代码为：

char*strrev5（/*const*/char*str,intlen）

{

if（len<=1）

returnstr;

chart=*str;

*str=*（str+len-1）;

*（str+len-1）=t;

return（strrev5（str+1,len-2）-1）;

}

以下给出一个测试程序：

intmain（intargc,char*argv[]）

{

char*str="hello";

printf（str）;

printf（"\n"）;

char*str2=strrev1（str）;

printf（str2）;

printf（"\n"）;

char*str3=strrev2（str2）;

printf（str3）;

printf（"\n"）;

char*str4=strrev3（str3）;

printf（str4）;

printf（"\n"）;

char*str5=strrev4（str4）;

printf（str5）;

printf（"\n"）;

char*str6=strrev5（str5,strlen（str5））;

printf（str6）;

printf（"\n"）;

return0;

}

你就可以看到字符串"hello"和"olleh"交替输出了。

说明：

1）这里解法中没有认真考虑输入字符串的合法性和特殊长度（如NULL、一个字符等）字符串的处理；2）前4个算法不改变输入字符串的值，解法五修改了输入字符串。

2.实现库函数strcpy的功能

voidstrcpy（char*dest,constchar*src）

{

assert（dest!

=NULL&&src!

=NULL）;

while（*src!

='\0'）

{

*dest++=*src++;

}

*dest='\0';

}

3.实现atoi函数,itoa函数

3.1intatoi（constchar*s）

{

if（s==NULL）return0;

intresult=0;

if（（'0'<=s[0]&&s[0]<='9'）||（s[0]=='-'）||s[0]=='+'）

{

if（s[0]=='+'||s[0]=='-'）

{

s++;

}

}

else

{

return0;

}

while（'0'<=*s&&*s<='9'）

{

result=result*10+（*s++-'0'）;

}

if（sign==-1）

{

result*=sign;

}

returnresult;

}

说明：

constchar*str;是修饰字符串不能改变的，而不是指针，修饰常量指针的是char*conststr；

那我就说说吧：

constint*constpint;//一个const指针，指向一个const成员

constint*pint;//一个非const指针，指向一个const成员

int*pint;//一个非const指针，指向一个非const成员

int*constpint;//一个const指针，指向一个非const成员

intconst*pint;//和第二个一样，一个非const指针，指向一个const成员，这个不常用

3.2itoa函数实现

//实现itoa函数

//整形转成字符串函数实现

//题目不难，重点考察面试者对问题考虑的全面程度

voiditoa_mf（intnum,charstr[]）

{

intsign=num;

inti=0;

intj=0;

chartemp[100];

//如果是负数就去掉符号,将-1234转成

if（sign<0）

{

num=-num;

}

//转成字符串，转成"4321"

do

{

temp[i]=num%10+'0';

num/=10;

i++;

}while（num>0）;

//如果是负数的话，加个符号在末尾，如：

"4321-"

if（sign<0）

{

temp[i++]='-';

}

temp[i]='\0';

i--;

//将temp数组中逆序输入到str数组中

//将"4321-"====>"-1234"

while（i>=0）

{

str[j]=temp[i];

j++;

i--;

}

//字符串结束标识

str[j]='\0';

}

3.3

（01）写一个将整数转换成字符串的函数itoa

解析：

整数转化成字符串，可以采用加'0',然后再逆序，整数加'0'就会隐形转化为char类型的数。

intmain（void）

{

intnum=12345,j=0,i=0;

chartemp[7],str[7];

while（num）

{

temp[i]=num%10+'0';

i++;

num=num/10;

}

temp[i]=0;

printf（"temp=%s\n",temp）;

i=i-1;

while（i>=0）

{

str[j]=temp[i];//字符串反转

j++;

i--;

}

str[j]=0;

printf（"string=%s\n",str）;

return0;

}

（02）编程实现字符串数转化成整数的方法。

解析：

可以采用减'0'再乘10累加的方法，字符串减'0'就会隐性转换为int类型的数

#include

#include

intmain（void）

{

intnum=12345,j=0,i=0,sum=0;

chartemp[7]={'1','2','3','4','5','\0'},str[7];

while（temp[i]）

{

sum=sum*10+（temp[i]-'0'）;

i++;

}

printf（"sum=%d\n",sum）

return0;

}

4.//实现库函数strcat的功能

voidstrcat_my（char*dst,constchar*src）

{

char*p=dst;

while（*p）

p++;//p指针指向最后

while（*p++=*src++）;

}

5.实现库函数strcmp的功能

//实现库函数strcmp的功能

intstrcmp_my（constchar*src,constchar*dst）

{//两个字符串自左向右逐个字符相比（按ASCII值大小相比较），直到出现不同的字符或遇'\0'为止

intret=0;

while（!

（ret=*（unsignedchar*）src-*（unsignedchar*）dst）&&*src）

++src,++dst;

if（ret<0）

ret=-1;

elseif（ret>0）

ret=1;

return（ret）;

}

6.//计算字符串中元音字符的个数

intis_vowel（chara）

{

switch（a）

{

case'a':

case'A':

case'e':

case'E':

case'i':

case'I':

case'o':

case'O':

case'u':

case'U':

return1;break;

default:

return0;break;

}

}

intcount_vowel（constchar*s）

{

intnum;

if（s[0]=='\0'）

num=0;

else

{

if（is_vowel（s[0]））

num=1+count_vowel（&s[1]）;

else

num=count_vowel（&s[1]）;

}

returnnum;

}

7.

/***********************************************

*函数名称：

fun

*描述：

对一个字符串重新排列，字母排在前面，数字排在后面，并不改变原来字母之间以及数字之间的字符顺序。

*参数：

char*s,int*m

*返回值：

chLetter（数组chLetter[]的首元素地址）

*局部变量：

charchLetter[N];

*charchNumber[N];

*inti,j,k;

************************************************/

char*fun（char*s,int*m）//参数m是通过调试才想到的

{

char*src=s;//定义一个src指针指向原字符串，便于操作src计算字符串长度

intcount=0;//统计字符串的个数

while（*src++）

count++;

char*pchLetter=newchar[count];//用来存放字母

char*pchNumber=newchar[count];//用来存放数字

memset（pchLetter,0,count）;

memset（pchNumber,0,count）;

inti,j,k;

j=0;//j用来记录字母的个数

k=0;//k用来记录数字的个数

for（i=0;i

{

if（（s[i]>='A'&&s[i]<='Z'）||（s[i]>='a'&&s[i]<='z'））//将字母存入pchLetter[]

{

pchLetter[j]=s[i];

j++;

}

if（s[i]>='0'&&s[i]<='9'）//将数字存入chNumber[]

{pchNumber[k]=s[i];

k++;

}

}

pchLetter[j]='';

pchNumber[k]='\0';

*m=j+k;//用来返回最后的字符和数字个数之和

strcat_my（pchLetter,pchNumber）;

returnpchLetter;

}

8.

/***********************************************

*函数名称：

fun

*描述：

将s所指字符串中最后一次出现的与t1所指字符串相同的子串替换为t2所指字符串

*参数：

char*s,char*t1,char*t2,int*m

*返回值：

w（数组w[]的首元素地址）

*局部变量：

charw[N];

*chartemp[T];

*chart1temp[T];

*inti,j,k,l;

************************************************/

voidfun（char*s,char*t1,char*t2,char*w）

{

char*src=s;//定义一个src指针指向原字符串，便于操作src计算字符串长度

intcount=0;//统计字符串的个数

while（*src++）

count++;

//intcount=strlen（s）;也可以

intt1_count=strlen（t1）;

char*temp=newchar[t1_count+1];//用来存放从s所指字符串中截取的子串

char*t1temp=newchar[t1_count+1];//用来存放t1所指字符串

memset（temp,0,（t1_count+1））;

memset（t1temp,0,（t1_count+1））;

inti,j,k,l;

//向t1temp中存入t1所指字符串

for（i=0;i

{t1temp[i]=t1[i];}

t1temp[t1_count]='\0';

//寻找相同时的最后一个字符的下标

for（i=0;i

{

l=0;

for（j=i;j<（i+t1_count）;j++,l++）//截取长度为T的子串存到temp[]中

{temp[l]=s[j];}//找到子串后立刻处理（和t1字符串比较）

temp[t1_count]='\0';

if（strcmp（t1temp,temp）==0）

{

k=i;//k记录相同时的最后一个字符的下标

}

}

j=0;

for（i=0;i

{

if（i>=k&&i<（k+t1_count））//在找到的k点处开始换值

{

w[i]=t2[j++];//换值

}

else{w[i]=s[i];}

}

delete[]temp;

delete[]t1temp;

temp=NULL;

t1temp=NULL;

}

★9.//字符串全排列算法

9.1.1全排列的递归实现

//设R={r1,r2,…,rn}是要进行排列的n个元素，Ri=R-{ri}

//（ri）Perm（X）表示在全排列Perm（X）的每一个排列前加上前缀ri得到的排列

//

//

（1）当n=1时，Perm（R）=（r）,其中r是集合R中唯一的元素；

//

（2）当n>1时，Perm（R）可由（r1）Perm（R1）,（r2）Perm（R2）,…,（rn）Perm（Rn）构成

//

//此程序就是按照上述思想来设计的

//

//其中：

//Perm（list,k,m）递归地产生所有前缀是list[0:

k-1],且后缀是list[k:

m]的全排列的所有排列。

那么调用算法Perm（list,0,n-1）则产生list[0:

n-1]的全排列。

//

//for（i=k;i<=n;i++）{

//Swap（list[k],list[i]）;

//Perm（list,k+1,n）;

//Swap（list[k],list[i]）;

//}

//以上这段代码其实就是实现的

（2）的思想。

#include"stdafx.h"

#include"iostream"

usingnamespacestd;

voidSwap（char&a,char&b）

{

chartemp;

temp=a;

a=b;

b=temp;

}

voidPerm（chars[],intk,intm）

{

if（k==m）//Printonepermutation.

{

cout<

}

else

{

for（inti=k;i<=m;i++）

{

Swap（s[k],s[i]）;

Perm（s,k+1,m）;

Swap（s[k],s[i]）;

}

}

}

int_tmain（intargc,_TCHAR*argv[]）

{

chars[]="123";

Perm（s,0,2）;

return0;

}

9.1.2也是递归实现

123的全排列有123、132、231、231、312、321这六种。

首先考虑213和321这二个数是如何得出的。

显然这二个都是123中的1与后面两数交换得到的。

然后可以将123的第二个数和每三个数交换得到132。

同理可以根据213和321来得231和312。

因此可以知道——全排列就是从第一个数字起每个数分别与它后面的数字交换。

voidPermutation（char*pStr,char*pBegin）

{

assert（pStr&&pBegin）;

if（*pBegin=='\0'）

printf（"%s\n",pStr）;

else

{

for（char*pCh=pBegin;*pCh!

='\0';pCh++）

{

swap（*pBegin,*pCh）;

Permutation（pStr,pBegin+1）;

swap（*pBegin,*pCh）;

}

}

}

int_tmain（intargc,_TCHAR*argv[]）

{

charstr[]="abc";

Permutation（str,str）;

return0;

}

9.1.3有重复

//在[nBegin,nEnd）区间中是否有字符与下标为pEnd的字符相等

boolIsSwap（char*pBegin,char*pEnd）

{

char*p;

for（p=pBegin;p

{

if（*p==*pEnd）

returnfalse;

}

re