【刷题之路】OR62 倒置字符串

一、标题描述

原题连接： OR62 倒置字符串
描述：
将一句话的单词进行倒置，标点不倒置。比如 I like beijing. 经过函数后变为：beijing. like I
输入描述：
每个测试输入包含1个测试用例： I like beijing. 输入用例长度不超过100
输出描述：
依次输出倒置之后的字符串,以空格分割
示例1：
   输入：I like beijing.
输出：beijing. like I
  二、解题

1、方法1——先存后用

1.1、思路解析

我们起首可以想到的是先把每个单词先到一个二维字符数组中，最后在对二维数组进行逆序打印即可：

1.2、代码实现

有了前面的思路，那我们写起代码来也就水到渠成了：

1. void inversion_word1() {
2.         char str[101] = { 0 }; // 保存要输入的字符串
3.         scanf("%[^\n]", str); // 接收一个字符串
4.         int len = strlen(str);
5.         char words[100][100] = { 0 }; // 保存每个单词
6.         int n = 0; // 标志一共有多少个单词,但实际存储的是单词数减1
7.         int j = 0; // 标志走到某个单词的第几个字母了(用于保存每个单词)
8.         // 这样只需要一层循环就够了
9.         int i = 0;
10.         for (i = 0; i < len; i++) {
11.                 if (' ' == str[i]) {
12.                         words[n][j + 1] = '\0'; // 在每个单词后面加上字符串结束标志
13.                         n++; // 单词数加1，也是行数加1
14.                         j = 0; // 已经完成了一个单词的存储，j需要重新归零
15.                         i++; // 空格空格就不存储了，打印的时候补上就行，所以跳过空格
16.                 }
17.                 words[n][j] = str[i]; // 将某个单词的每个字符保存
18.                 j++;
19.         }
20.         // 最后逆序打印即可
21.         for (i = n; i >= 0; i--) {
22.                 printf("%s ", words[i]);
23.         }
24. }

复制代码

时间复杂度：O(n), n为所有单词的总长度
空间复杂度：O(nm),n为单词的个数，m为所有单词及标点符号的平均长度
改进：
大概有人会觉得上面的存储方式有点儿麻烦，能不能改进一下？
其实我们可以使用scanf()函数特性来完成边输入边存储：

1. void inversion_word2() {
2.         char words[100][100] = { 0 };
3.         int n = 0;
4.         int j = 0;
5.         int x = 0;
6.         while (1) {
7.                 // scanf默认遇到空格就会停止
8.                 x = scanf("%s", words[n]);
9.                 if (getchar() == '\n') { // 如果接收到'\n',就停止
10.                         break;
11.                 }
12.                 if (x) { // 如果读取成功，转到下一行
13.                         n++;
14.                 }
15.         }
16.         // 最后逆序打印
17.         for (j = n; j >= 0; j--) {
18.                 printf("%s ", words[j]);
19.         }
20. }

复制代码

时间复杂度：O(n),n为单词个数
空间复杂度：O(nm),n为单词的个数，m为所有单词及标点符号的平均长度
2、方法2——设置断点

2.1、思路解析

上面的方法有点儿浪费内存空间，这里有个能淘汰空间实用的方法：
我们界说一个字符指针数组，将每个单词的起始字符地点生存起来，然后将非字母自负全部更换成字符串结束标志，相当于在整个字符串中加了多个断点，最后对字符数组进行逆序打印及可：

当某个字符不是空格且它前一个字符不是空格时，则阐明这个字符就是一个单词的起始字母。所以将这个字符的地点参加到，字符指针数组中，将它的前一个字符改成字符串结束标志’\0’即可。
2.2、代码实现

有了上面的思路我们写起代码来也就水到渠成了：

1. // 我们先定义一个函数，判断某个字符是否为空格，是，返回1，不是，返回0
2. int is_blank(char c) {
3.         return c == ' ';
4. }
5. void inversion_word3() {
6.         char str[101] = { 0 }; // 保存要输入的字符串
7.         scanf("%[^\n]", str); // 接收一个字符串
8.         int len = strlen(str);
9.         char* word[100] = { 0 }; // 存储每个单词的起始地址
10.         int n = 0; // 标记共有过少个字母
11.         int i = 0;
12.         // 遍历一遍str即可
13.         for (i = 0; i < len - 1; i++) {
14.                 if (0 == i && 0 == is_blank(str[i])) { // 先将第一单词的首字母地址存起来
15.                         word[n] = &str[i];
16.                         n++;
17.                         continue;
18.                 }
19.                 if (is_blank(str[i]) == 1 && is_blank(str[i + 1]) == 0) {
20.                         word[n] = &str[i + 1];
21.                         str[i] = '\0';
22.                         n++;
23.                 }
24.         }
25.         // 最后再逆序打印即可
26.         for (i = n - 1; i >= 0; i--) {
27.                 printf("%s ", word[i]);
28.         }
29. }

复制代码

3、方法三——先整体在局部的逆序

3.1、思路分析

我们起首思索我们在逆序一个字符串的时间，是不是把后面的字符全都放到了前面？很简朴，当然是，只不过是次序到过来了，举个最简朴的例子就是“ab-cd”逆序之后变成了“dc-ba”，那若是我们在整体逆序的基础上在进行局部逆序是不是就能做到把单词的位置逆序，而单词本身不逆序了呢？
我们可以先界说一个通用的逆序函数，将两个指针之间的字符内容进行逆序。然后再通过两个辅助指针遍历字符串，找到每个单词的起始字符和结尾字符，然后传给逆序函数进行逆序就行了，遍历方法如下：

初始时我们可以先让一个start指针指向字符串的起始位置，然后让另一个指针temp一直向前走，直到temp指向一个空格；
然后将start和temp - 1之间的空间进行逆序；
逆序完后，先将start指向temp + 1的位置，再将temp后移一位:

重复以上操纵，直到temp指向’\0’
3.2、代码实现

有了以上思路，那我们写起代码来也就水到渠成了：

1. // 先定义一个通用的字符串逆序函数
2. void reverse_str(char* left, char* right) {
3.         // left和right都不能为NULL
4.         assert(left && right);
5.         while (left < right) {
6.                 char tmp = *left;
7.                 *left = *right;
8.                 *right = tmp;
9.                 left++;
10.                 right--;
11.         }
12. }
14. void inversion_word4() {
15.         char str[101] = { 0 }; // 保存要输入的字符串
16.         scanf("%[^\n]", str); // 接收一个字符串
17.         int len = strlen(str);
18.         // 先对字符串进行整体逆序
19.         reverse_str(str, str + len - 1);
20.         char* temp = str; // 辅助指针，辅助遍历字符串,初始化指向字符串起始位置
21.         char* start = str; // 辅助指针，指向每个单词的起始位置
22.         // 再对字符串进行局部逆序
23.         while (*temp) {
24.                 while (*temp != ' ' && *temp != '\0') {
25.                         temp++;
26.                 }
27.                 reverse_str(start, temp - 1);
28.                 if (*temp == ' ') {
29.                         start = temp + 1;
30.                         temp++;
31.                 }
32.         }
33.         printf("%s", str);
34. }

复制代码

时间复杂度：O(n),n为字符串的总长度，(虽然是两成循环，但temp是一直往前走，所以复杂度还是O(n).
空间复杂度：O(m),m为单词的个数。代表调用逆置函数的次数。
这里另有一个神奇的现象

就是先局部还是先整体其实结果都是一样的，此中的原理很简朴，大家用个很短的例子就能搞清楚。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。