1.反转字符串（要求O(1)的额外空间）
LeetCode链接
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
- swap常见的两种交换形式
- 常见的值交换
- 通过位运算
class Solution {
public:
void reverseString(vector<char>& s) {
int l=0, h=s.size()-1;
char temp;
while(l<=h){
// temp = s[l];
// s[l++] = s[h];
// s[h--] = temp;
swap(s[l++], s[h--]);
}
}
};
2. 反转字符串2
LeetCode链接
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
- 在写循环的时候，可以直接每次+2*k
- 每次判断+k是否符超出size的范围
class Solution {
public:
void reverse(string &s, int start, int end){ // 这里是左闭右开
for(int i=start, j=end; i<j; i++, j--){
swap(s[i], s[j]);
}
}
string reverseStr(string s, int k) {
for(int i=0; i<s.size(); i+=(2*k)){
if(i + k <= s.size()){
reverse(s, i, i+k-1);
}else{
reverse(s, i, s.size()-1);
}
}
return s;
}
};
3.替换空格
LeetCode链接
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
- 卡哥建议：对于线性数据结构，填充或者删除，后序处理会高效的多。好好体会一下。(4中的删除后序会跟高效吗)
- resize() 重新分配空间
- 一个指针指向旧的地址，新指针指向新的地址
class Solution {
public:
string replaceSpace(string s) {
int count = 0; // 统计空格出现的次数
for(int i=0; i<s.size(); i++){
if(s[i] == ' '){
count++;
}
}
int i=s.size()-1, j=s.size()+2*count - 1;
s.resize(s.size() + 2*count);
// 从后往前，使用双指针法，快指针指向原来的为末尾，慢指针指向新的末尾
for(; i>=0; i--, j--){
if(s[i] != ' '){
s[j] = s[i];
}else{
s[j] = '0';
s[j-1] = '2';
s[j-2] = '%';
j-=2;
}
}
return s;
}
};
4.反转字符串中的单词
LeetCode链接
- 给你一个字符串 s ，请你反转字符串中 单词 的顺序。
- 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
- 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
- 注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
- 先去除字符串中多余的空格(删除单个字符建议从后向前进行)
- 直接反转整合字符串
- 最后反转字符串中的每个单词
class Solution {
public:
// 1.去除多余的空格
void replaceWhite(string &s){
// 1. 如果字符串开头全是空格，就先遍历high直到不是空格位置
int low = 0, high = 0; // 定义快慢指针
while(high<s.size() && s[high] == ' ') high++;
// 2.去除字符串中间的空格
// while(high < s.size()){
// // 去掉字符串中间冗余的空格
// if(s[high]!=' ' && s[high+1] == ' '){
// s[low++] = s[high];
// s[low++] = ' ';
// }else if(s[high] != ' '){
// s[low++] = s[high];
// }
// high++;
// }
for(; high<s.size(); high++){
if(high-1 > 0 && s[high-1]==s[high] && s[high]== ' '){ // 如果当前字符是' '并且前一个字符是空
continue; // 不做任何处理
}else{
s[low++] = s[high]; // 如果不是空格，并且是字符后的第一个空格就复制
}
}
// 3.去除字符串末尾的空格
if(low - 1 > 0 && s[low-1] == ' '){
s.resize(low-1);
}else{
s.resize(low);
}
}
// 双指针法快速删除多余空格
void removeExtraSpace(string &s){
int low = 0;
for(int i=0; i<s.size(); i++){
if(s[i] != ' '){
if(low != 0) s[low++] = ' ';
while(i < s.size() && s[i] != ' '){
s[low++] = s[i++];
}
}
}
s.resize(low);
}
// 2.反转整个字符串
void reverseString(string &s){
for(int i=0, j=s.size()-1; i<=j; i++, j--){
swap(s[i], s[j]);
}
}
// 3.反转每个单词
void reverseSingleWord(string &s, int start, int end){
for(int i=start, j=end; i<j; i++, j--){ // 左闭右闭
swap(s[i], s[j]);
}
}
string reverseWords(string s) {
replaceWhite(s);
reverseString(s);
for(int i=0, j=0; j<=s.size(); j++){
if(j==s.size() || s[j]==' '){ // 到达最后一个单词 或者是遇到了空格
reverseSingleWord(s, i, j-1); //
i = j+1;
}
}
return s;
}
};
5. 剑指Offer58-II.左旋转字符串
LeetCode链接文章来源：https://www.toymoban.com/news/detail-439552.html
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。文章来源地址https://www.toymoban.com/news/detail-439552.html
- 先反转前半部分和后半部分，再整体反转
class Solution {
public:
void reverse(string &s, int start, int end){
while(start <= end){
swap(s[start++], s[end--]);
}
}
string reverseLeftWords(string s, int n) {
// 1.先反转前半部分和后半部分，再反转整体
reverse(s, 0, n-1);
reverse(s, n, s.size()-1);
reverse(s, 0, s.size()-1);
return s;
}
};
到了这里，关于第8天-代码随想录刷题训练-字符串● 344.反转字符串 ● 541. 反转字符串II ● 剑指Offer 05.替换空格 ● 151.翻转字符串里的单词 ● 剑指Offer58-II.左旋转字符串的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
