2010筆面試專欄一：字符串
計算機筆試和面試最常考察的就是字符串的各種操作。字符串處理是我們程序員日常工作最常遇到的問題，能夠體現程序員的基本功。下面我就最近一個月以來的各種筆試和面試遇到的有關字符串處理的題目和大家分享一下：
1、google筆試：編碼實現求給定字符串(全為小寫英文字母)的最小后繼，如“abc”的最小后繼為 “abd”,“dhz”的最小后繼為“dj”。
思路：題目比較簡單，對最后一個字符+1，如果大于’z’則對前一個字符+1，如果又是大于 ’z’，重復之前步驟。所以寫代碼時，我們只要對字符串循環從后往前對每一個字符進行+1，直到出現+1后不超過’z’為止。如果退出循環時第一個字符大于于’z’則提示不存在，否則把退出循環的字符的后一位置為’\0’即可。
代碼:
{
int srclen=strlen(src);
minnext=(char*)malloc((srclen+1)*sizeof(char));
if(minnext==NULL)
{
return -1;
}
strcpy(minnext,src);
int i=srclen-1;
while(i>=0)
{
minnext[i]++;
if(minnext[i]<='z')
{
break;
}
i--;
}
if(i<0)
{
return 0;
}
else
{
minnext[++i]='\0';
return 1;
}
}
如果把給定字符串全為小寫英文字母改為大小寫英文字母，則只要把：if(minnext[i]<='z')改為 if(minnext[i]<='z'&&minnext[i]>'a'||minnext[i]<='Z')，注意minnext[i]<='z'&&minnext[i]>'a'是為了防止minnext[i]為大寫的情況，因為大寫英文字母(A:65)比小寫(a:97)的ASCII 碼小，如果不加minnext[i]>'a'則minnext[i]為(’Z’+1,ASCII 碼:91)也會跳出循環。
2、中興：編碼實現字符串右移n位，如“diopHeg”右移2位為“egdiopH”
思路1：只要把需要移動的最后n個字符保存下來，把前面剩下的全部后移n個位置，最后把開始保存好的n 個字符填充到前面n個位置。注意：n超過字符串長度的情況，所以事前先做n mod 字符串的長度。
代碼：
{
int len=strlen(src);
int mov=n%len;
char* rstr=(char*)malloc((mov+1)*sizeof(char));
if(rstr==NULL)
{
return 0;
}
int i=0;
while(i<mov)
{
rstr[i]=src[len-mov+i];
i++;
}
rstr[i]='\0';
i=len-mov-1;
while(i>=0)
{
src[i+mov]=src[i];
i--;
}
i=0;
while(i<mov)
{
src[i]=rstr[i];
i++;
}
free(rstr);
return 1;
}
思路2：使用字符串庫函數簡化編碼工作，用一個新的字符串ss保存結果，先把源字符串指針s移到需要右移的子串的第一個字符的位置，如 “diopHeg”右移2位就把s移動到指向’e’，接著 strcpy(ss,s)，把s所指位置賦值為’\0’，最后strcat(ss,s)。
int RightMove(char* src,char* &ssrc,int n)
{
int len=strlen(src);
ssrc=(char*)malloc(sizeof(char)*(len+1));
n=n%len;
if(ssrc==NULL)
{
return 0;
}
int i=0;
char* s=src;
while(i<len-n)
{
s++;
i++;
}
strcpy(ssrc,s);
*s='\0';
strcat(ssrc,src);
return 1;
}
3、新郵通：字符串反轉：給定字符串“we;tonight;you;”，編碼實現輸出“ew;thginot;uoy;”
思路：使用兩個變量first和end分別記錄當前需要反轉的子串的頭和尾字符的下標，每遇到’;’就把first和end之間的子串進行前后反轉。
代碼：
{
int len=strlen(src);
int i=0;
int first=0;
int end=0;
while(i<len)
{
if(src[i]==';')
{
end=i-1;
while(first<end)
{
char temp=src[first];
src[first]=src[end];
src[end]=temp;
first++;
end--;
}
first=i+1;
}
i++;
}
}
如果給定字符串結尾沒有’;’，如“we;tonight;you”，編碼實現輸出“ew;thginot;uoy”，只需要修改一下代碼9、10、11行：
{
if(src[i]==';')
end=i-1;
else
end=i;
4、西艾：X86結構下，下面代碼輸出結果是什么？
代碼：
int* p=(int*)str;
p[0]=0x61626364;
p[1]=0x31323334;
p[2]=0x41424344;
cout<<str<<endl;
解題：考察知識點：
（1）int的內存大小：32bit=4byte；char的內存大小：4bit=1byte；
（2）常用字符的ASCII 碼，’a’:97;’A’=65;’0’=48；
（3）十六進制轉，0x61=97；
4）大小端模式：
所謂的小端模式，是指數據的低位保存在內存的低地址中，而數據的高位保存在內存的高地址中，這種存儲模式將地址的高低和數據位權有效地結合起來，高地址部分權值高，低地址部分權值低，和我們的邏輯方法一致。
所謂的大端模式，是指數據的低位（就是權值較小的后面那幾位）保存在內存的高地址中，而數據的高位，保存在內存的低地址中，這樣的存儲模式有點兒類似于把數據當作字符串順序處理：地址由小向大增加，而數據從高位往低位放；
而X86結構為小端模式，所以：
p[0]=0x61626364;//97,98,99,100對應a,b,c,d,小端存在字符串str則為dcba
p[1]=0x31323334;//同理4321
p[2]=0x41424344;//同理DCBA
代碼輸出：dcba4321DCBA
留言列表
