程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 字符串類習題、面試題詳解(第二篇),習題第二篇

字符串類習題、面試題詳解(第二篇),習題第二篇

編輯:C++入門知識

字符串類習題、面試題詳解(第二篇),習題第二篇


第一篇鏈接:字符串類習題、面試題詳解(第一篇)

 

6題:回文串(競賽基礎題)

輸入一個字符串,求出其最長回文子串。子串的含義是:在原串中連續出現的字符串片段。回文的含義是:正著看和倒著看相同,如abba和yyxyy。在判斷時,應該忽略所有標點符號和空格,且忽略大小寫,但輸出應保持原樣(在回文串的首部和尾部不要輸出多余字符)。輸入字符串長度不超過5000,且占據單獨一行。應該輸出最長的回文串,如果有多個,輸出起始位置最靠左的。

樣例輸入:Confuciuss say: Madam, I’m Adam.

樣例輸出:Madam,I’m Adam

方法1:枚舉回文串的起點和終點。

 1 #include <stdio.h>  
 2 #include <ctype.h>  
 3 #include <string.h>  
 4 #define MAXN 5000 + 10  
 5 
 6 char buf[MAXN], s[MAXN];  
 7 int p[MAXN];  
 8 
 9 int main(void)  
10 {  
11     int n, m = 0, max = 0, x = 0, y = 0;  
12     int i, j, k, ok;  
13     fgets(buf, sizeof(buf), stdin);  
14     n = strlen(buf);  
15     
16     for (i = 0; i < n; i++)  
17     {  
18         if (isalpha(buf[i]))  
19         {  
20             p[m] = i;                        //保存字符的實際位置  
21             s[m++] = toupper(buf[i]);        //保存為大寫字母  
22         }  
23     }  
24     
25     for (i = 0; i < m; i++)                //枚舉回文串起始位置  
26     {  
27         for (j = i; j < m; j++)            //枚舉回文串終止位置  
28         {  
29             ok = 1;  
30             for (k = i; k <= j; k++)  
31             {  
32                 if (s[k] != s[i + j - k])  
33                     ok = 0;  
34             }  
35             
36             if (ok && j - i + 1 > max)  
37             {  
38                 max = j - i + 1;  
39                 x = p[i];  
40                 y = p[j];  
41             }  
42         }  
43     }  
44     
45     for (i = x; i <= y; i++)  
46     {  
47         printf("%c", buf[i]);  
48     }  
49     printf("\n");  
50     
51     return 0;  
52 }

 

方法2:枚舉回文串的中間位置。

 1 #include <stdio.h>  
 2 #include <string.h>  
 3 #include <ctype.h>  
 4 #define MAXN 5000 + 10  
 5 char buf[MAXN], s[MAXN];  
 6 int p[MAXN];  
 7 
 8 int main(void)  
 9 {  
10     int n, m = 0, max = 0, x = 0, y = 0;  
11     int i, j;  
12     fgets(buf, sizeof(buf), stdin);  
13     n = strlen(buf);  
14     
15     for (i = 0; i < n; i++)  
16     {  
17         if (isalpha(buf[i]))  
18         {  
19             p[m] = i;                   //保存字符實際位置  
20             s[m++] = toupper(buf[i]);  
21         }  
22     }  
23     
24     for (i = 0; i < m; i++)             //枚舉回文串的中間位置  
25     {  
26         for (j = 0; i - j >= 0 && i + j < m; j++)       //回文子串長度為奇數  
27         {  
28             if (s[i - j] != s[i + j])  
29                 break;  
30             if (j * 2 + 1 > max)  
31             {  
32                 max = j * 2 + 1;  
33                 x = p[i - j];  
34                 y = p[i + j];  
35             }  
36         }  
37         
38         for (j = 0; i - j >= 0 && i + j + 1 < m; j++)   //回文串長度為偶數  
39         {  
40             if (s[i - j] != s[i + j + 1])  
41                 break;  
42             if (j * 2 + 2 > max)  
43             {  
44                 max = j * 2 + 2;  
45                 x = p[i - j];  
46                 y = p[i + j + 1];  
47             }  
48         }  
49     }  
50     
51     for (i = x; i <= y; i++)  
52         printf("%c", buf[i]);  
53     printf("\n");  
54     
55     return 0;  
56 }

解析:枚舉回文串的中間位置時要注意長度為奇數和偶數的處理方式是不一樣的。

 

7題:編碼實現求給定字符串(全為小寫英文字母)的最小後繼,如"abc"的最小後繼為"abd","dhz"的最小後繼為"di"。(Google筆試題)

 1 #include <stdio.h>  
 2 #include <string.h>  
 3 #define MAXN 1024  
 4   
 5 int main(void)  
 6 {  
 7     char buf[MAXN];  
 8     int n, m, i;  
 9     scanf("%s", buf);  
10   
11     n = strlen(buf);  
12     for (i = n - 1; i >= 0; i--)  
13     {  
14         if (buf[i] + 1 <= 'z')  
15         {  
16             buf[i] += 1;  
17             buf[i + 1] = '\0';  
18             break;  
19         }  
20     }  
21     printf("%s\n", buf);  
22   
23     return 0;  
24 }  

