leetcode刷题 (5.31) 字符串

1. 反转字符串

344

题目：
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

思路：
双指针，区别于反转链表（字符串是数组，在内存中连续分布）

笔记：
利用Python可以同时赋值的特性，数组的swap操作可以同时赋值

s[left], s[right] = s[right], s[left]

为什么不需要设置tmp变量来保存中间值？

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

因为赋值操作是等号从右往左的顺序执行，单纯把数值s.size() - 1, 0 赋给 s[left], s[right]，而分开操作，一旦赋值s[i] = s[j]，s[i]就会被新值覆盖，所以要先保存中间变量。

C++：

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

Python：

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """ Do not return anything, modify s in-place instead. """

        left, right = 0, len(s) - 1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

2. 反转字符串II

541

题目：
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

输入：s = "abcdefg", k = 2
输出："bacdfeg"

思路：
打破固有 for 循环 k++ 思维：i 每次移动 2*k 即可

题目的两个“如果”条件，可以理解为始终反转前k个（<=），然后前进2k步，难在反转前k个（<=）的处理：
对于C++，就是看到底是反转 [i, i + k) 还是 [i, n) ，可以用min()判断
对于Python，如果切片写的边界实际没达到（比如s[0:999]），默认返回实际字符串最后一个值，所以不用再判断 “剩余字符小于k的情形”。

笔记：
注：C++ reverse()函数是左开右闭，范围是 [first,last) 内全部反转。
重点不是考察reverse()操作，所以可以用库函数

C++：

class Solution {
    
public:
    string reverseStr(string s, int k) {
    
        int n = s.size();
        for (int i = 0; i < n; i += (2 * k)) {
    
            // 1. 每隔 2k 个字符的前 k 个字符进行反转
            // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
            // 3. 剩余字符少于 k 个，则将剩余字符全部反转。—— min()取n的情况
            reverse(s.begin() + i, s.begin() + min(i + k, n));
        }
        return s;
    }
};

Python：

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        t = list(s)
        for i in range(0, len(t), 2 * k):
        	# 就算字符串不足k长，也不会报错，返回的是实际长度
            t[i: i + k] = reversed(t[i: i + k])
        return "".join(t)

3. 替换空格

剑指Offer 05

题目：
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

输入：s = "We are happy."
输出："We%20are%20happy."

思路：
看着很简单，就for循环检测一下遇到空格就换成字符就ok，但没有考虑到空格和新字符长度不一样的问题，所以不可能原地换，一定要扩空间。

用原地反向填充：先扩容size，再反向双指针填充可以最大程度减少空间复杂度。

但对于Python和JAVA，字符串都被设计成「不可变」的类型，（C++ string可变）即无法直接修改字符串的某一位字符，需要新建一个字符串实现（往新字符串里顺序填充即可）。

笔记：
注意审题：

 s.resize(sOldSize + 2 * count);

为什么不是 3 * count ? “%20” 明明占3位？因为原本空格就占了1位

C++：

class Solution {
    
public:
    string replaceSpace(string s) {
    
        int count = 0;
        int sOldSize = s.size();
        // 统计空格数量
        for (char c : s) {
    
            if (c == ' ') count++;
        }
        // 修改 s 长度
        s.resize(sOldSize + 2 * count);
        int sNewSize = s.size();
        // 倒序遍历修改
        for(int i = sNewSize - 1, j = sOldSize - 1; j < i; i--, j--) {
    
            if (s[j] != ' ')
                s[i] = s[j];
            else {
    
                s[i - 2] = '%';
                s[i - 1] = '2';
                s[i] = '0';
                i -= 2;
            }
        }
        return s;
    }
};

Python：

class Solution:
    def replaceSpace(self, s: str) -> str:
        res = []
        for c in s:
            if c == ' ': res.append("%20")
            else: res.append(c)
        return "".join(res)