LeetCode刷題day27

算法打卡第二十七天,今天你刷題了嗎

😄😄😄😄😄😄😄😄😄😄

😃😃😃😃😃😃😃😃😃😃

💓💓💓大家一起來刷題!💓💓💓

😍😍😍😍😍😍😍😍😍😍

😘😘😘😘😘😘😘😘😘😘

今日刷題重點—字元串的基本使用

​​344. 反轉字元串​​

編寫一個函數，其作用是将輸入的字元串反轉過來。輸入字元串以字元數組 s 的形式給出。

不要給另外的數組配置設定額外的空間，你必須原地修改輸入數組、使用 O(1) 的額外空間解決這一問題。

示例 1：

輸入：s = ["h","e","l","l","o"]
輸出：["o","l","l","e","h"]      

示例 2：

輸入：s = ["H","a","n","n","a","h"]
輸出：["h","a","n","n","a","H"]      

思路分析

雙指針法

使用兩個指針l,和r,一個在最左邊一個在最右邊,每次交換兩個位置的内容,直至l=r結束移動.

參考代碼

//雙指針法 
void reverseString(vector<char>& s) {
  int l = 0;
  int r = s.size()-1;
  int temp;
  while(l<r){
    temp = s[l];
    s[l] = s[r];
    s[r] = temp;
    l++;
    r++;
  } 
  
}      

​​541. 反轉字元串 II​​

給定一個字元串 s 和一個整數 k，從字元串開頭算起，每計數至 2k 個字元，就反轉這 2k 字元中的前 k 個字元。

如果剩餘字元少于 k 個，則将剩餘字元全部反轉。

如果剩餘字元小于 2k 但大于或等于 k 個，則反轉前 k 個字元，其餘字元保持原樣。

示例 1：

輸入：s = "abcdefg", k = 2
輸出："bacdfeg"      

示例 2：

輸入：s = "abcd", k = 2
輸出："bacd"      

思路分析

這個題和上題思路一樣.具體思路如下:

• 每2k個字元長度,反轉前k個的字元==>這也就決定了i每一輪的增量是2k
• 如果不夠2k但大于k則反轉前k個.
• 如果剩餘的小于k,則全部進行反轉.

參考代碼

reverseStr(string s, int k) {
  //每次i向後移動2k個機關長度
  //如果剩餘少于k,則将剩餘全部反轉
  // 如果剩餘字元小于2k但大于等于k,則反轉前k個字元
  for(int i = 0;i < s.size();i += 2*k){
    if(i+k <= s.size()){//如果剩餘字元小于2k但大于等于k,則反轉前k個字元
      reverse(s.begin()+i,s.begin()+i+k);
      continue;
    }
    reverse(s.begin()+i,s.end());//如果剩餘少于k,則将剩餘全部反轉
  } 
  return s;
  
}      

​​劍指 Offer 05. 替換空格​​

請實作一個函數，把字元串 s 中的每個空格替換成"%20"。

示例 1：

輸入：s = "We are happy."
輸出："We%20are%20happy."      

方法一:雙指針

由于C++ 的string底層維護的也是一個字元數組.我們知道數組元素的删除和插入有時候會導緻所有元素都向後移動,這樣很花費時間.所有我們可以提前統計字元串中的空格,然後為字元串重新到最終需要的空間.

處理時我們使用快慢指針,從後往前一邊将空格轉換成%20,一邊将元素放在對應的位置.最終傳回字元串即可.

算法步驟:

• 統計字元串s中的空格個數:cnt
• 為s重新配置設定更大的空間:s.size()+cnt*2
• 定義兩個指針i,j從後往前,一邊将空格轉換成%20,一邊将元素放在對應的位置
• 傳回字元串s

參考代碼1

//雙指針法 
string replaceSpace(string s) {
  int cnt = 0;//統計字元串中的空格個數
  int len1 = s.size();
  for(int i = 0;i < len1;i++){
    if(s[i]==' '){
      cnt++;
    }
  }
  s.resize(len1+cnt*2);
  //從後往前替換成 %20

  for(int i = len1-1,j = s.size()-1; i < j; i--){//i周遊老串的每一個字元 
    if(s[i]!=' '){
      s[j] = s[i];
      j--;
    }else{
      s[j] = '0';
      s[j-1] = '2';
      s[j-2] = '%';
      j-=3;
    } 
    
  }
  return s;
}      

方法二:字元串拼接

定義一個字元串變量,如果是非空格字元則直接進行拼接,如果是空格則拼接上%20. 雖然是最普通的方法,但是這個效率還蠻高的,嘿嘿

參考代碼2

string replaceSpace(string s) {
  string ans="";
  for(int i = 0;i < s.size();i++){
    if(s[i]!=' '){
      ans+=s[i];
    }else{
      ans +="%20";
    }
  }
  return ans;
}      

​​151. 翻轉字元串裡的單詞​​

給你一個字元串 s ，逐個翻轉字元串中的所有 單詞 。

單詞 是由非空格字元組成的字元串。s 中使用至少一個空格将字元串中的 單詞 分隔開。

請你傳回一個翻轉 s 中單詞順序并用單個空格相連的字元串。

說明：

輸入字元串 s 可以在前面、後面或者單詞間包含多餘的空格。

翻轉後單詞間應當僅用一個空格分隔。

翻轉後的字元串中不應包含額外的空格。

