题目描述:给给你一个字符串 s ,逐个翻转字符串中的所有 单词 。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。

说明:

输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
翻转后单词间应当仅用一个空格分隔。
翻转后的字符串中不应包含额外的空格。

输入:s = "the sky is blue"
输出:"blue is sky the"

       自己也是从头开始学习C语言,所以,会说的简单一些,尽量把思路都讲清楚,觉得麻烦的同学可以直接看最下方的代码。

      思路:双指针解法。本题算是一道入门题,所有初学者看到的第一眼,都会想到直接令两个特定位置的单词交换位置,比如,将blue和the,is和sky交换位置,随后再进行去除空格。但是,这种思路的问题在于s是一个字符数组而不是一个字符串数组,虽然可以将字符数组去除保留空格后转换为字符串数组,再对字符串数组进行交换,但这样时间代价上需要遍历两次数组(字符和字符串数组各一次),空间上需要新建一个字符串数组。

      因此,双指针算法的目标是只遍历一次数组,就得到最终的结果。我们可以由后向前进行遍历,利用双指针来定位单词。如下图所以,

      第一步。新建pre和after指针都指向字符串末尾。

      第二步。遍历时,每当遍历到不是空格的位置处。就令after和pre指向它。

      第三步,继续遍历直到遍历到是空格时,令pre指向该位置,令cur指向pre+1的位置,这里我们可以看到cur指向的位置处为'b',after指向的位置处为'e'。

      第四步,在通过一个while循环,我们便可以获得blue这个单词,存储到新建的字符数组res中,随后,新加一个空格。

      直到pre<0,循环结束。下面为代码。

  1. char* reverseWords(char *s){
  2. char* ret=(char*)malloc(sizeof(char)*(strlen(s)+1));
  3. //定义新的数组空间
  4. int pre=strlen(s)-1,after=strlen(s)-1;
  5. //一个是记录单词开头的索引
  6. //一个是记录单词末尾的索引
  7. int cur=0,index=0;
  8. while(pre>0){
  9. if(s[pre]==' '){
  10. pre--;
  11. }else{
  12. after=pre;
  13. while(pre>=0&&s[pre]!=' '){
  14. pre--;
  15. }
  16. cur=pre+1;
  17. while(cur<after){
  18. ret[index++]=s[cur];
  19. cur++;
  20. }
  21. ret[index++]=' ';
  22. }
  23. }
  24. //随后,还要判断其末尾是不是空格
  25. //因为ret[index++]=‘’这个语句的原因
  26. if(index>0&&ret[index-1]=' '){
  27. ret[index-1]='\0';
  28. } else{
  29. ret[index]='\0';
  30. }
  31. return ret;
  32. }