反轉字符串

leetcode.344

• 鏈接https://leetcode.cn/problems/...
• 解題方法：雙指針
  l，r指針分別放在字符串的首尾兩端，每次交換兩個字符
  每交換一次指針向中間移動一位

• leetcode解題代碼

  class Solution {
  public:
    void reverseString(vector<char>& s) {
        int l = 0, r = s.size() - 1;
        while (l < r){
            swap(s[l], s[r]);
            l ++, r --;
        }
    }
  };

leetcode.541

• 鏈接https://leetcode.cn/problems/...
• 解題方法：雙指針
  定義維護的區間[l, r]，每次維護2k個數

• leetcode解題代碼

  class Solution {
  public:
    string reverseStr(string s, int k) {
        int n = s.size();
        for (int i = 0; i < n - 1; i += k * 2){
            int l = i, r = min(i + k, n);
            reverse(s.begin() + l, s.begin() + r);
        }
        return s;
    }
  };

反轉字符串中的單詞

• 題目類型：給一個字符串組成的句子(帶空格或標點)，然後對句中單個字符串進行一系列處理
• 這類題目可以分為兩類，一類是有前置或者後置空格的，另一類是沒有前置和後置空格的

leetcode.58

• 鏈接https://leetcode.cn/problems/...
• 解題方法：創建一個臨時字符串（用來存每一個單詞），和一個答案數組
  遍歷原字符串，如果遍歷到空格，判斷臨時字符串是否為空
  如果臨時字符串非空則説明已經遍歷完一個單詞，將其加入答案數組中並清空臨時字符串
  如果遍歷到的不是空格，將其加入臨時字符串中

• leetcode解題代碼

  class Solution {
  public:
    int lengthOfLastWord(string s) {
        s += " ";// 在字符串末尾加上一個空格防止遺漏最後一個單詞
        string temp = "";
        vector<string> res;
        for (auto c: s){
            if (c == ' '){
                if (!temp.empty()){
                    res.push_back(temp);
                    temp.clear();
                }
            }
            else temp += c;
        }
        if (res.empty()) return 0;
        return res.back().size();
    }
  };

leetcode.557

• 鏈接https://leetcode.cn/problems/...
• 解題方法：與上一題類似

• leetcode解題代碼

  class Solution {
  public:
    string reverseWords(string s) {
        s += " ";
        string temp = "";
        vector<string> res;
        for (auto c: s){
            if (c == ' '){
                if (!temp.empty()){
                    res.push_back(temp);
                    temp.clear();
                }
            }
            else temp += c;
        }
        s.clear();
        for (auto c: res){
            reverse(c.begin(), c.end());
            s += c + ' ';
        }
        s.pop_back();// 一開始加了一個空格記得刪掉
        return s;
    }
  };

劍指offer.58(leetcode.151)

• 鏈接https://leetcode.cn/problems/...
  https://leetcode.cn/problems/...
• 解題方法：與上一題類似

• leetcode解題代碼

  class Solution {
  public:
    string reverseWords(string s) {
        s += " ";
        string temp;
        vector<string> res;
        for (auto c: s){
            if (c == ' '){
                if (!temp.empty()){
                    res.push_back(temp);
                    temp.clear();
                }
            }
            else temp += c;
        }
        s.clear();
        reverse(res.begin(), res.end());
        for (auto c: res){
            s += c + ' ';
        }
        s.pop_back();
        return s;
    }
  };

• ACM模式調試

輸入字符串s

the sky is blue

輸出

blue is sky the

調試代碼

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

int main(){
    string s;
    getline(cin, s);
    
    s += ' ';
    string temp;
    vector<string> res;
    for (auto c: s){
        if (c == ' '){
            if (!temp.empty()){
                res.push_back(temp);
                temp.clear();
            }
        }
        else temp += c;
    }
    
    s.clear();
    reverse(res.begin(), res.end());
    for (auto c: res){
        s += c + ' ';
    }
    s.pop_back();
    
    cout << s << endl;
    return 0;
}

字符串中的其他操作（替換空格，旋轉字符串等）

劍指offer.05

• 鏈接https://leetcode.cn/problems/...
• 解題方法：創新新字符串，遍歷原字符串找到空格替換即可

• leetcode解題代碼

  class Solution {
  public:
    string replaceSpace(string s) {
        string res;
        for (auto c: s){
            if (c == ' '){
                res += "%20";
            }
            else res += c;
        }
        return res;
    }
  };

leetcode.796

• 鏈接https://leetcode.cn/problems/...
• 解題方法：如果字符串goal能通過字符串s旋轉得到
  那麼字符串goal一定是字符串s+s的字串，時間複雜度為O(n^2)
  （本題可以用KMP和字符串哈希求解，時間複雜度可以降到O(n)）

• leetcode解題代碼

  class Solution {
  public:
    bool rotateString(string s, string goal) {
        if (s.size() != goal.size()) return false;
        s += s;
        return s.find(goal) != std::string::npos;
    }
  };

劍指offer.58

• 鏈接https://leetcode.cn/problems/...
• 解題方法：整體旋轉
  分別旋轉前半部分和後半部分

• leetcode解題代碼

  class Solution {
  public:
    string reverseLeftWords(string s, int n) {
        reverse(s.begin(), s.end());
        reverse(s.begin(), s.end() - n);
        reverse(s.end() - n, s.end());
        return s;
    }
  };

  解題參考：https://www.acwing.com/
  刷題順序參考：https://www.programmercarl.com/