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];
}
}
};
識訓摘要：異或運算在陣列交換上更快一些
學習的文章鏈接：https://programmercarl.com/0344.反轉字串.html#其他語言版本
541、反轉字串Ⅱ
·模擬法
給陣列區域翻面~
題目鏈接：https://leetcode.cn/problems/reverse-string-ii/
思路：根據題目模擬就行
???考慮回圈怎么減少運算：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;
}
};
識訓摘要：理清題目意思，模擬考慮的情況要全而精簡
學習的文章鏈接：https://programmercarl.com/0541.反轉字串II.html#其他語言版本
劍指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
?????模擬程序漸漸多了起來，最好使用自定義函式，這樣模擬程序會更加清晰，
學習的文章鏈接：https://programmercarl.com/0151.翻轉字串里的單詞.html
劍指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用了很久……
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/525945.html
標籤：其他
下一篇：演算法題--替換空格