字符串类习题、面试题详解（第一篇）

1题：WERTYU（竞赛基础题）

把手放在键盘上时，稍不注意就会往右错一位，这样的话Q会变为W，J会变为K等。输入一个错位后敲出的字符串，输出打字员本来想打出的句子。

样例输入：O S, GOMR YPFSU/

样例输出：I AM FINE TODAY.

 1 #include <stdio.h>  
 2 const char *str = "`1234567890-=QWERTYUIOP[]\ASDFGHJKL;'ZXCVBNM,./";  
 3   
 4 int main(void)  
 5 {  
 6     char c;  
 7     int i;  
 8     while ((c = getchar()) != EOF)  
 9     {  
10         for (i = 0; str[i] && str[i] != c; i++);  
11         if (str[i])  
12             putchar(str[i - 1]);  
13         else  
14             putchar(c);  
15     }  
16       
17     return 0;  
18 }

解析：本题注意两点：（1）for循环终止条件的判断，常量字符串末尾自动补“”，因而可利用str[i]的取值判断是否查找到最后一个字符。（2）反斜线“”是特殊字符，需要使用转义序列或直接引用其ASCII码。

2题：TeX括号（竞赛基础题）

在TeX中，左双引号是``，右双引号是’’。输入一篇包含双引号的文章，你的任务是把它转换成TeX格式。

样例输入：

“To be or not to be,” quoth the Bard, “thatis the question”.

样例输出：

``To be or not to be,” quoth the Bard,``that is the question”.

 1 #include <stdio.h>  
 2   
 3 int main(void)  
 4 {  
 5     char c;  
 6     int q = 1;  
 7     while ((c = getchar()) != EOF)  
 8     {  
 9         if (c == '"')  
10         {  
11             printf("%s", q ? "``" : "''");  
12             q = !q;  
13         }  
14         else  
15             printf("%c", c);  
16     }  
17       
18     return 0;  
19 }

解析：本题的关键是如何判断一个双引号是左双引号还是右双引号。

3题：周期串（竞赛基础题）

如果一个字符串可以由某个长度为k的字符串重复多次得到，我们说该串以k为周期。例如，abcabcabcabc以3为周期（注意，它也以6和12为周期）。输入一个长度不超过80的串，输出它的最小周期。

样例输入：HoHoHo

样例输出：2

写法1：

 1 #include <stdio.h>  
 2 #include <string.h>  
 3 #define MAXLEN 80  
 4 int main(void)  
 5 {  
 6     char str[MAXLEN + 1] = {0};  
 7     scanf("%s", str);  
 8     int len = strlen(str);  
 9     int result = len;  
10     int i, j;  
11   
12     for (i = 1; i < len / 2 + 1; i++)              //i为周期  
13     {  
14         for (j = 0; j < len - i; j++)  
15         {  
16             if (str[j] != str[j + i])  
17                 break;  
18         }  
19   
20         if (j == len - i)  
21         {  
22             result = i;  
23             break;  
24         }  
25     }  
26     printf("%d
",result);  
27   
28     return 0;  
29 }

写法2：

 1 #include <stdio.h>  
 2 #include <string.h>  
 3 int main(void)  
 4 {  
 5     char word[100];  
 6     scanf("%s", word);  
 7     int len = strlen(word);  
 8     int i, j;  
 9   
10     for (i = 1; i <= len; i++)  
11     {  
12         if (len % i == 0)  
13         {  
14             int ok = 1;  
15             for (j = i; j < len; j++)  
16                 if (word[j] != word[j % i])  
17                 {  
18                     ok = 0;  
19                     break;  
20                 }  
21             if (ok)  
22             {  
23                 printf("%d
", i);  
24                 break;  
25             }  
26         }  
27     }  
28   
29     return 0;  
30 }

解析：本题两种解法的思路是一致的。

4题：编写一个函数，把一个char组成的字符串循环右移n位。例如：原来是”abcdefghi”，如果n = 2，移位后应该是”hiabcdefg”。（面试题）

 1 #include <stdio.h>  
 2 #include <string.h>  
 3 #define MAX_LEN 1024  
 4   
 5 void LoopMove_1(char *pStr, int steps)  
 6 {  
 7     int len = strlen(pStr) - steps;  
 8     char temp[MAX_LEN];  
 9   
10     strcpy(temp, pStr + len);  
11     strcpy(temp + steps, pStr);  
12     *(temp + steps + len) = '';  
13     strcpy(pStr, temp);  
14 }  
15   
16 void LoopMove_2(char *pStr, int steps)  
17 {  
18     int len = strlen(pStr) - steps;  
19     char temp[MAX_LEN];  
20   
21     memcpy(temp, pStr + len, steps);  
22     memcpy(temp + steps, pStr, len);  
23     memcpy(pStr, temp, len + steps);  
24 }  
25   
26 int main(void)  
27 {  
28     char str1[] = "abcdefghi";  
29     LoopMove_1(str1, 3);  
30     printf("%s
", str1);  
31   
32     char str2[] = "gklmnopqrst";  
33     LoopMove_1(str2, 3);  
34     printf("%s
", str2);  
35     return 0;  
36 }

解析：本题提供了两种方法。

5题：编写程序，从键盘输入一组任意长度的字符串，当输入“#”符时结束输入（字符串不包括“#”），然后程序反向输出该字符串。（面试题）

方法1：将输入的字符串保存在一个数据结构中，然后将其内容反向输出。例如：首先申请一个栈，每输入一个字符时都将该字符做入栈操作，直到入栈队列中发现“#”为止（“#”不入栈）。然后再将栈中的元素顺序出栈。

 1 #include <stdio.h>    
 2 #define MAX_LEN 1024    
 3     
 4 int main(void)    
 5 {    
 6     char arr[MAX_LEN], c;    
 7     int i = 0, j;    
 8     while ((c = getchar()) != '#')    
 9     {    
10         arr[i++] = c;    
11     }    
12     arr[i] = '';    
13     
14     for (j = i - 1; j >= 0; j--)    
15     {    
16         printf("%c", arr[j]);    
17     }    
18     printf("
");    
19         
20     return 0;    
21 }

方法2：题目没要求保存输入的字符串，因此可用递归解此题。递归算法本身有栈的特性，每次递归地调用递归函数时，系统都会将现场保存在栈中，待调用结束返回时再恢复现场的内容。

 1 #include <stdio.h>    
 2     
 3 void StrRev()    
 4 {    
 5     char c;    
 6     scanf("%c", &c);    
 7     if ('#' == c)    
 8     {    
 9         printf("反转后的字符串:");    
10         return;    
11     }    
12     
13     StrRev();    
14     printf("%c", c);    
15 }    
16     
17 int main(void)    
18 {    
19     printf("请输入英文字符串(以#结束):");    
20     StrRev();    
21     printf("
");    
22     return 0;    
23 }