[动画详解]LeetCode151.翻转字符串里的单词

💖💖💖欢迎来到我的博客，我是anmory💖💖💖
又和大家见面了
欢迎来到动画详解LeetCode算法系列
用通俗易懂的动画让算法题不再神秘
先来自我推荐一波
个人网站欢迎访问以及捐款
推荐阅读
如何低成本搭建个人网站
专栏:动画详解leetcode算法题
C语言知识

题目描述

---

解题思路

我们的思路就是先让整句话变得正常，也就是去掉开头和结尾多余的空格
再去掉单词之间多余的空格
当句子变得正常之后，我们就可以先将整个字符串反转，再将每一个单词反转
这样就做到反转字符串里的单词了

---

动画详解

---

代码实现

// 翻转字符串中指定范围的字符
void reversePos(char* s, int start, int end)
{int left = start;int right = end;char* tmp;while (left <= right){tmp = s[right];s[right] = s[left];s[left] = tmp;left++;right--;}
}// 去除单词中多余的空格
void delSpace(char* s)
{// 使用双指针来删除单词中多余的空格int left = 0;int right = strlen(s)-1;// 删除第一个单词之前的空格while(s[left] == ' '){left++;}// 删除最后一个单词之后的空格while(s[right] == ' '){right--;}// 删除单词中间多余的空格,双指针法删除int slow = 0;for(int i = left;i<=right; i++){// 如果遇到两个及以上空格那么就跳过if(s[i]==' ' && s[i+1]==' '){continue;}s[slow] = s[i];slow++;// i不++，因为在循环内部i已经在++了}s[slow] = '\0';// 在最后添加\0
}char* reverseWords(char* s) 
{// 先删除两端和中间多余的空格delSpace(s);// 反转整个字符串reversePos(s,0,strlen(s)-1);// 反转字符串里的单词int slow = 0;// 指向每一个单词开头的指针for(int i = 0; i<=strlen(s); i++)// 遍历字符串，包括\0{if(s[i]==' '|| s[i]=='\0')// 当位置为空或\0就说明单词结束{reversePos(s,slow,i-1);// 此时i所在的地方字符是空格slow = i+1;}}return s;
}

---

复杂度分析

可以看出循环的层数都是一层，因此时间复杂度为O(n)

---

总结

💖💖💖非常感谢各位的支持💖💖💖
我们共同进步
本系列持续更新，关注我，带你手撕算法题
下期再见