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