字符串是数组的形式,使用O(1)的空间将字符串反转
代码
class Solution {
public:
void reverseString(vector<char>& s) {
for(int i=0,j=s.size()-1;i<s.size()/2;i++,j--){
swap(s[i],s[j]);
}
}
};
代码
class Solution {
public:
void reverseString(vector<char>& s) {
int left = 0;
int right = s.size()-1;
while(left<=s.size() && right>=0 && right>left){
swap(s[left],s[right]);
left++;
right--;
}
}
};
int temp = s[i];
s[i] = s[j];
s[j] = temp;
//开始s[i]==a s[j]==b
s[i]^=s[j]; //s[i]=a^b a异或b
s[j]^=s[i]; //s[j]=b^(a^b)=a
s[i]^=s[j]; //s[i]=a^(a^b)=b
//最终s[i]==b s[j]==a
字符串s每计数至2k个字符,就反转这2k个字符的前k个字符;
剩余字符少于k个,就将剩余字符全部反转;如果剩余字符大于等于k个且小于2k个,反转前k个字符
i+=(2*k),i每次移动2k个距离
代码
class Solution {
public:
string reverseStr(string s, int k) {
for(int i=0;i<s.size();i+=2*k){
if(i+k<=s.size()){
reverse(s.begin()+i,s.begin()+i+k);
continue;//继续寻找下一组
}
reverse(s.begin()+i,s.end());
}
return s;
}
};
代码
class Solution {
public:
string reverseStr(string s, int k) {
for(int i=0;i<s.size();i+=2*k){
if(i+k<=s.size()){
reverse(s.begin()+i,s.begin()+i+k);
}
else{
reverse(s.begin()+i,s.end());
}
}
return s;
}
};
字符串s(包含小写字母和数字字符)将数字字符替换位number,字母不变
不能简单地遇到数字就将其替换位number,因为数字是1个字符,而number是6个字符,直接替换的话,大小不对等,需要扩充大小
i指向新串的末尾,j指向旧串的末尾,从后向前遍历
详细的遍历过程
原因
从前向后遍历的话,遇到数字字符,就需要将该数字字符后面的字符向后移动5个格,然后才可以填充number,时间复杂度是O(n^2)
代码
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int main(){
string s;
cin>>s;
int count = 0;
int oldsize = s.size();
for(int i=0;i<s.size();i++){
if(s[i]>='0'&& s[i]<='9'){
count++;
}
}
s.resize(s.size()+count * 5);
int newsize = s.size();
for(int i=newsize-1,j=oldsize-1;j<i;i--,j--){
if(s[j]>='a'&&s[j]<='z'){
s[i]=s[j];
}
else{
s[i] = 'r';
s[i-1] = 'e';
s[i-2] = 'b';
s[i-3] = 'm';
s[i-4] = 'u';
s[i-5] = 'n';
i -= 5;
}
}
cout<<s<<endl;
}
反转字符串s中单词的顺序? ?输入的字符串的开头或结尾可能会存在多个空格,单词与单词之间可能也存在多个空格
反转字符串时,仅仅在单词与单词之间有1个空格?
关键是字符串去除空格的逻辑,反转的逻辑:整体反转+局部反转
fast指向单词,slow指向单词所在的新的位置??
在每个单词移动之前,添加一个空格,第一个单词除外
实例
代码
class Solution {
public:
string reverseWords(string s) {
//1 移除多余空格
int slow = 0;
for(int fast=0;fast<s.size();fast++){
if(s[fast]!=' '){//找到了单词
//单词前添加一个空格
if(slow!=0){
s[slow] = ' ';
slow++;
}
//将单词移动到新的位置
while(fast<s.size() && s[fast]!=' '){
s[slow] = s[fast];
slow++;
fast++;
}
}
}
s.resize(slow);
//2 反转单词
//①整体反转
reverse(s.begin(),s.end());//左闭右开
//②单词反转
int start = 0;
for(int i=0;i<=s.size();i++){//reverse左闭右开
if(s[i]==' ' || i==s.size()){//每个单词后有空格,最后一个单词后没空格
reverse(s.begin()+start,s.begin()+i);//reverse左闭右开
start = i + 1;
}
}
return s;
}
};
字符串前有空格? 字符串中有多余空格? ? 字符串后有多余空格
代码
class Solution {
public:
void removespace(string& s){
int slow = 0;
int fast = 0;
//去掉前面的空格,寻找有效的字符,持续过程,开头可能有多个空格
while(fast<s.size()&&s[fast]==' '){
fast++;
}
//去掉中间多余的空格,如果原字符串末尾有空格的话,会使得末尾有1个空格
for(;fast<s.size();fast++){//使用fast+1的话,fast+1可能会越界
if(fast-1>0 && s[fast]==s[fast-1] && s[fast]==' '){
continue;
}
else{//不是空格时,直接将fast位置处的值赋值给slow,然后slow向后移动一个位置
s[slow] = s[fast];
slow++;}
}
//去掉末尾的1个空格,因为上述代码的slow++了,slow会移动到多一个位置的地方,所以判断slow-1
if(slow-1>0&&s[slow-1]==' '){
s.resize(slow-1);
}
else{//原字符串末尾没有空格
s.resize(slow);
}
}
string reverseWords(string s) {
removespace(s);//去除字符串中多余的空格
reverse(s.begin(),s.end());//左闭右开,将字符串全部反转
int start = 0;//反转单词的首字母的位置
for(int i=0;i<=s.size();i++){
if(s[i]==' ' || i==s.size()){//这里有两种情况,单词以空格结尾,单词是最后一个单词
reverse(s.begin()+start,s.begin()+i);
start = i + 1;//下一个单词的首字母的位置
}
}
return s;
}
};
将字符串s后面的k个字符移到字符串的前面,实现右旋转操作
代码
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
string s;
int k;
cin>>k;
cin>>s;
//整体反转
reverse(s.begin(),s.end());
//局部反转
reverse(s.begin(),s.begin()+k);
reverse(s.begin()+k,s.end());
cout<<s<<endl;
}
代码
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
string s;
int k;
cin>>k;
cin>>s;
//整体反转
reverse(s.begin(),s.begin()+s.size()-k);
//局部反转
reverse(s.begin()+s.size()-k,s.end());
reverse(s.begin(),s.end());
cout<<s<<endl;
}