解析:對最後一個字符+1,如果大於'z'則對前一個字符+1,如果又大於 'z' 則重復之前的步驟。

 

8題:X86結構下,下面代碼的printf輸出結果是什麼?(西艾面試題)

 1 #include <stdio.h>  
 2   
 3 int main(void)  
 4 {  
 5     char str[20]="Good night";  
 6     int *p = (int *)str;  
 7     p[0] = 0x61626364;  
 8     p[1] = 0x31323334;  
 9     p[2] = 0x41424344;  
10     printf("%s\n", str);  
11   
12     return 0;  
13 }  

解析:輸出結果為:dcba4321DCBA。X86結構下,數據的低位保存在內存的低地址中,數據的高位保存在內存的高地址中。還需要注意常見字符的ASCII碼(十進制),’a’為97,’A’為65,’1’為49。

 

9題:編一個函數,輸入一個字符串,要求做一個新字符串,把其中所有的一個或多個連續的空白字符都壓縮為一個空格。這裡所說的空白包括空格、'\t'、'\n'、'\r'。例如原來的字符串是:

This Content hoho       is ok

       ok?

 

       file system

uttered words   ok ok     ?

end.

壓縮了空白之後就是:

This Content hoho is ok ok? file systemuttered words ok ok ? end.(面試題)

參考程序如下:

 1 #include <stdio.h>  
 2 #include <string.h>  
 3 #include <stdlib.h>  
 4   
 5 const char *p = "This Content hoho       is ok\  
 6         ok?\  
 7 \  
 8         file system\n\  
 9 uttered words   ok ok      ?\  
10 end.";  
11   
12 int IsSpace(char c)  
13 {  
14     if (c == ' ')  
15         return 1;  
16     else if (c == '\n' || c == '\r')  
17         return 2;  
18     else if (c == '\t')  
19         return 3;  
20     else  
21         return 0;  
22 }  
23   
24 char *shrink_space(char *dest, const char *src, size_t n)  
25 {  
26     char *t_dest = dest;  
27     char temp;  
28     int pre = -1, cur = -1, key = -1;  
29     while (IsSpace(*src))   //忽略字符串起始空格  
30          src++;  
31     *t_dest = *src;  
32   
33     while ((temp = *src++) != '\0')  
34     {  
35         key = IsSpace(temp);  
36         if (0 == key)               //0表示字符  
37         {  
38             cur = 0;  
39             *t_dest++ = temp;  
40         }  
41         else if (1 == key)          //1表示空格  
42         {  
43             if (pre == 1)           //如果前面也是空格  
44                 continue;  
45             else  
46             {  
47                 cur = 1;  
48                 *t_dest++ = temp;  
49             }  
50         }  
51         else if (2 == key && pre == 0)  
52         {  
53             *t_dest++ = ' ';  
54         }  
55         else if (3 == key)  
56         {  
57             if (pre == 1)  
58                 continue;  
59             else  
60             {  
61                 *t_dest++ = ' ';        //將\t轉換為1個空格  
62                 cur = 1;  
63             }  
64         }  
65        pre = cur;  
66     }  
67     *t_dest = '\0';  
68   
69     return dest;  
70 }  
71 int main(void)  
72 {  
73     int len = strlen(p);  
74     char *dest = (char *)malloc(sizeof(char) * (len + 1));  
75     shrink_space(dest, p, 1);  
76     printf("%s\n", dest);  
77     free(dest);  
78     dest = NULL;  
79   
80     return 0;  
81 }  

 

10題:寫出在母串中查找子串出現次數的代碼。(面試題)

 1 #include <stdio.h>  
 2 #include <string.h>  
 3 #define BUFSIZE 1024  
 4   
 5 int StrCount(char *strLong, char *strShort)  
 6 {  
 7     int result = 0;  
 8     char *t_strS = strShort;  
 9     char *t_strD = strLong;  
10     while (*t_strD != '\0')  
11     {  
12         t_strS = strShort;    //子串  
13         while (*t_strD == *t_strS && *t_strS != '\0' && *t_strD != '\0')  
14         {  
15             t_strD++;  
16             t_strS++;  
17         }  
18         if (*t_strS == '\0')  
19             result += 1;  
20         else if (*t_strD == '\0')  
21             break;  
22         else  
23             t_strD++;  
24     }  
25   
26     return result;  
27 }  
28   
29 int main(void)  
30 {  
31     int len;  
32     char strD[BUFSIZE], strS[BUFSIZE];  
33     fgets(strD, sizeof(strD), stdin);  
34     len = strlen(strD);  
35     strD[len - 1] = '\0';  
36     fgets(strS, sizeof(strS), stdin);  
37     len = strlen(strS);  
38     strS[len - 1] = '\0';  
39     printf("%d\n", StrCount(strD, strS));  
40     return 0;  
41 }  

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved