【演算法訓練營day8】LeetCode344. 反轉字元串 LeetCode541. 反轉字元串II 劍指Offer05. 替換空格 LeetCode151. 翻轉字元串里的單詞 劍指Offer58-II. 左旋轉字元串

【演算法訓練營day8】LeetCode344. 反轉字元串 LeetCode541. 反轉字元串II 劍指Offer05. 替換空格 LeetCode151. 翻轉字元串里的單詞 劍指Offer58-II. 左旋轉字元串

LeetCode344. 反轉字元串

題目鏈接：344. 反轉字元串

初次嘗試

雙指針法，比較簡單的一道題，熟悉一下字元串的操作。

class Solution {
public:
    void reverseString(vector<char>& s) {
        int left = 0, right = s.size() - 1;

        while (left < right) {
            char temp;
            temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }

        return;
    }
};

看完程式碼隨想錄後的想法

思路一樣，可以使用swap()函數代替手動交換。

LeetCode541. 反轉字元串II

題目鏈接：541. 反轉字元串II

初次嘗試

自己寫的好複雜還棧溢出了，程式碼能力還是有待提高。

看完程式碼隨想錄後的想法

真的是寫程式碼的思路不夠清晰，其實邏輯很簡單的一道題，自己卻寫的這麼費勁，說明程式碼能力還是不太行，只能多練習了。

學到了一個思路：

當需要固定規律一段一段去處理字元串的時候，要想想在在for循環的表達式上做做文章。

學到了兩個語法知識：

  1. end()返回的迭代器指向的是最後一個元素的後一個位置。
  2. reverse()的輸入是左閉右開的。
class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += 2 * k) {
            if (s.size() - i < k) {
                reverse(s.begin() + i, s.end());
            }
            else {
                reverse(s.begin() + i, s.begin() + i + k);
            }
        }
        
        return s;
    }
};

劍指Offer05. 替換空格

題目鏈接：劍指Offer05. 替換空格

初次嘗試

這種典型題就是用來學解題思路的，直接看題解。

看完程式碼隨想錄後的想法

學到了一個思路：

很多數組填充類的問題，都可以先預先給數組擴容帶填充後的大小，然後在從後向前進行操作。

學到了一個語法知識：

  1. resize()函數的用法。
class Solution {
public:
    string replaceSpace(string s) {
        int count = 0;
        int oldSize = s.size();

        for (int i = 0; i < s.size(); i++) {
            if (s[i] == ' ') count++;
        }

        s.resize(s.size() + count * 2);
        int newSize = s.size();

        for (int i = oldSize - 1, j = newSize - 1; i < j; i--, j--) {
            if(s[i] != ' ') {
                s[j] = s[i];
            }
            else {
                s[j] = '0';
                s[j - 1] = '2';
                s[j - 2] = '%';
                j -= 2;
            }
        }

        return s;
    }
};

LeetCode151. 翻轉字元串里的單詞

題目鏈接：151. 翻轉字元串里的單詞

初次嘗試

思路一摸一樣，但是真的是一寫就廢，永遠的棧溢出！！！！！！！QAQ

看完程式碼隨想錄後的想法

細節，細節，還是tm的細節！！！！！！！真的是太容易出bug了，心累了！！！！！！！

class Solution {
public:
    void reverse(string& s, int start, int end){ //翻轉，區間寫法：左閉又閉 []
        for (int i = start, j = end; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }

    void removeExtraSpaces(string& s) {//去除所有空格並在相鄰單詞之間添加空格, 快慢指針。
        int slow = 0;   //整體思想參考//programmercarl.com/0027.移除元素.html
        for (int i = 0; i < s.size(); ++i) { //
            if (s[i] != ' ') { //遇到非空格就處理，即刪除所有空格。
                if (slow != 0) s[slow++] = ' '; //手動控制空格，給單詞之間添加空格。slow != 0說明不是第一個單詞，需要在單詞前添加空格。
                while (i < s.size() && s[i] != ' ') { //補上該單詞，遇到空格說明單詞結束。
                    s[slow++] = s[i++];
                }
            }
        }
        s.resize(slow); //slow的大小即為去除多餘空格後的大小。
    }

    string reverseWords(string s) {
        removeExtraSpaces(s); //去除多餘空格，保證單詞之間之只有一個空格，且字元串首尾沒空格。
        reverse(s, 0, s.size() - 1);
        int start = 0; //removeExtraSpaces後保證第一個單詞的開始下標一定是0。
        for (int i = 0; i <= s.size(); ++i) {
            if (i == s.size() || s[i] == ' ') { //到達空格或者串尾，說明一個單詞結束。進行翻轉。
                reverse(s, start, i - 1); //翻轉，注意是左閉右閉 []的翻轉。
                start = i + 1; //更新下一個單詞的開始下標start
            }
        }
        return s;
    }
};

劍指Offer58-II. 左旋轉字元串

題目鏈接：劍指Offer58-II. 左旋轉字元串

初次嘗試

今日耐心已經耗盡，被第四題破防了，直接看題解。

看完程式碼隨想錄後的想法

和第四題有異曲同工之妙，可以把n前後想像成兩個不用空格連接的單詞，本質上和第四題解法一樣。

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

VirMach 便宜 VPS