一、題目描述
給你一個字符串?s?，請你反轉字符串中?單詞?的順序。
單詞?是由非空格字符組成的字符串。s?中使用至少一個空格將字符串中的?單詞?分隔開。
返回?單詞?順序顛倒且?單詞?之間用單個空格連接的結果字符串。
注意：輸入字符串?s中可能會存在前導空格、尾隨空格或者單詞間的多個空格。返回的結果字符串中，單詞間應當僅用單個空格分隔，且不包含任何額外的空格。
示例 1：
輸入：s = "the sky is blue" 輸出："blue is sky the"
示例 2：
輸入：s = " ?hello world ?" 輸出："world hello" 解釋：反轉后的字符串中不能存在前導空格和尾隨空格。
示例 3：
輸入：s = "a good ? example" 輸出："example good a" 解釋：如果兩個單詞間有多余的空格，反轉后的字符串需要將單詞間的空格減少到僅有一個。
提示：
1 <= s.length <= 10^4s?包含英文大小寫字母、數字和空格?' 's?中?至少存在一個?單詞
二、解題思路
- 首先，我們需要去除字符串s的前導空格和尾隨空格，同時將字符串中間多余的空格縮減為一個空格。
- 然后，我們將整個字符串反轉。
- 接下來，我們需要遍歷反轉后的字符串，將每個單詞反轉回原來的順序。
三、具體代碼
class Solution {public String reverseWords(String s) {// 去除前導和尾隨空格，并將中間多余空格縮減為一個空格StringBuilder sb = trimSpaces(s);// 反轉整個字符串reverse(sb, 0, sb.length() - 1);// 反轉每個單詞reverseEachWord(sb);return sb.toString();}private StringBuilder trimSpaces(String s) {int left = 0, right = s.length() - 1;// 去除前導空格while (left <= right && s.charAt(left) == ' ') left++;// 去除尾隨空格while (left <= right && s.charAt(right) == ' ') right--;// 將中間多余空格縮減為一個空格StringBuilder sb = new StringBuilder();while (left <= right) {char c = s.charAt(left);if (c != ' ') {sb.append(c);} else if (sb.charAt(sb.length() - 1) != ' ') {sb.append(c);}left++;}return sb;}private void reverse(StringBuilder sb, int start, int end) {while (start < end) {char temp = sb.charAt(start);sb.setCharAt(start, sb.charAt(end));sb.setCharAt(end, temp);start++;end--;}}private void reverseEachWord(StringBuilder sb) {int n = sb.length();int start = 0, end = 0;while (start < n) {// 循環至單詞的末尾while (end < n && sb.charAt(end) != ' ') end++;// 翻轉單詞reverse(sb, start, end - 1);// 更新start，去找下一個單詞end++;start = end;}}
}
四、時間復雜度和空間復雜度
1. 時間復雜度
trimSpaces?方法：這個方法遍歷了整個字符串一次，所以時間復雜度是 O(n)，其中 n 是字符串的長度。reverse?方法：這個方法是用來翻轉字符串的一部分，它的時間復雜度是 O(m)，其中 m 是要翻轉的部分的長度。reverseEachWord?方法：這個方法遍歷了整個字符串一次，并且在每個單詞上調用了一次?reverse?方法。假設單詞的平均長度是 k，那么這個方法的時間復雜度是 O(n + k)，其中 n 是字符串的長度，k 是單詞的平均長度。
綜合起來，整個算法的時間復雜度是 O(n + k)，因為?trimSpaces?和?reverseEachWord?都是遍歷整個字符串，而?reverse?是在單個單詞上操作，所以單詞的總長度是 n。
2. 空間復雜度
trimSpaces?方法：這個方法創建了一個新的 StringBuilder 來存儲處理后的字符串，所以空間復雜度是 O(n)，其中 n 是字符串的長度。reverse?方法和?reverseEachWord?方法：這兩個方法都是原地操作，沒有使用額外的空間，所以它們的空間復雜度是 O(1)。
綜合起來，整個算法的空間復雜度是 O(n)，因為?trimSpaces?方法創建了一個新的 StringBuilder 來存儲處理后的字符串。
五、總結知識點
-
字符串處理：對字符串進行遍歷、去除前后空格、縮減中間多余空格等操作。
-
StringBuilder 類的使用：StringBuilder 是一個可變的字符序列，用于高效地拼接字符串、修改字符串內容等。
-
字符串反轉：通過交換字符串首尾字符的位置，實現字符串的反轉。
-
循環和條件語句：使用 while 循環和 if 條件語句來控制程序的邏輯流程。
-
字符數組與字符串的轉換：StringBuilder 在內部維護一個字符數組，可以通過 append 方法添加字符，最終通過 toString 方法轉換為字符串。
-
邊界條件處理：在去除前后空格和反轉字符串時，需要考慮字符串為空或只有一個字符的邊界情況。
-
函數封裝：將去除空格、反轉字符串、反轉每個單詞等功能封裝成單獨的函數，提高代碼的可讀性和可維護性。
-
指針或索引的使用：在遍歷字符串時，使用指針或索引來跟蹤當前處理的位置。
以上就是解決這個問題的詳細步驟，希望能夠為各位提供啟發和幫助。
)
異常)
