📄 c.txt
字号:
65 int main()
66 {
67 char hello[] = "hasd11H";
68
69 EncodeString(hello, strlen(hello));
70 cout << hello << endl;
71
72 return 0;
73 }
程序说明如下：
q 代码第61～62行，EncodeString()函数调用了ReplaceChars ()函数和ReverseString()函数，前者替代字符，后者翻转整个字符串。
q ReplaceChars()函数调用GetFourthChar()函数来查找并替换后面第4个字符。GetFourthChar()函数查找两个全局数组，这两个数组分别包含了所有的字母。
q ReverseString()函数使用了begin和end两个分别指向字符串头尾的指针，然后头尾的内容不断交换，begin指针往尾移动，end指针往头移动，如此循环直到两个指针碰头。
程序执行结果如下：
L11hwel
面试例题20：反转字符串，但其指定的子串不反转。
考点：字符串相关的综合编程能力。
出现频率：★★★
给定一个字符串以及该字符串的子串，将字符串反转，但子串部分不反转，示例如下。
输入字符串为"Welcome you, my friend"
子串为"you"
输出为"dneirf ym ,you emocleW"
解析
对于本类型题目，采取的步骤如下所示。
q 扫描一遍字符串，然后用stack把它反转，同时记录下子串出现的位置。
q 扫描一遍记录下来的子串，再用stack反转。
q 将堆栈里的字符弹出，这样子串又恢复了原来的顺序。
这里使用扫描数组的方法。如果扫描中发现子串，就将子串倒过来压入堆栈。最后再将堆栈里的字符弹出，这样子串又恢复了原来的顺序。C++标准库中的stack是后进先出的栈结构，使用stack可以轻松地完成这个转换。程序代码如下：
1 #include <iostream>
2 #include <cassert>
3 #include <stack>
4 using namespace std;
5
6 const char* reverse(const char* s1, const char* token)
7 {
8 stack<char> stack1;
9 const char* ptoken = token, *head = s1, *rear = s1;
10 assert(s1 && token);
11 while (*head != '\0')
12 {
13 while(*head != '\0' && *ptoken == *head)
14 {
15 ptoken++;
16 head++;
17 }
18 if(*ptoken == '\0')
19 {
20 const char* p;
21 for(p=head-1; p>=rear; p--)
22 {
23 stack1.push(*p);
24 }
25 ptoken = token;
26 rear = head;
27 }
28 else
29 {
30 stack1.push(*rear++);
31 head = rear;
32 ptoken = token;
33 }
34 }
35 char *pReturn = new char[strlen(s1)+1];
36 int i=0;
37 while(!stack1.empty())
38 {
39 pReturn[i++] = stack1.top();
40 stack1.pop();
41 }
42 pReturn[i]='\0';
43
44 return pReturn;
45 }
46
47 int main(int argc, char* argv[])
48 {
49 char welcome[] = "Welcome you, my friend";
50 char token[] = "you";
51 const char *pRev = reverse(welcome, token);
52
53 cout << "before reverse:" << endl;
54 cout << welcome << endl;
55 cout << "after reverse:" << endl;
56 cout << pRev << endl;
57
58 return 0;
59 }
代码第13～17行，reverse()函数搜索字符串的字串位置。其中指针ptoken记录当前扫描的子串位置，如果其内容为结束符'\0'（代码第18～27行），如果搜索到了这个子串，将它倒过来压入堆栈，否则直接压入堆栈（代码第28～33行）。最后申请一块堆内存，使用退栈把栈中内容存入堆内存中并返回堆内存。程序执行结果如下：
before reverse:
welcome you, my friend
after reverse:
dneirf ym ,you emocleW
面试例题21：编写字符串反转函数strrev。
考点：字符串相关的综合编程能力。
出现频率：★★★★
编写字符串反转函数：strrev，要求时间和空间效率都尽量高。
测试用例:输入“abcd”，输出应为“dcba”。
解析
这种类型的题目最简单的解法是：遍历字符串，将第1个字符和最后1个字符交换，第2个和倒数第2个字符交换，依次循环。解法1代码如下：
1 char* strrev1(const char* str)
2 {
3 int len = strlen(str);
4 char* tmp = new char[len + 1];
5
6 strcpy(tmp,str);
7 for (int i = 0; i < len/2; ++i)
8 {
9 char c = tmp[i];
10 tmp[i] = tmp[len - i - 1];
11 tmp[len - i - 1] = c;
12 }
13
14 return tmp;
15 }
解法1是通过数组下标的方式访问字符串，也可以用指针直接操作。解法2代码如下：
1 char* strrev2(const char* str)
2 {
3 char* tmp = new char[strlen(str) + 1];
4 strcpy(tmp,str);
5 char* ret = tmp;
6 char* p = tmp + strlen(str) - 1;
7
8 while (p > tmp)
9 {
10 char t = *tmp;
11 *tmp = *p;
12 *p = t;
13
14 --p;
15 ++tmp;
16 }
17
18 return ret;
19 }
解法1和解法2都没有考虑时间和空间的优化，典型的优化策略就是两个字符交换的算法优化，我们可以借助异或运算符（^）完成两个字符的交换，对应的是解法3和解法4。
解法3：
1 char* strrev3(const char* str)
2 {
3 char* tmp = new char[strlen(str) + 1];
4 strcpy(tmp,str);
5 char* ret = tmp;
6 char* p = tmp + strlen(str) - 1;
7
8 while (p > tmp)
9 {
10 *p ^= *tmp;
11 *tmp ^= *p;
12 *p ^= *tmp;
13
14 --p;
15 ++tmp;
16 }
17
18 return ret;
19 }
解法4：
1 char* strrev4(const char* str)
2 {
3 char* tmp = new char[strlen(str) + 1];
4 strcpy(tmp,str);
5 char* ret = tmp;
6
7 char* p = tmp + strlen(str) - 1;
8
9 while (p > tmp)
10 {
11 *p = *p + *tmp;
12 *tmp = *p - *tmp;
13 *p = *p - *tmp;
14
15 --p;
16 ++tmp;
17 }
18
19 return ret;
20 }
也可以使用递归算法来解决这个问题。每次交换首尾两个字符，中间部分又变成和原来字符串相同的问题。
解法5：
1 char* reverse5(char* str,int len)
2 {
3 if (len <= 1)
4 return str;
5
6 char t = *str;
7 *str = *(str + len -1);
8 *(str + len -1) = t;
9
10 return (reverse5(str + 1,len - 2) - 1);
11 }
注意：这5个解法中只有解法5修改了输入字符串，其他4种都是在函数体内申请堆内存。下面给出测试用的main()函数：
1 int main(int argc,char* argv[])
2 {
3 char* str = "123456";
4 cout << str << endl;
5
6 char* str2 = reverse1(str);
7 cout << str2 << endl;
8
9 char* str3 = reverse2(str2);
10 cout << str3 << endl;
11
12 char* str4 = reverse3(str3);
13 cout << str4 << endl;
14
15 char* str5 = reverse4(str4);
16 cout << str5 << endl;
17
18 char* str6 = reverse5(str5,strlen(str5));
19 cout << str6 << endl;
20
21 return 0;
22 }
程序输出结果如下：
123456
654321
123456
654321
123456
654321
面试例题22：编程实现任意长度的两个正整数相加。
考点：字符串相关的综合编程能力。
出现频率：★★★★
解析
在C/C++中可以用int、float、double等类型表示数字，但是它们的长度都是有限的，而本题要求数字是任意长度，因而需要用字符串表示数字，同样用字符串表示结果。因此所要做的就是做一个类似整数加法的字符串转换，程序代码如下所示：
1 #include <stdio.h>
2 #include <string.h>
3 #include <stdlib.h>
4 #include <math.h>
5
6 char* addBigInt(char* num1, char* num2)
7 {
8 int c = 0; //进位，开始最低进位为0
9 int i = strlen(num1)-1; //指向第一个加数的最低位
10 int j = strlen(num2)-1; //指向第二个加数的最低位
11 int maxLength = strlen(num1) >= strlen(num2) ?
12 （strlen(num1)+1）:（strlen(num2)+1）; //得到2个数中较大数的位数
13 char* rst = (char*)malloc(maxLength+1); //保存结果
14 int k;
15 if (rst == NULL)
16 {
17 printf("malloc error!\n");
18 exit(1);
19 }
20
21 rst[maxLength] = '\0'; //字符串最后一位为'\0'
22 k = strlen(rst) - 1 ; //指向结果数组的最低位
23 while ( (i >= 0) && (j >= 0) )
24 {
25 rst[k] = ( (num1[i] - '0') + (num2[j] - '0') + c )%10 +'0'; //计算本位的值
26 c = ( (num1[i] - '0') + (num2[j] - '0') + c )/10; //向高位进位值
27 --i;
28 --j;
29 --k;
30 }
31 while ( i >= 0 )
32 {
33 rst[k] = ( (num1[i] - '0') + c )%10 + '0';
34 c = ( (num1[i] - '0') + c)/10;
35 --i;
36 --k;
37 }
38 while ( j >= 0 )
39 {
40 rst[k] = ( (num2[j] - '0') + c )%10 + '0';
41 c = ( (num2[j] - '0') + c )/10;
42 --j;
43 --k;
44 }
45 rst[0] = c + '0';
46
47 if ( rst[0] != '0' ) //如果结果最高位不等于0，则输出结果
48 {
49 return rst;
50 }
51 else
52 {
53 return rst+1;
54 }
55 }
56
57 int main()
58 {
59 char num1[] = "123456789323";
60 char num2[] = "45671254563123";
61 char *result = NULL;
62
63 result = addBigInt(num1, num2);
64 printf("%s + %s = %s\n", num1, num2, result);
65
66 return 0;
67 }
程序执行结果如下所示：
123 456 789 323 + 45 671 254 563 123 = 45 794 711 352 446
面试例题23：编程实现字符串循环右移。
考点：字符串综合编程能力。
出现频率：★★★★
解析
根据题意，编写的函数能把字符串循环右移n位。例如字符串“abcdefghi”，如果n=2，移位后是“hiabcdefgh”。
程序代码如下所示：
1 #include <stdio.h>
2 #include <stdlib.h>
3
4 void loopMove(char *str, int n)
5 {
6 int i = 0;
7 char *temp = NULL;
8 int strLen = 0;
9 char *head = str; //指向字符串头
10
11 while(*str++);
12 strLen = str - head - 1; //计算字符串长度
13 n = n % strLen; // 计算字符串尾部移到头部的字符个数
14 temp = (char *)malloc(n); //分配内存
15 for (i = 0; i < n; i++)
16 {
17 temp[i] = head[strLen - n + i]; //临时存放从尾部移到头部的字符
18 }
19 for (i = strLen - 1; i >= n; i--)
20 {
21 head[i] = head[i - n]; //从头部字符移到尾部
22 }
23 for (i = 0; i < n; i++)
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -