代码随想录算法训练营
Day 9 代码随想录算法训练营第九天 |LeetCode151.翻转字符串里的单词 卡码网:55.右旋转字符串
目录
- 代码随想录算法训练营
- 前言
- LeetCode151.翻转字符串里的单词
- 卡码网:55.右旋转字符串
- 一、LeetCode151.翻转字符串里的单词
- 1.题目链接
- 2.思路
- 3.题解
- 二、卡码网:55.右旋转字符串
- 1.题目链接
- 2.思路
- 3.题解
- 字符串总结
前言
LeetCode151.翻转字符串里的单词
讲解文档
卡码网:55.右旋转字符串
讲解文档
一、LeetCode151.翻转字符串里的单词
1.题目链接
LeetCode151.翻转字符串里的单词
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.题目链接
卡码网:55.右旋转字符串
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.右旋转字符串