題目描述
給定一個字符串抱慌，你需要反轉字符串中每個單詞的字符順序歹鱼，同時仍保留空格和單詞的初始順序泣栈。
示例：
? 輸入："Let's take LeetCode contest"
? 輸出："s'teL ekat edoCteeL tsetnoc"
提示：
? 在字符串中卜高，每個單詞由單個空格分隔弥姻，并且字符串中不會有任何額外的空格。
數據結構
- 字符串掺涛、字符數組
算法思維
- 遍歷庭敦、逆序、雙指針
解題要點
- 如何優(yōu)化實現一個單詞中的字符反轉
解題思路
一. Comprehend 理解題意
- 單詞的順序不變
- 顛倒每個單詞內部字符的順序
二. Choose 選擇數據結構與算法
雙指針 解法
- 數據結構：指針薪缆、字符串
- 算法思維：遍歷秧廉、逆序伞广、雙指針
解題思路
- 聲明雙指針和緩存
- 遍歷字符串
? 如果不是：讀到了字符串末尾 或者 讀到了空格
? ? 判斷首指針是否為空
? ? ? 如果為空就賦值成當前位置
? ? 不管首指針是否為空，尾指針都和遍歷位置對齊
? 如果：讀到了末尾疼电，或者讀到了空格
? ? 判斷首指針是否為空
? ? ? 如果不為空嚼锄，就逆序遍歷首尾指針之間的所有字符，存入緩沖區(qū)
? ? ? 每讀完一個單詞都要添加一個空格蔽豺，并且將首尾指針復原 - 最終去掉緩沖區(qū)末尾的空格后区丑，作為字符串返回
邊界問題
- 為了討論最后一個字符非空的情況，將邊界條件設為：
i <= s.length()
細節(jié)問題
- 需要非空判斷
- 遍歷完整個字符串修陡，需要判斷當前首尾指針中間是都有數據
如果有數據沧侥，要額外寫入一次到緩存區(qū)中，避免丟失最后一個單詞
三. Code 編碼實現基本解法
class Solution {
public String reverseWords(String s) {
int len = s.length();
//0.非空判斷
if (len == 0) return "";
//1.聲明雙指針和緩存
int first = -1, last = -1;
StringBuffer sb = new StringBuffer();
char[] arr = s.toCharArray();
//2.遍歷字符串
for (int i = 0; i <= len; i++) {
//3.如果不是讀到了字符串末尾魄鸦，或者讀到了空格
if (i != len && arr[i] != ' ') {
//4.就判斷首指針是否為空宴杀，如果為空就賦值成當前位置
if (first == -1) {
first = i;
}
//5.不管首指針是否為空，尾指針都和遍歷位置對齊
last = i;
} else if (first != -1) { //6.如果讀到了末尾拾因，或者讀到了空格旺罢，且首指針不為空
//7.逆序遍歷首尾指針之間的所有字符，存入緩沖區(qū)
while (last >= first) {
sb.append(arr[last]);
last--;
}
//8.每讀完一個單詞都要添加一個空格绢记，并且將首尾指針復原
sb.append(' ');
first = -1;
last = -1;
}
}
//9.最終去掉緩沖區(qū)末尾的空格后主经，作為字符串返回
return sb.substring(0,sb.length()-1);
}
}
執(zhí)行耗時：8 ms，擊敗了 56.64% 的Java用戶
內存消耗：39 MB庭惜，擊敗了 64.81% 的Java用戶
時間復雜度：O(n) -- 兩次字符串的遍歷 O(n)
空間復雜度：O(n) -- 一個緩沖區(qū) O(n)罩驻，兩個指針 O(1)
四. Consider 思考更優(yōu)解
改變算法思維
- 使用遍歷的方式反轉字符效率太低
- 使用 StringBuffer 作為緩沖區(qū)存取數據，消耗時間和空間
- 題目給定了條件：“每個單詞由單個空格分隔”
因此可以使用 雙指針 + 字符數組 的方式直接 原地反轉 字符
五. Code 編碼實現最優(yōu)解
優(yōu)化解法：原地反轉
class solution{
//使用雙指針护赊，原地反轉單詞
public String reverseWords(String s) {
if (s == null || s.length() == 0) {//邊界檢查
return s;
}
char[] chars = s.toCharArray();
int len = chars.length;
//指向單詞的初始字符
int start = 0;
int end = 0;//指向單詞的結尾字符或者是終止索引
//截取單詞進行 單詞翻轉
for (int i = 0; i < len; i++) {
if (chars[i] == ' ') {//如果查詢到了空格惠遏，一個單詞結束
end = i - 1;
reverse(chars, start, end);
start = i + 1;//反轉單詞之后把start指向下一個單詞的起始
} else if (i == len - 1) {//如果查詢到了數組最后一個字符，一個單詞結束
reverse(chars, start, len - 1);
}
}
return new String(chars);
}
//雙指針原地翻轉方法骏啰，給定反轉的源數組节吮，給定起始索引和終止索引
public void reverse(char[] s, int start, int end) {
while (start < end) {//如果起始索引小于終止索引计维，進行反轉
//交換雙指針對應的字符
char temp = s[start];
s[start] = s[end];
s[end] = temp;
start++;
end--;
}
}
}
執(zhí)行耗時：3 ms财异，擊敗了 99.88% 的Java用戶
內存消耗：39.2 MB璃谨，擊敗了 34.70% 的Java用戶
時間復雜度：O(n) -- 字符串的遍歷 O(n)
空間復雜度：O(1) -- 字符數組 O(1)婉称，雙指針 O(1)
六. Change 變形與延伸
=== 待續(xù) ===
