锐客网

  1. 首页 > 睿知 > it技术 > >

C++|算法-字符串（反转字符串里的单词）

c++算法

算法-字符串：反转字符串里的单词 【C++|算法-字符串（反转字符串里的单词）】给定一句英文，要求倒叙输出每一个单词，并删除单词两边冗余的空格（句子前面和后面没有空格，两个单词直接只有一个空格）。
注意：不可以使用额外的辅助空间，原地修改字符串。

#include #include using namespace std; //首先去除原字符串多余的空格，然后反转整个字符串，然后根据空格判定并反转单词void removeSpaces(string &s){ //移除字符串最好从后向前遍历 //去除多余的空格，执行完此循环后，每个单词之间最多保留一个空格 for(int i = s.size()-1; i > 0; i--){ if(s[i] == s[i-1] && s[i] == ' '){ s.erase(s.begin()+i); } } //错误写法?? 原因：因为移除了s[i]之后，我们希望要移除的元素还是原s[i]的位置，但是这种写法里i是递增的 //如果s为"hello"（前面有4个空格），那么这段代码输出为： //进入循环时的长度s.size()==9 //移除元素的下标是：0 移除的元素是： //移除元素后的长度s.size()==8 //进入循环时的长度s.size()==8 //移除元素的下标是：1 移除的元素是： //移除元素后的长度s.size()==7 //进入循环时的长度s.size()==7 //进入循环时的长度s.size()==7 //进入循环时的长度s.size()==7 //进入循环时的长度s.size()==7 //hello //for(int i = 0; i < s.size()-1; i++){ //cout<<"进入循环时的长度s.size()=="<0 && s[0]==' '){ s.erase(s.begin()); } //判定字符串最后一个字符是不是有空格 if(s.size()>0 && s[s.size()-1]==' '){ s.erase(s.end()-1); } }//根据空格判定并反转单词 void reverseWords(string &s){ int begin = 0; //单词开始的下标 int end = 0; //单词结束的下标 for(int i = 0; i < s.size(); i++){ if(i>0 && s[i]==' '){ end = i; reverse(s.begin()+begin, s.begin()+end); begin = i+1; //begin一定小于s.size()-1，因为前面判定字符串末尾不能是空格 } //处理最后一个单词 if(i == s.size()-1){ end = i+1; reverse(s.begin()+begin, s.begin()+end); } } }int main() { string s = "helloworld ! I amaprogrammer!"; removeSpaces(s); reverse(s.begin(), s.end()); reverseWords(s); cout<

输出结果为：
programmer! a am I ! world hello

需要注意的是，erase函数本身就是O(n)的函数，因此removeSpaces函数时间复杂度达到了O(n^2)。使用双指针方法对removeSpaces函数进行改进，字符串是特殊的数组。
#include #include using namespace std; void removeSpaces(string &s){ int slow = 0; int fast = 0; while(s.size()>0 && fast0 && s[fast]==s[fast-1] && s[fast]==' '){ //其实fast==1的话，s[0]==s[1]==' '，所以fast是大于1的 continue; //直接fast++ } else{ s[slow++] = s[fast]; } } //判定字符串最后一个字符是不是有空格 if(slow>0 && s[slow-1]==' '){ s.resize(slow-1); //重新设置字符串大小 } else{ s.resize(slow); //重新设置字符串大小 } }int main() { string s = " helloworld ! I amaprogrammer!"; removeSpaces(s); cout<

    推荐阅读


    上一篇：C++|算法-栈和队列（用栈实现队列）

    下一篇：C++|算法-优化（以空间换时间，找n个小写字母中出现次数最多的字母）