反转字符串中的单词
思路（进阶）
- 我们首先不考虑太多限制因素，先看如何实现字符串中单词的反转
- 举个例子：我们要反转字符串“the sky is blue”中的单词，我们可以先将字符串中的每个字符反转“eht yks si eulb”，然后我们可以发现，从右到左看字符串正好就是我们想要的结果“blue is sky the”，所以再将整个字符串反转不就行了吗?
- 而具体方法我们已经在反转整个字符串，分区域反转字符串分析清楚。
- 接下来就是要考虑题目最恼火的限制条件：不允许多余空格的出现，即只允许单词之间出现一个空格，多余的空格须全部删除。
- 当然，最容易想到的还是暴力解法，即碰到字符串串首空格（字符串开头就是空格）和单词之间的重复空格，就不断将字符串的元素前移，直至覆盖多余空格，但可想而知，这样做的效率不高。
- 其实比较好的做法其实我们已经在移除元素中讲过，只不过上一次我们处理的是数组，而这一次处理的时字符串（实际上字符串也是数组）
- 如果不对移除元素中的代码进行改进（如下代码），那么我们实现的就是将整个字符串中的空格删除，这显然不是我们想要的结果，我们应该让每个单词之间留有一个空格
int slow = 0; for(int fast = 0; fast <= strlen(s); fast++) { if(s[fast] != ' ') s[slow++] = s[fast]; }
- 因此我们就要对上述代码进行改进:
int slow = 0; for(int fast = 0; fast <= strlen(s); fast++) { if(s[fast] != ' ') { //只要slow不位于第一个字符（不是第一个单词），就需要手动插入空格，即确保每个单词之间有一个空格 if(slow != 0) s[slow++] = ' '; //如果while仍是if，那么上述插入空格的语句就会对一个单词重复执行 //因此要用循环对每个单词进行整理 while(s[fast] != ' ' && s[fast] != '\0') s[slow++] = s[fast++]; } }
实现代码
void Part_reverseWords(char* s, int left, int right) //反转指定区域的字符串 { while (left <= right) { char temp = s[left]; s[left] = s[right]; s[right] = temp; left++; right--; } } void ReplaceSpaces(char *s) //删除多余空格 { int slow = 0; for(int fast = 0; fast < strlen(s); fast++) { if(s[fast] != ' ') { //只要slow不位于第一个字符（不是第一个单词），就需要手动插入空格，即确保每个单词之间有一个空格 if(slow != 0) s[slow++] = ' '; //如果while仍是if，那么上述插入空格的语句就会对一个单词重复执行 //因此要用循环对每个单词进行整理 while(s[fast] != ' ' && s[fast] != '\0') s[slow++] = s[fast++]; } } s[slow ] = '\0'; //在新的字符串末尾添加结束符 } char* reverseWords(char* s) { ReplaceSpaces(s); int i = 0; //对每个单词进行反转 for (int j = i + 1; j <= strlen(s); j++) { if (s[j] == ' ' || j == strlen(s)) { Part_reverseWords(s, i, j - 1); i = j + 1; } } //对整个字符串反转 Part_reverseWords(s,0,strlen(s) - 1); return s; }
