1.反轉字符串（344-易）
題目描述：將輸入的字符串反轉過來。輸入字符串以字符數(shù)組 char[] 的形式給出。必須原地修改數(shù)組！即額外空間復雜度O(1)。
示例：
輸入：["h","e","l","l","o"]
輸出：["o","l","l","e","h"]
思路：雙指針遍歷字符數(shù)組，依次交換左右指針指向元素。
代碼：
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 和一個整數(shù) k，你需要對從字符串開頭算起的每隔 2k 個字符的前 k 個字符進行反轉。
- 如果剩余字符少于 k 個，則將剩余字符全部反轉。
- 如果剩余字符小于 2k 但大于或等于 k 個，則反轉前 k 個字符，其余字符保持原樣。
示例：
輸入: s = "abcdefg", k = 2
輸出: "bacdfeg"
思路：字符塊為2k（遍歷步長為2k）；反轉要求：我們要反轉前k個，不足k全部反轉，即我們需要確定反轉區(qū)域的左右索引。
注意：左邊界為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) {
// 確定待反轉區(qū)域的左右索引(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)實現(xiàn)。
- 無空格字符構成一個 單詞 。
- 輸入字符串可以在前面或者后面包含多余的空格，但是反轉后的字符不能包括。
- 如果兩個單詞間有多余的空格，將反轉后單詞間的空格減少到只含一個。
示例：
輸入："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);
}
