1.反转字符串（344-易）
题目描述：将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。必须原地修改数组！即额外空间复杂度O(1)。
示例：
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]
思路：双指针遍历字符数组，依次交换左右指针指向元素。
代码：
public void reverseString(char[] s) {
int l = 0, r = s.length - 1;
while (l < r) {
char tmp = s[l];
s[l++] = s[r];
s[r--] = tmp;
}
}
2.反转字符串II（541-易）
题目描述：给定一个字符串 s 和一个整数 k，你需要对从字符串开头算起的每隔 2k 个字符的前 k 个字符进行反转。
- 如果剩余字符少于 k 个，则将剩余字符全部反转。
- 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
示例：
输入: s = "abcdefg", k = 2
输出: "bacdfeg"
思路：字符块为2k（遍历步长为2k）；反转要求：我们要反转前k个，不足k全部反转，即我们需要确定反转区域的左右索引。
注意：左边界为i，右边界为i + k - 1和ch.length - 1的最大值（满足前k个反转前k个，否则反转剩余的字符）
代码：
public String reverseStr(String s, int k) {
char[] cs = s.toCharArray();
for (int i = 0; i < cs.length; i += 2 * k) {
// 确定待反转区域的左右索引(l~r)
int l = i, r = Math.min(i + k - 1, cs.length - 1);
while (l < r) {
char tmp = cs[l];
cs[l++] = cs[r];
cs[r--] = tmp;
}
}
return String.valueOf(cs);
}
3.反转字符串中的单词（151-中）
题目描述：给定一个字符串，逐个翻转字符串中的每个单词。要求：使用额外空间复杂度O(1)实现。
- 无空格字符构成一个 单词 。
- 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
- 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
示例：
输入："the sky is blue"
输出："blue is sky the"
输入：" hello world! "
输出："world! hello"
解释：输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
输入："a good example"
输出："example good a"
解释：如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
思路：双指针：字符串从后向前遍历（逆序遍历），记录每个单词的起始和结束位置，先拼接单词，再拼接结果。
注意：过滤空格，这里i>0，并且需要特判是否遍历完成！
代码：
class Solution {
public String reverseWords(String s) {
char[] cs = s.toCharArray();
StringBuilder ans = new StringBuilder();
for (int i = cs.length - 1; i >= 0; i--) {
StringBuilder word = new StringBuilder();
// 1.过滤空格
while (i > 0 && cs[i] == 32) {
i--;
}
if (i == 0 && cs[i] == 32) break;
// 2.每个单词的起止位置
int end = i;
while (i >= 0 && cs[i] != 32) {
i--;
}
int start = i + 1;
// 3.拼接单词
while (start <= end) {
word.append(cs[start++]);
}
word.append(" ");
// 4.拼接结果
ans.append(word);
}
return ans.toString().substring(0, ans.length() - 1);
}
}
4.反转字符串中的单词III（557-易）
题目描述：给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。单词由单个空格分隔。
示例：
输入："Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"
思路：使用栈比较简单，字符入栈，遇到空格，出栈进行拼接。最后不要忘记出栈最后一个单词（题目没有额外空格），直接看代码。
另外可以使用原地解，即使用双指针（推荐）：
- 基于交换reverse：当遇到空格或者结尾时，反转字符串（效率高）。
- 基于拼接StringBuilder：找到起止索引，反向拼接。
代码：
// 使用辅助栈
public String reverseWords(String s) {
if (s == null || s.length() == 0) {
return "";
}
Deque<Character> stack = new LinkedList<>();
StringBuilder sb = new StringBuilder();
for (char c: s.toCharArray()) {
if (c != ' ') {
stack.push(c);
} else if (c == ' ') {
while (!stack.isEmpty()) {
sb.append(stack.pop());
}
sb.append(' ');
}
}
while (!stack.isEmpty()) {
sb.append(stack.pop());
}
return sb.toString();
}
// 双指针
public String reverseWords(String s) {
char[] chs = s.toCharArray();
int start = 0;
for (int i = 0; i <= chs.length; i++) {
if (i == chs.length || chs[i] == ' ') {
reverse(chs, start, i - 1);
start = i + 1;
}
}
return new String(chs);
}
public void reverse(char[] chs, int i, int j) {
char tmp;
while (i < j) {
tmp = chs[i];
chs[i++] = chs[j];
chs[j--] = tmp;
}
}
// 双指针（StringBuilder拼接）
public String reverseWords(String s) {
char[] cs = s.toCharArray();
StringBuilder ans = new StringBuilder();
for (int i = 0; i < cs.length; i++) {
int start = i;
while (i < cs.length && cs[i] != 32) {
i++;
}
int end = i - 1;
while (start <= end) {
ans.append(cs[end--]);
}
ans.append(' ');
}
return ans.toString().substring(0, ans.length() - 1);
}
