[TOC]
一、分割字符串
1816. 截断句子（简单难度）
class Solution {
public:
/*解析：分割+截断+拼接
最简单的思路是先分割字符串为单词数组，然后反转数组元素，再拼接单词并添加上新的空格，
该思路的难点是根据空格分割字符串为单词数组。
*/
string truncateSentence(string s, int k) {
// 分割字符串为字符串数组
vector<string> words=splitWord(s);
// 截断字符串数组
vector<string> temp(words.begin(),words.begin()+k);
// 拼接为一个字符串
string res;
for(int i=0;i<temp.size();i++) {
if(i==0)res+=temp[i];
else{
res+=" ";
res+=temp[i];
}
}
return res;
}
vector<string> splitWord(string str){
vector<string> words;
string word;
for(char c:str){
// 遇到空格字符并且word有字符就添加word并且重置word，保证不会添加开头空格
if(c==' '&&word.size()>0){
words.push_back(word);
word="";
}
// 不添加空格
else if(c!=' '){
word+=c;
}
}
// str末位不一定有空格
if(word.size()) words.push_back(word);
return words;
}
};
151. 翻转字符串里的单词（中等难度）
剑指 Offer 58 - I. 翻转单词顺序（简单难度）
方法一：分割+反转+拼接
class Solution {
public:
/*解析：这道题是以空格分隔单词，难点在于开头、中间、结尾的空格数量都不确定。
方法一：分割+反转+拼接
最简单的思路是先分割字符串为单词数组，然后反转数组元素，再拼接单词并添加上新的空格，
该思路的难点是根据空格分割字符串为单词数组。
*/
string reverseWords(string s) {
// 分割字符串为字符串数组
vector<string> words=splitWord(s);
// 反转字符串数组
reverse(words.begin(),words.end());
// 拼接为一个字符串
string res;
for(int i=0;i<words.size();i++) {
if(i==0)res+=words[i];
else{
res+=" ";
res+=words[i];
}
}
return res;
}
vector<string> splitWord(string str){
vector<string> words;
string word;
for(char c:str){
// 遇到空格字符并且word有字符就添加word并且重置word，保证不会添加开头空格
if(c==' '&&word.size()>0){
words.push_back(word);
word="";
}
// 不添加空格
else if(c!=' '){
word+=c;
}
}
// str末位不一定有空格
if(word.size()) words.push_back(word);
return words;
}
};
方法二：原地双指针
class Solution {
public:
/*解析：这道题是以空格分隔单词，难点在于开头、中间、结尾的空格数量都不确定。
方法二：原地双指针（不容易想到）
因为该方法需要反转，所以从后向前遍历：
left，right都从最后一个元素出发，right先走到第一个字符处，left=right，走到第一个空格处
[left+1,right]就是单词所在索引区间，循环重复
*/
string reverseWords(string s) {
string res;// 结果字符串
int n = s.size();
if(n == 0) return res;
int left =n-1;// 左指针
int right = n - 1;// 右指针
while(right >= 0){
//从后往前寻找第一字符（如果不是空且没有到头，right就左移）
while(right >= 0 && s[right] == ' ') right--;
if(right < 0) break;
//从后往前寻找第一个空格
int left = right;
while( left >= 0 && s[left] != ' ' ) left--;
//添加单词到结果，单词所在位置[left+1,right]
res += s.substr(left + 1, right - left);
res += ' ';
//继续往前分割单词
right = left;
}
//去除最后一个字符空格
if (!res.empty()) res.pop_back();
return res;
}
}
186. 翻转字符串里的单词 II（中等难度）
三、旋转字符串
剑指 Offer 58 - II. 左旋转字符串（简单难度）
class Solution {
public:
/*解析：本题的意思是将字符串的[0,n)移动到字符串的末尾
方法一：列表遍历拼接（借助额外内存空间）:先拼接[n,s.length())，再拼接[0,n)
方法二：列表遍历拼接（取余操作简化）
方法三：3次反转：反转[0,n);反转[n,s.length())；反转[0,s.length())
*/
string reverseLeftWords(string s, int n) {
//方法一：列表遍历拼接（借助额外内存空间）
// string res;
// // 获取[n,s.length())加入res中
// for(int i=n;i<s.length();i++){
// res+=s[i];
// }
// // 获取[0,n)加入res中
// for(int i=0;i<n;i++){
// res+=s[i];
// }
// return res;
//方法二：列表遍历拼接（取余操作简化）
// string res;
// int len=s.length();
// for(int i=n;i<n+len;i++){
// res+=s[i%len];
// }
// return res;
//方法三：巧妙反转
reverse(s.begin(),s.begin()+n);
reverse(s.begin()+n,s.end());
reverse(s.begin(),s.end());
return s;
}
};
796. 旋转字符串（简单难度）
class Solution {
public:
/*本题是判断s是否能够通过多次左旋转来得到goal
我们已经知道左旋转字符串的操作（剑指 Offer 58 - II. 左旋转字符串）
那么可以通过模拟左旋转来判断，左旋转的次数是有限的：1~s.length()
*/
bool rotateString(string s, string goal) {
// 旋转1~s.length()次
for(int n=1;n<=s.length();n++){
// 左旋转1个字符
reverse(s.begin(),s.begin()+1);
reverse(s.begin()+1,s.end());
reverse(s.begin(),s.end());
// 检查本次旋转后是否==goal
if(s==goal) return true;
}
return false;
}
};
三、字符串比较大小
剑指 Offer 45. 把数组排成最小的数（中等难度）
class Solution {
public:
/*解析：本题是一个排序问题，但难点在于如何比较2个数？
小的数排在前面不一定数就小，例如3和30,330>303.
解决方案是将整数转成字符串，这样排序a和b两个数时，可以比较a+b和b+a谁更大
在代码实现时需要知道如何实现自定义排序方式
*/
// 自定义排序方式
static bool cmp(string& a,string& b){
return a + b < b + a;
}
string minNumber(vector<int>& nums) {
// 将整数数组转换为字符串数组
vector<string> strs;
for(int num:nums) strs.push_back(to_string(num));
// 自定义排序
sort(strs.begin(), strs.end(), cmp);
// 将字符串数组拼接为字符串
string res;
for(string s : strs) res+=s;
return res;
}
};