代码随想录算法训练营
Day 9 代码随想录算法训练营第九天 |LeetCode151.翻转字符串里的单词 卡码网：55.右旋转字符串
目录
前言
LeetCode151.翻转字符串里的单词
卡码网：55.右旋转字符串
一、LeetCode151.翻转字符串里的单词
1.题目链接
2.思路
（1）如何反转
先反转整个字符串，再逐个反转单词
如何反转单词：双指针
i作为单词起点，j作为单词终点，如果j遇到空格或j为n（到末尾），则说明i与j夹住一个单词，反转
（2）处理空格：双指针
（这里按照空间复杂度O(1)做的）
快指针fast指向要获取的元素，慢指针slow指向元素的新位置
1）字符串首的空格：如果为空格则fast++，直到fast遇到第一个不是空格的字符为止
2）去除单词间的多余空格：
连续空格则移动fast
不是连续空格则将s[fast]放进s[slow]，slow和fast同时移动
3）去掉末尾空格
检查s[0]到s[slow-1]字符串末尾有无空格，若有，则左移slow
4）修改字符串大小
3.题解
class Solution {
public:
void reverse(string& s, int i, int j) {
while (i < j) {
swap(s[i], s[j]);
i++;
j--;
}
}
string cut(string s) {
int slow = 0;
int fast = 0;
int n = s.size();
while (fast < n && s[fast] == ' ') {
fast++;
}
while (slow < n && fast < n) {
if (fast > 0 && s[fast] == ' ' && s[fast - 1] == ' ') {
fast++;
} else {
s[slow] = s[fast];
slow++;
fast++;
}
}
while (s[slow - 1] == ' ' && slow > 0) {
slow--;
}
s.resize(slow);
return s;
}
string reverseWords(string s) {
s = cut(s);
int n = s.size();
reverse(s, 0, n - 1);
int i = 0;
while (i < n) {
int j = i;
while (j < n && s[j] != ' ') {
j++;
}
reverse(s, i, j - 1);
i = j + 1;
}
return s;
}
};
二、卡码网：55.右旋转字符串
1.题目链接
2.思路
先整体反转，再将n-k和k各自反转
示意图
也可以先反转局部，再反转整体
3.题解
先整体后局部
#include<bits/stdc++.h>
using namespace std;
void reverse(string &s,int l,int r)
{
while(l<r)
{
swap(s[l],s[r]);
l++;
r--;
}
}
int main()
{
int k ;
string s;
cin>>k;
cin>>s;
int n=s.size();
reverse(s,0,n-1);
reverse(s,0,k-1);
reverse(s,k,n-1);
cout<<s;
return 0;
}
先局部后整体
#include<bits/stdc++.h>
using namespace std;
void reverse(string &s,int l,int r)
{
while(l<r)
{
swap(s[l],s[r]);
l++;
r--;
}
}
int main()
{
int k ;
string s;
cin>>k;
cin>>s;
int n=s.size();
reverse(s,0,n-k-1);
reverse(s,n-k,n-1);
reverse(s,0,n-1);
cout<<s;
return 0;
}
字符串总结
1、字符串基础：字符串可以用字符数组或string类实现，一般用string类，因为相关接口更完备
2、双指针
（1）双指针实现反转字符
（2）填充问题：先给字符串扩容，再从后向前操作（例如：替换数字为number）
（3）双指针移除元素
快指针指向要获取的元素，慢指针指向元素的新位置
3、反转字符串：设计反转策略，可以先用纸笔写出反转的情况
先反转整体，再反转局部：LeetCode151.翻转字符串里的单词 卡码网：55.右旋转字符串
先反转局部，再反转整体：卡码网：55.右旋转字符串
