代码随想录算法训练营第九天|151.翻转字符串里的单词，卡码网：55.右旋转字符串

151.翻转字符串里的单词

题目链接：151. 反转字符串中的单词 - 力扣（LeetCode）

题目要求是给定一个字符串，要求把里面的单词进行倒序输出，并且要删除里面多余的空格。

我的第一种做法是把里面的字符串提取出来，然后倒序放入一个新的字符串中，这样空间复杂度会比较高，也AC了，但肯定不是最优的解法。

class Solution {
public:
    string reverseWords(string s) {
    string ss[10010];
    int index = 0;
    int i = 0;
    while (i < s.size())
    {
        while (s[i] == ' '&&i<s.size()) i++;
        int start = i;
        while (s[i] != ' '&&i<s.size()) i++;
        int end = i - 1;
        string temp = "";
        for (int j = start; j <= end; j++)
        {
            temp += s[j];
        }
        ss[index] = temp;
        index++;
        while (s[i] == ' '&&i<s.size()) i++;
    }
    string result;
    for (int i = index - 1; i >= 0; i--)
    {
        result += ss[i];
        if(i!=0) result += ' ';
    }
    return result;
}
};

后来参考了一下随想录的题解，解题思路如下：

1.使用双指针算法去掉多余的空格

2.将整个字符串反转

3.将其中的每个单词再次反转

第二步和第三步都比较容易解决，第一步是比较难想到的，利用双指针算法来去除多余的空格。基本思路是：

1.快指针先行，去除前置空格

2.遇到单词的首字母后时，快指针给慢指针持续赋值。需要注意的是，两个单词之间需要加上空格，这里需要慢指针单独处理。

3.快指针遇到空格继续向前，寻找下一个单词，直到快指针遍历完整个字符串

后面的两个反转操作手写一个反转函数就可以实现，这里就不细讲了。代码实现如下：
 

class Solution {
public:
void reverse(string &s,int start,int end)
{
	int mid=(end-start+1)/2-1;
	for(int i=0;i<=mid;i++)
	{
		swap(s[start+i],s[end-i]);
	}
}
    string reverseWords(string s) {
        int slowindex=0;
        int fastindex=0;
        while(fastindex<s.size()&&s[fastindex]==' ') fastindex++;
        for(;fastindex<s.size();fastindex++)
        {
            if(slowindex!=0) s[slowindex++]=' ';
            while(fastindex<s.size()&&s[fastindex]!=' ')
            {
                s[slowindex]=s[fastindex];
                slowindex++;
                fastindex++;
            }
            while(fastindex<s.size()&&s[fastindex]==' ') fastindex++;
            fastindex--;
        }
        s.resize(slowindex);
        reverse(s,0,s.size()-1);
        int i=0;
        int startx=0;
        int endx=0;
        cout<<s.size()<<' '<<s<<endl;
        while(i<s.size())
        {
        	while(s[i]!=' '&&i<s.size()) i++;
        	endx=i-1;
        	reverse(s,startx,endx);
        	startx=endx+2;
        	i=startx;
        	cout<<i<<' '<<startx<<' '<<endx<<endl;
		}
        return s;
    }
};

总结就是，学到了通过双指针法去掉多余的元素，而且时间，空间复杂度较低，非常精妙。

卡码网：55.右旋转字符串

题目链接：55. 右旋字符串（第八期模拟笔试） (kamacoder.com)

输入一个字符串和一个数字，需要将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。示例如下：

对于输入字符串 "abcdefg" 和整数 2，函数应该将其转换为 "fgabcde"。

我一开始的思路是将一部分元素延伸到原字符串的后面，然后从后向前赋值来实现元素替换，也AC了

#include<iostream>
using namespace std;
int main()
{
    string s;
    int k;
    cin>>k>>s;
    int len=s.size();
    for(int i=0;i<=len-k-1;i++) s+=s[i];
    for(int i=len-k;i<s.size();i++) s[i-(len-k)]=s[i];
    s.resize(len);
    cout<<s;
}

后来看了随想录的题解，思路如下：

1.将整个字符串反转

2.将前k个和剩下的再次反转

确实精妙啊，不看到自己确实想不到。以此类推，左转的话就是后k个和剩下的再次反转即可。

#include<iostream>
using namespace std;
void reverse(string &s,int start,int end)
{
	int mid=(end-start+1)/2-1;
	for(int i=0;i<=mid;i++) swap(s[start+i],s[end-i]);
}
int main()
{
	string s;
	int k;
	cin>>k>>s;
	reverse(s,0,s.size()-1);
	reverse(s,0,k-1);
	reverse(s,k,s.size()-1);
	cout<<s;
}

总结，感觉字符串的难题就是各种花里胡哨的反转，而且一般都是对空间复杂度有严格要求，尽量在原地完成。KMP放在明天学好了，顺便做一个字符串和双指针的总结。