示例 1：

輸入：s = "the sky is blue"
輸出："blue is sky the"      

示例 2：

輸入：s = "  hello world  "
輸出："world hello"      

解釋：輸入字元串可以在前面或者後面包含多餘的空格，但是翻轉後的字元不能包括。

示例 3：

輸入：s = "a good   example"
輸出："example good a"      

解釋：如果兩個單詞間有多餘的空格，将翻轉後單詞間的空格減少到隻含一個。

示例 4：

輸入：s = "  Bob    Loves  Alice   "
輸出："Alice Loves Bob"      

示例 5：

輸入：s = "Alice does not even like bob"
輸出："bob like even not does Alice"      

菜雞做法

本題對字元串考察的很綜合,是一個很不錯的題目!!!

使用split()函數,定義一個新字元串,然後把字元串倒叙相加,

但是這樣的話,好像配不上中等題的标簽了,這道題核心就是去空格,倒叙,拼接,結果你直接把split()就完成了最難的工作.除非是在實在沒有其他思路時可以試一下這個方法.畢竟最核心的不要直接用庫搞定…

參考代碼1

明日補充…

方法二

我們可以嘗試一下成為大佬,提高一下題目的難度:不要使用輔助空間,空間複雜度要求為

是以解題思路:

• 移除多餘空格
• 将整個字元串反轉
• 将每個單詞反轉

舉個栗子,源字元串為："the sky is blue "

• 移除多餘空格 : “the sky is blue”
• 字元串反轉：“eulb si yks eht”
• 單詞反轉：“blue is sky the”

這樣我們就完成了翻轉字元串裡的單詞。

但是如何去除單詞間的空格呢?

下面是菜雞的做法:哎,菜雞到鳳凰,哪能一夜之間就變呢?

void removeExtraSpaces(string& s) {
    for (int i = s.size() - 1; i > 0; i--) {
        if (s[i] == s[i - 1] && s[i] == ' ') {
            s.erase(s.begin() + i);
        }
    }
    // 删除字元串最後面的空格
    if (s.size() > 0 && s[s.size() - 1] == ' ') {
        s.erase(s.begin() + s.size() - 1);
    }
    // 删除字元串最前面的空格
    if (s.size() > 0 && s[0] == ' ') {
        s.erase(s.begin());
    }
}      

但是呢,兄弟們,erase的複雜度是O(n),因為字元串的底層也是字元數組呢.而且外部還有一個for循環,是以整體時間複雜度為:

//移除備援空格,使用雙指針(快慢指針)法, 複雜度:O(n) 
void removeExtraSpaces(string &s){
  int slowIndex = 0,fastIndex = 0;//定義快慢指針
   //去掉前面的空格
   while(s.size()>0&&fastIndex < s.size()&&s[fastIndex]==' '){
    fastIndex++;
   } 
   //去掉字元串中間的備援空格
   for(;fastIndex<s.size();fastIndex++){
    if(fastIndex>1&&s[fastIndex-1]==s[fastIndex]&&s[fastIndex]==' '){//s目前:"x "我們隻需要從第三個字元判斷就可以了. 
      continue;
     }else{
      s[slowIndex++] = s[fastIndex];
     }
   } 
   //去掉末尾字元串并重置字元串大小. 
   if(slowIndex-1>0 && s[slowIndex-1]==' '){//字元串的結束下标是slowIndex-1,而且可能是空格.是以需要去重. 
    s.resize(slowIndex-1);
   } else{
    s.resize(slowIndex);//重置字元串大小.  字元串的底層是一個字元數組. 
   }
}      

參考代碼2

//字元串反轉 
void reverse(string& s,int start,int end){
  for(int i = start,j = end;i<j;i++,j--){
    swap(s[i],s[j]);
  }
}

//移除備援空格,使用雙指針(快慢指針)法, 複雜度:O(n) 
void removeExtraSpaces(string &s){
  int slowIndex = 0,fastIndex = 0;//定義快慢指針
   //去掉前面的空格
   while(s.size()>0&&fastIndex < s.size()&&s[fastIndex]==' '){
    fastIndex++;
   } 
   //去掉字元串中間的備援空格
   for(;fastIndex<s.size();fastIndex++){
    if(fastIndex>1&&s[fastIndex-1]==s[fastIndex]&&s[fastIndex]==' '){//s目前:"x "我們隻需要從第三個字元判斷就可以了. 
      continue;
     }else{
      s[slowIndex++] = s[fastIndex];
     }
   } 
   //去掉末尾字元串并重置字元串大小. 
   if(slowIndex-1>0 && s[slowIndex-1]==' '){//字元串的結束下标是slowIndex-1,而且可能是空格.是以需要去重. 
    s.resize(slowIndex-1);
   } else{
    s.resize(slowIndex);//重置字元串大小.  字元串的底層是一個字元數組. 
   }
} 

string reverseWords(string s) {
  removeExtraSpaces(s);
  reverse(s,0,s.size()-1);//反裝整個字元串
  for(int i = 0;i < s.size();i++){
    int j = i;
    //查找單詞間的空格,
    while(j<s.size()&&s[j]!=' '){
      j++;
    } //j位置是空格 
    reverse(s,i,j-1);
    i =  j;//重新指派而且i++,下一次i從j+1開始,也就是下一個單詞開始. 
  } 
  return s; 
}