題目描述
給定一個字符串，你需要反轉(zhuǎn)字符串中每個單詞的字符順序，同時仍保留空格和單詞的初始順序。
示例：
? 輸入："Let's take LeetCode contest"
? 輸出："s'teL ekat edoCteeL tsetnoc"
提示：
? 在字符串中，每個單詞由單個空格分隔，并且字符串中不會有任何額外的空格。
數(shù)據(jù)結(jié)構(gòu)
- 字符串、字符數(shù)組
算法思維
- 遍歷、逆序、雙指針
解題要點
- 如何優(yōu)化實現(xiàn)一個單詞中的字符反轉(zhuǎn)
解題思路
一. Comprehend 理解題意
- 單詞的順序不變
- 顛倒每個單詞內(nèi)部字符的順序
二. Choose 選擇數(shù)據(jù)結(jié)構(gòu)與算法
雙指針 解法
- 數(shù)據(jù)結(jié)構(gòu)：指針、字符串
- 算法思維：遍歷、逆序、雙指針
解題思路
- 聲明雙指針和緩存
- 遍歷字符串
? 如果不是：讀到了字符串末尾 或者 讀到了空格
? ? 判斷首指針是否為空
? ? ? 如果為空就賦值成當(dāng)前位置
? ? 不管首指針是否為空，尾指針都和遍歷位置對齊
? 如果：讀到了末尾，或者讀到了空格
? ? 判斷首指針是否為空
? ? ? 如果不為空，就逆序遍歷首尾指針之間的所有字符，存入緩沖區(qū)
? ? ? 每讀完一個單詞都要添加一個空格，并且將首尾指針復(fù)原 - 最終去掉緩沖區(qū)末尾的空格后，作為字符串返回
邊界問題
- 為了討論最后一個字符非空的情況，將邊界條件設(shè)為：
i <= s.length()
細節(jié)問題
- 需要非空判斷
- 遍歷完整個字符串，需要判斷當(dāng)前首尾指針中間是都有數(shù)據(jù)
如果有數(shù)據(jù)，要額外寫入一次到緩存區(qū)中，避免丟失最后一個單詞
三. Code 編碼實現(xiàn)基本解法
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.就判斷首指針是否為空，如果為空就賦值成當(dāng)前位置
if (first == -1) {
first = i;
}
//5.不管首指針是否為空，尾指針都和遍歷位置對齊
last = i;
} else if (first != -1) { //6.如果讀到了末尾，或者讀到了空格，且首指針不為空
//7.逆序遍歷首尾指針之間的所有字符，存入緩沖區(qū)
while (last >= first) {
sb.append(arr[last]);
last--;
}
//8.每讀完一個單詞都要添加一個空格，并且將首尾指針復(fù)原
sb.append(' ');
first = -1;
last = -1;
}
}
//9.最終去掉緩沖區(qū)末尾的空格后，作為字符串返回
return sb.substring(0,sb.length()-1);
}
}
執(zhí)行耗時：8 ms，擊敗了 56.64% 的Java用戶
內(nèi)存消耗：39 MB，擊敗了 64.81% 的Java用戶
時間復(fù)雜度：O(n) -- 兩次字符串的遍歷 O(n)
空間復(fù)雜度：O(n) -- 一個緩沖區(qū) O(n)，兩個指針 O(1)
四. Consider 思考更優(yōu)解
改變算法思維
- 使用遍歷的方式反轉(zhuǎn)字符效率太低
- 使用 StringBuffer 作為緩沖區(qū)存取數(shù)據(jù)，消耗時間和空間
- 題目給定了條件：“每個單詞由單個空格分隔”
因此可以使用 雙指針 + 字符數(shù)組 的方式直接 原地反轉(zhuǎn) 字符
五. Code 編碼實現(xiàn)最優(yōu)解
優(yōu)化解法：原地反轉(zhuǎn)
class solution{
//使用雙指針，原地反轉(zhuǎn)單詞
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;//指向單詞的結(jié)尾字符或者是終止索引
//截取單詞進行 單詞翻轉(zhuǎn)
for (int i = 0; i < len; i++) {
if (chars[i] == ' ') {//如果查詢到了空格，一個單詞結(jié)束
end = i - 1;
reverse(chars, start, end);
start = i + 1;//反轉(zhuǎn)單詞之后把start指向下一個單詞的起始
} else if (i == len - 1) {//如果查詢到了數(shù)組最后一個字符，一個單詞結(jié)束
reverse(chars, start, len - 1);
}
}
return new String(chars);
}
//雙指針原地翻轉(zhuǎn)方法，給定反轉(zhuǎn)的源數(shù)組，給定起始索引和終止索引
public void reverse(char[] s, int start, int end) {
while (start < end) {//如果起始索引小于終止索引，進行反轉(zhuǎn)
//交換雙指針對應(yīng)的字符
char temp = s[start];
s[start] = s[end];
s[end] = temp;
start++;
end--;
}
}
}
執(zhí)行耗時：3 ms，擊敗了 99.88% 的Java用戶
內(nèi)存消耗：39.2 MB，擊敗了 34.70% 的Java用戶
時間復(fù)雜度：O(n) -- 字符串的遍歷 O(n)
空間復(fù)雜度：O(1) -- 字符數(shù)組 O(1)，雙指針 O(1)
六. Change 變形與延伸
=== 待續(xù) ===
