刷题笔记day8

344.反转字符串

文章讲解：代码随想录
是否自己做出来通过全部用例：是

遇到的困难/犯的错误

这题很简单，双指针法。

自己写的代码

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

看了题解后的收获

数组存储在连续空间，反转比链表简单。

541.反转字符串II

文章讲解：代码随想录
是否自己做出来通过全部用例：否

遇到的困难/犯的错误

审题不清，题目要求是每2k个字符，反转其中的前k个字符。

自己写的代码

class Solution {
public:
    string reverseStr(string s, int k) {
        int left, right;
        string s1 = s;
        for (int i = 0; i <= s1.length() / (2 * k); ++i) {
            if (s1.length() - 2 * k * i < k) {
                left = 2 * k * i;
                right = s1.length() - 1;
            }
            else {
                left = 2 * k * i;
                right = 2 * k * i + k - 1; 
            }
            while (right > left) {
                char temp = s1[left];
                s1[left] = s1[right];
                s1[right] = temp;
                --right;
                ++left;
            }
        }
        return s1;
    }
};

看了题解后的收获

i可以递增2k，特殊情况：if (i + k < s1.length())。

题剑指Offer 05.替换空格

文章讲解：代码随想录
是否自己做出来通过全部用例：否

遇到的困难/犯的错误

知道用双指针法，但是for循环没捋清楚逻辑。

自己写的代码

看了题解后写的代码：

class Solution {
public:
    string replaceSpace(string s) {
        int counts = 0;
        auto oldsize = s.size();
        for (auto c : s) {
            if (c == ' ') {
                ++counts;
            }
        }
        s.resize(s.size() + counts * 2);
        auto newsize = s.size();
        for (int i = newsize - 1, j = oldsize - 1; i > j; --i, --j) {
            if (s[j] != ' ') {
                s[i] = s[j];
            }
            else {
                s[i] = '0';
                s[i-1] = '2';
                s[i-2] = '%';
                i -= 2;
            }
        }
        return s;
    }
};

看了题解后的收获

注意双指针法中的逻辑，for循环捋不清也可以把两个指针先在外面定义好，再while (front < behind)。
代码如下：

class Solution {
public:
    string replaceSpace(string s) {
        int counts = 0;
        auto oldsize = s.size();
        for (auto c : s) {
            if (c == ' ') {
                ++counts;
            }
        }
        s.resize(s.size() + counts * 2);
        auto newsize = s.size();
        int front = oldsize - 1;
        int behind = newsize - 1;
        while (front < behind) {
            if (s[front] != ' ') {
                s[behind] = s[front];
            }
            else {
                s[behind] = '0';
                s[behind-1] = '2';
                s[behind-2] = '%';
                behind -= 2;
            }
            --front;
            --behind;
        }
        return s;
    }
};

151.翻转字符串里的单词

文章讲解：代码随想录
是否自己做出来通过全部用例：是

遇到的困难/犯的错误

思路是把每个单词是放在一个vector的容器中，然后倒序再提出。

自己写的代码

class Solution {
public:
    string reverseWords(string s) {
        vector<string> vec;
        string temp;
        char last = ' ';
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] != ' ') {
                temp += s[i];
                if (i == s.size() - 1) {
                    vec.push_back(temp);  
                }
            }
            else {
                if (last != ' ') {
                    vec.push_back(temp);
                    temp.clear();
                }
            }
            last = s[i];
        }
        temp.clear();
        reverse(vec.begin(), vec.end());
        for (auto iter = vec.begin(); iter != vec.end(); ++iter) {
            temp += *iter;
            if (iter == vec.end() - 1) {
                continue;
            } 
            temp += " ";           
        }
        return temp;
    }
};

看了题解后的收获

快慢指针法对多余的空格进行处理后，进行整体的reverse和单词的reverse。

剑指Offer58-II.左旋转字符串

文章讲解：代码随想录
是否自己做出来通过全部用例：是

遇到的困难/犯的错误

额外创造了一个字符串，用resize实现。

自己写的代码

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        auto oldsize = s.size();
        s.resize(s.size()+n);
        for (int i = 0; i<n;++i) {
            s[oldsize+i]=s[i];
        }
        string result(s, n);
        return result;
    }
};

看了题解后的收获

可以不额外创造空间，用两次reverse实现。