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& 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)
