344、反转字符串
·两两交换
给字符串翻个面doge
题目链接：https://leetcode.cn/problems/reverse-string/submissions/
思路：首尾交换
代码实现：
时间复杂度O(n)
空间复杂度O(1)
class Solution {
public:
void reverseString(vector<char>& s) {
for(int i=0;i<s.size()/2;i++){
swap(s[i],s[s.size()-i-1]);
}
}
};
异或运算实现数组交换：
class Solution {
public:
void reverseString(vector<char>& s) {
int j=s.size()-1;
int i=0;
for(;j>i;i++,j--){
s[j]^=s[i];
s[i]^=s[j];
s[j]^=s[i];
}
}
};
收获摘要：异或运算在数组交换上更快一些
541、反转字符串Ⅱ
·模拟法
给数组局部翻面~
思路：根据题目模拟就行
考虑循环怎么减少运算：i步长为2k
代码实现：
时间复杂度O(n^2)
空间复杂度O(1)
class Solution {
public:
void myswop(string& s,int n,int m){
for(int i=n,j=m;i<j;i++,j--){
s[i]^=s[j];
s[j]^=s[i];
s[i]^=s[j];
}
}
string reverseStr(string s, int k) {
for(int i=0;i<s.size();i=i+2*k){
if(i+k>s.size()){
myswop(s,i,s.size()-1);
}
else{
myswop(s,i,i+k-1);
}
}
return s;
}
};
收获摘要：理清题目意思，模拟考虑的情况要全而精简
剑指Offer 05、替换空格
·双指针法
移除元素进化版–>替换元素！
题目链接：https://leetcode.cn/problems/ti-huan-kong-ge-lcof/submissions/
思路：用%20替换空格，数组变长了
扩充原有数组
用双指针从后往前填充
代码实现：
时间复杂度O(n)
空间复杂度O(1)
class Solution {
public:
string replaceSpace(string s) {
int c=0;
int l=s.size()-1;
int rl=0;
for(int i=0;i<=l;i++){
if(s[i]==' ')c++;
}
s.resize(s.size()+c*2);
rl=l+c*2;
while(l>=0){
if(s[l]!=' '){
s[rl]=s[l];
rl--;
l--;
}
else
{
s[rl]='0';
s[rl-1]='2';
s[rl-2]='%';
rl=rl-3;
l--;
}
}
return s;
}
};
收获摘要：双指针一如既往的快啊。学会手动调已有数组长度doge。
学习的文章链接：https://programmercarl.com/剑指Offer05.替换空格.html#其他语言版本
151.翻转字符串里的单词
·模拟！模拟！
本来可以水，不用辅助空间就开始折磨，折磨！啊！泪射了出来.jpg
题目链接：https://leetcode.cn/problems/reverse-words-in-a-string/discussion/
思路：用双指针移除多余空格
反转字符
反转单词
代码实现：
时间复杂度O(n)
空间复杂度O(1)
class Solution {
public:
void myswop(string& s,int n,int m){
for(int i=n,j=m;i<j;i++,j--){
s[i]^=s[j];
s[j]^=s[i];
s[i]^=s[j];
}
}
string reverseWords(string s) {
int slow=0;
int l;
int fast;
for(fast=0;fast<s.size();fast++){//去空格
if(s[fast]!=' ')//只有是字母时处理，手动添加空格后添加单词而不是添加字母
{
cout<<"fast="<<fast<<endl;
if(slow!=0){//不是fast!!是slow的第一个单词!!（第一个单词已经添加完）orz
s[slow]=' ';
slow++;
}
while(s[fast]!=' '&&fast<s.size()){
s[slow]=s[fast];
slow++;
fast++;
}
}
}
l=slow;
s.resize(l);
myswop(s,0,l-1);
slow=0;
for(int i=0;i<=l;i++){//这里的边界是数组末尾+1
if(i==l||s[i]==' '){
myswop(s,slow,i-1);
slow=i+1;//下一个单词的头下标
}
}
return s;
}
};
收获摘要：代码就像裹脚布，又臭又长doge
模拟的过程简直折磨
coding三分钟，debug一小时orz
模拟过程渐渐多了起来，最好使用自定义函数，这样模拟过程会更加清晰。
剑指Offer58-Ⅱ、左旋转字符串
·局部-整体反转
翻翻乐doge
题目链接：https://leetcode.cn/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/submissions/
思路：1、开新数组
2、不开新数组：
0-n-1 局部反转
n-size-1 局部反转
整体反转
代码实现：
时间复杂度O(n)
空间复杂度O(1)
class Solution {
public:
void myswop(string& s,int n,int m){
for(int i=n,j=m;i<j;i++,j--){
s[i]^=s[j];
s[j]^=s[i];
s[i]^=s[j];
}
}
string reverseLeftWords(string s, int n) {
myswop(s,0,n-1);
myswop(s,n,s.size()-1);
myswop(s,0,s.size()-1);
return s;
}
};
收获摘要：啪！的一下，很快就打完了。思路很巧妙~
学习的文章链接：https://programmercarl.com/剑指Offer58-II.左旋转字符串.html#其他语言版本
学习时长：4h40min
本来以为今天会快一些的，理解得很快，也有思路，但是debug用了很久……
原文地址：http://www.cnblogs.com/tinct/p/16852990.html
