代码随想录算法训练营第8天 | 344.反转字符串、541. 反转字符串II、剑指Offer 05.替换空格、151.翻转字符串里的单词、剑指Offer58-II.左旋转字符串

发布于 2022-11-23  100 次阅读


344. 反转字符串 - 力扣(LeetCode)

思路:双指针直接秒杀,在两个指针相遇前不停交换两个指针所指的值就可以了

我的AC代码

//时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    void reverseString(vector<char>& s) {
        int nsize = s.size();
        int left = 0;
        int right = nsize - 1;
        while(left < right) {
            char tmp = s[left];
            s[left] = s[right];
            s[right] = tmp;
            right--;
            ++left;
        }
    }
};

标准答案

//时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    void reverseString(vector<char>& s) {
        for (int i = 0, j = s.size() - 1; i < s.size()/2; i++, j--) {
            swap(s[i],s[j]);
        }
    }
};

插播一下swap互相交换两个值的写法

写法1

int tmp = s[i];
s[i] = s[j];
s[j] = tmp;

写法2(位运算)

s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];

541. 反转字符串 II - 力扣(LeetCode)

思路:按照题目描述的一步一步来,当走2k的时候翻转前k个。有几点要注意,比如刚进入循环的时候就要判断目前字符串的长度是否足2k,如果不足2k,是否又足k,还有就是每次翻转完成也要判断一次

标准答案写得太智慧了,像这种题目确实应该多考虑考虑循环前进的步数

我的AC代码

//时间复杂度O(n2),空间复杂度O(1)
class Solution {
public:
    string myswap(int left, int right, string s) {
        while(left < right) {
            swap(s[left], s[right]);
            left++;
            right--;
        }
        return s;
    }
    string reverseStr(string s, int k) {
        int scnt = s.size();
        int cnt = 0;
        int start = 0;
        for(int i = 0;i < scnt; ++i) {
            ++cnt;
            if(scnt - start < 2 * k && scnt - start >= k) {
                    s = myswap(start, start + k - 1, s);
                    break;
                }
                else if(scnt - start < k) {
                    s = myswap(start, scnt - 1, s);
                    break;
            }
            if(cnt == 2*k) {
                s = myswap(start, start + k - 1, s);
                start = start + 2 * k;
                cnt = 0;
                if(scnt - start < 2 * k && scnt - start >= k) {
                    s = myswap(start, start + k - 1, s);
                    break;
                }
                else if(scnt - start < k) {
                    s = myswap(start, scnt - 1, s);
                    break;
                }
            }
        }
        return s;
    }
};

标准答案

//时间复杂度O(n2),空间复杂度O(1)
class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += (2 * k)) {
            // 1. 每隔 2k 个字符的前 k 个字符进行反转
            // 2. 剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符
            if (i + k <= s.size()) {
                reverse(s.begin() + i, s.begin() + i + k );
            } else {
                // 3. 剩余字符少于 k 个,则将剩余字符全部反转。
                reverse(s.begin() + i, s.end());
            }
        }
        return s;
    }
};

剑指 Offer 05. 替换空格 - 力扣(LeetCode)

思路:新建一个string用来保存结果,遍历原来的字符串,遇到空格就加上%20,其他普通字符正常加就行

建议使用标准答案的双指针法,时间复杂度和空间复杂度都降低到了极致

我的AC代码

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    string replaceSpace(string s) {
        int scnt = s.size();
        string a = "";
        for(int i = 0;i < scnt; ++i) {
            if(isspace(s[i])) {
                a += "%20";
            }
            else {
                a += s[i];
            }
        }
        return a;
    }
};

标准答案

//时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    string replaceSpace(string s) {
        int count = 0; // 统计空格的个数
        int sOldSize = s.size();
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == ' ') {
                count++;
            }
        }
        // 扩充字符串s的大小,也就是每个空格替换成"%20"之后的大小
        s.resize(s.size() + count * 2);
        int sNewSize = s.size();
        // 从后先前将空格替换为"%20"
        for (int i = sNewSize - 1, j = sOldSize - 1; j < i; i--, j--) {
            if (s[j] != ' ') {
                s[i] = s[j];
            } else {
                s[i] = '0';
                s[i - 1] = '2';
                s[i - 2] = '%';
                i -= 2;
            }
        }
        return s;
    }
};

151. 反转字符串中的单词 - 力扣(LeetCode)

思路:先将字符串全部翻转,在过程中去掉多余的空格,然后再一个一个把单词翻转回来就行了

建议使用标准答案,空间复杂度为O(1)

我的AC代码

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    string reverseWords(string s) {
        string a = "";
        int flag = 0;
        int scnt = s.size();
        for (int i = scnt - 1; i >= 0; --i) {
            if(s[i] == ' ') {
                if(flag == 1) {
                    a += ' ';
                    flag = 0;
                }
            }
            else {
                flag = 1;
                a += s[i];
            }
        }
        if(s[0] == ' ') {
            a.resize(a.size() - 1);// 去掉字符串前部的空格
        }
        int left = 0;
        int acnt = a.size();
        for(int i = 0;i < acnt; ++i) {
            if(a[i] == ' ' || i == acnt - 1) {
                int cnt = i;
                if(i == acnt -1) {
                    cnt++;
                }
                reverse(a.begin() + left, a.begin() + cnt);
                left = i + 1;
            }
        }
        return a;
    }
};

复刻标准答案

class Solution {
public:
    string reverseWords(string s) {
        int scnt = s.size();
        int slow = 0;
        for(int i = 0; i < scnt; ++i) {
            if(s[i] != ' ') {
                if(slow != 0) {
                    s[slow++] = s[i - 1];
                }
                while(i < scnt && s[i] != ' ') {
                    s[slow++] = s[i++];
                }
            }
        }
        s.resize(slow);
        reverse(s.begin(), s.begin() + slow);
        int start = 0;
        for(int i = 0; i < slow; ++i) {
            if(i == slow - 1) {
                reverse(s.begin() + start, s.begin() + slow);
                break;
            }
            if(s[i] == ' ') {
                reverse(s.begin() + start, s.begin() + i);
                start = i + 1;
            }
        }

        return s;
    }
};

标准答案

//时间复杂度O(n),空间复杂度O(1)
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;   //整体思想参考https://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;
    }
};

剑指 Offer 58 - II. 左旋转字符串 - 力扣(LeetCode)

思路:用额外空间就秒杀了,不用额外空间的步骤是:

  1. 反转区间为前n的子串
  2. 反转区间为n到末尾的子串
  3. 反转整个字符串

还是建议用标准答案的写法,空间复杂度为O(1)

我的AC代码

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    string reverseLeftWords(string s, int n) {
        int scnt = s.size();
        n = n % scnt;
        if(n == 0) {
            return s;
        }
        string ans = "";
        for(int i = n; i < scnt; ++i) {
            ans += s[i];
        }
        for(int i = 0; i < n; ++i) {
            ans += s[i];
        }
        return ans;
    }
};

复刻标准答案

复刻完一遍标准答案,才发现居然是有s.end()的,心碎了

之前一直都是用s.bigin() + 字符串长度来找到最后一位的

而且我发现直接开一个新数组居然比疯狂reverse快,虽然leetCode的记时不是很可靠

//时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    string reverseLeftWords(string s, int n) {
        int scnt = s.size();
        reverse(s.begin(), s.begin() + n);
        reverse(s.begin() + n, s.begin() + scnt);
        reverse(s.begin(), s.begin() + scnt);
        return s;
    }
};

标准答案

//时间复杂度O(n),空间复杂度O(1)
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;
    }
};


心有猛虎,细嗅蔷薇