344 反转字符串 Reverse String

要点

题目要求 in place 修改。使用相向双指针完成

代码

C++

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

Python

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        i, j = 0, len(s) - 1
        while i < j:
            tmp = s[i]
            s[i] = s[j]
            s[j] = tmp
            i += 1
            j -= 1

541 反转字符串II Reverse String II

要点

此题要求我们每隔 2k 长度，取前 k 个进行反转。
注意关注 python 的 str 是不可修改的类型，但 C++ 的是可以的。

代码

C++

class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += 2 * k) {
            if (i + k > s.size()) reverse(s, i, s.size());
            else reverse(s, i, i + k);
        }
        return s;
    }

    void reverse(string& s, int start, int end) { // [)
        for (int i = start, j = end - 1; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }
};

Python

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        t = list(s)
        for i in range(0, len(t), 2 * k):
            if i + k > len(t):
                self.reverse(t, i, len(t))
            else:
                self.reverse(t, i, i + k)
        return ''.join(t)
                
    def reverse(self, t: List[str], start: int, end: int) -> None:
        i = start
        j = end - 1
        while i < j:
            tmp = t[i]
            t[i] = t[j]
            t[j] = tmp 
            i += 1
            j -= 1

剑指 Offer 05. 替换空格 LCOF

要点

1. C++ 先遍历一遍数空格，根据空格数进行字符串的 resize，再从后向前使用双指针填充。
2. Python 由于字符串类型不可更改，可转换为 list 后再处理。也可以使用方便的 split 函数再 join

代码

C++

class Solution {
public:
    string replaceSpace(string s) {
        int old_length = s.size();
        int count = 0;
        for (char letter : s) {
            if (letter == ' ') count++;
        }
        s.resize(s.size() + 2 * count);
        int left = old_length - 1;
        int right = s.size() - 1;
        while (left >= 0) {
            if (s[left] == ' ') {
                s[right] = '0';
                s[right - 1] = '2';
                s[right - 2] = '%';
                right -= 2;
            } else {
                s[right] = s[left];
            }
            left--; right--;
        }
        return s;
    }
};

Python

class Solution:
    def replaceSpace(self, s: str) -> str:
        t = list(s)
        prev_len = len(t)
        count = 0

        for letter in s:
            if letter == ' ':
                count += 1

        t += [' '] * 2 * count 
        left = prev_len - 1
        right = len(t) - 1

        while left >= 0:
            if t[left] != ' ':
                t[right] = t[left]
            else:
                t[right] = '0'
                t[right - 1] = '2'
                t[right - 2] = '%'
                right -= 2
            right -= 1
            left -= 1
        return ''.join(t)

151 翻转字符串里的单词 Reverse Words in a String

要点

1. 实现一个全 string 翻转的 reverse 方法
2. 翻转两次：一次全 string，一次单词内
3. 删掉多余的空格：双指针。当快指针非空格时处理，跳过其它空格，但是当慢指针不是 0 的时候左侧都额外加入一个空格，剩下的 while 快指针不是 0 都一步一步读写， 快慢指针一起右移，直到快指针再次碰到空格。

代码

C++

class Solution {
public:
    string reverseWords(string s) {
        removeExtraSpaces(s);
        reverse(s, 0, s.size());
        int i = 0, j = 0;
        while (j <= s.size()) {
            if (s[j] == ' ' || j == s.size()) {
                reverse(s, i, j);
                i = j + 1;
            }
            j++;
        }
        return s;
    }

    void reverse(string& s, int start, int end) {
        for (int i = start, j = end - 1; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }

    void removeExtraSpaces(string& s) {
        int left = 0;
        for (int right = 0; right < s.size(); right++) {
            if (s[right] != ' ') {
                if (left != 0) s[left++] = ' ';
                while (right < s.size() && s[right] != ' ') {
                    s[left++] = s[right++];
                }
            }
        }
        s.resize(left);
    }
};

Python

class Solution:
    def reverseWords(self, s: str) -> str:
        t = s.strip(' ')
        t = t.split()

        left = 0
        right = len(t) - 1
        print(t)
        
        while left < right:
            tmp = t[left]
            t[left] = t[right]
            t[right] = tmp 
            left += 1
            right -= 1
        
        return ' '.join(t)

剑指 Offer 58 - II. 左旋转字符串 LCOF

要点

1. 类似于矩阵转置的思路，左旋转：前 n 个翻转，后 len - n 个翻转，最后整体翻转。注意整体翻转为最后一步
2. python 可以用切片

代码

C++

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;
    }
};

Python

class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        return s[n: ] + s[: n]