可以做数学题的网站/链接地址

1.问题描述

分割字符串这种操作在java中其实是有API直接调用的，但是在C++中没有，今天就来分析实现一个可以去除冗余空格并且分割字符串的可复用的函数！

2.解决方案

方法一：使用string库函数完成

使用STL进行字符串分割涉及到string类的两个函数find和substr：
1、find函数
原型：size_t find (const string& str, size_t pos = 0) const;
功能：查找子字符串第一次出现的位置。
参数说明：str为子字符串，pos为初始查找位置。
返回值：如果是字串返回第一次出现的位置，如果不是返回string::npos(为-1或者4294967295都算对！！！！！！！！！！)
2、substr函数(左起始，右长度)
原型：string substr (size_t pos = 0, size_t n = npos) const;
功能：获得子字符串。
参数说明：pos为起始位置（默认为0），n为要截取字符串的长度
返回值：一个子字符串，从其指定的位置开始
备注：如果没有指定长度_Count或_Count+_Off超出了源字符串的长度，则子字符串将延续到源字符串的结尾

第一步：去重冗余空格操作

1.使用string库函数erase()直接移除

逻辑很简单就遇见多余空格就移除，但是移除函数最快，自己实现用双指针也得o(n)27. 移除元素，那么整体代码就是o(n^2)了很慢

void removeExtraSpaces_low(string& s) {//1.删除中间的空格for(int i=s.size()-1;i>0;i--) {if (s[i]==s[i - 1]&&s[i]==' ') {s.erase(s.begin() + i);}}//2.删除字符串最后面的空格if (s.size() > 0 && s[s.size() - 1] == ' ') {s.erase(s.begin() + s.size() - 1);}//3.删除字符串最前面的空格if (s.size() > 0 && s[0] == ' ') {s.erase(s.begin());}
}

2.使用双指针

1.使用双指针法来去移除空格，最后resize(重新设置)一下字符串的大小，就可以做到O(n)的时间复杂度。
2.fastIndex走的快，slowIndex走的慢，最后slowIndex就标记着移除多余空格后新字符串的长度。
3.其实就是一个字符串有很多没用的字符，fastIndex在前面进行筛选正确的字符就赋给slowIndex，错误的fastIndex就直接略过，所以最后slowIndex走过的就是真正的目标字符串！

//移除冗余空格：使用双指针(快慢指针法) O(n)的算法
//去掉冗余空格 " This is  a  sentence with 7 tokens  " --变为-->"This is a sentence with 7 tokens"
void removeExtraSpaces(string& s) {//1.定义快指针，慢指针int slowIndex=0, fastIndex=0;//2.去掉字符串前面的空格while (s.size() > 0 && fastIndex<s.size()&&s[fastIndex]==' '){fastIndex++;}//3.去掉字符串中间部分的冗余空格for (;fastIndex<s.size();fastIndex++) {//最妙的地方!!!!!!!//遇到中间多余的空格(从第二个空格开始算多余的)，直接略过，如果是第一个空格或者字母直接赋值给慢指针if (fastIndex-1>0 && s[fastIndex-1]==s[fastIndex] && s[fastIndex]==' '){continue;}else{s[slowIndex++]=s[fastIndex];}}//4.去掉字符串末尾的空格，因为如果字符串原本最后有很多空格，第一个空格是会被记录到slowIndex中的，所以要清楚一下if(slowIndex-1> 0 && s[slowIndex-1]==' ') {s.resize(slowIndex - 1);} else {s.resize(slowIndex); // 重新设置字符串大小}
}

第二步：将标准的字符串进行分割

//"This is a sentence with 7 tokens"
//input		输入的字符串
//c			分割符
//segment	输出分割字符片段(集)
bool strSegmentation(string input,char c,vector<string>& segment){if(input.size()==0) return false;while(1){int index=input.find(c);if(index==-1){segment.push_back(input);break;} else{string str=input.substr(0,index);input.erase(0,index+1);segment.push_back(str);}}if(segment.size() == 0) return false;else return true;
}

第三步：合起来看效果

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
using namespace std;void removeExtraSpaces_low(string& s) {//1.删除中间的空格for(int i=s.size()-1;i>0;i--) {if (s[i]==s[i - 1]&&s[i]==' ') {s.erase(s.begin() + i);}}//2.删除字符串最后面的空格if (s.size() > 0 && s[s.size() - 1] == ' ') {s.erase(s.begin() + s.size() - 1);}//3.删除字符串最前面的空格if (s.size() > 0 && s[0] == ' ') {s.erase(s.begin());}
}//移除冗余空格：使用双指针(快慢指针法) O(n)的算法
//去掉冗余空格 " This is  a  sentence with 7 tokens  " --变为-->"This is a sentence with 7 tokens"
void removeExtraSpaces(string& s) {//1.定义快指针，慢指针int slowIndex=0, fastIndex=0;//2.去掉字符串前面的空格while (s.size() > 0 && fastIndex<s.size()&&s[fastIndex]==' '){fastIndex++;}//3.去掉字符串中间部分的冗余空格for (;fastIndex<s.size();fastIndex++) {//最妙的地方!!!!!!!//遇到中间多余的空格(从第二个空格开始算多余的)，直接略过，如果是第一个空格或者字母直接赋值给慢指针if (fastIndex-1>0 && s[fastIndex-1]==s[fastIndex] && s[fastIndex]==' '){continue;}else{s[slowIndex++]=s[fastIndex];}}//4.去掉字符串末尾的空格，因为如果字符串原本最后有很多空格，第一个空格是会被记录到slowIndex中的，所以要清楚一下if(slowIndex-1> 0 && s[slowIndex-1]==' ') {s.resize(slowIndex - 1);} else {s.resize(slowIndex); // 重新设置字符串大小}
}//input		输入的字符串
//c			分割符
//segment	输出分割字符片段(集)
bool strSegmentation(string input,char c,vector<string>& segment){if(input.size()==0) return false;while(1){int index=input.find(c);if(index==-1){segment.push_back(input);break;} else{string str=input.substr(0,index);input.erase(0,index+1);segment.push_back(str);}}if(segment.size() == 0) return false;else return true;
}int main(){string str = "    This is     a    sentence with 7 tokens";//1.去除冗余空格removeExtraSpaces(str);cout<<str<<endl;//2.分割字符串vector<string> segment;if(!strSegmentation(str, ' ' ,segment)) return 0;for (auto item: segment) {cout<<item<<endl;}return 0;
}/*
输出结果
This is a sentence with 7 tokens
This
is
a
sentence
with
7
tokens
*/

方法二：使用string和char[]互相转化加char[]库函数strtok()一步完成

strtok()用法总结

思路很简单，先把string转化为char，然后就是在strtok()分割过程中产生的char*直接赋值给string，然后收集就好，这个做法去重冗余空格加分割字符串一步到位，非常的nice！！

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cstring>
using namespace std;int main() {//1.准备要分割的字符串和vector<string> ans;string str="      This    is  a sentence with  7 tokens      ";char* sentence=(char *)str.data();//2.开始分割char* tokenPtr=strtok(sentence," ");while(tokenPtr!=NULL) {//关键点：char*直接转化为string并放入vector中ans.push_back(tokenPtr);tokenPtr = strtok(NULL, " ");}//3.输出验证for (auto item: ans) {cout<<item<<endl;}return 0;
}