代码随想录-DAY⑦-字符串——leetcode 344 | 541 | 151

344

思路

没啥好说的，
双指针头尾交换，
相遇结束。

时间复杂度：O(n)
空间复杂度：O(1)

代码

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

541

思路

下标 i 一次跳过2k个节点，
反转每个下标从 2k 的倍数开始的，长度为 k 的子串，
若该子串长度不足 k，则反转整个子串。

时间复杂度：O(n)
空间复杂度：O(1)

代码

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

151

思路

时间复杂度：O(n)
空间复杂度：O(1)

代码

在这里插入代码片