微軟面試題： LeetCode 151. 翻轉字元串里的單詞 出現次數：6
題目描述：
給定一個字元串，逐個翻轉字元串中的每個單詞。
說明：
無空格字元構成一個 單詞 。
輸入字元串可以在前面或者後面包含多餘的空格，但是反轉後的字元不能包括。
如果兩個單詞間有多餘的空格，將反轉後單詞間的空格減少到只含一個。
示例：
輸入：" hello world! " 輸出："world! hello" 解釋：輸入字元串可以在前面或者後面包含多餘的空格，但是反轉後的字元不能包括。
分析：本題考查的重點是能夠 在原字元串上實現 時間 O（n） 空間（1） 的演算法
程式碼如下：
1 #ifndef SOLUTION_SOLUTION_H 2 #define SOLUTION_SOLUTION_H 3 4 #include <bits/stdc++.h> 5 6 using namespace std; 7 8 class Solution 9 { 10 public: 11 //Time：O(n) space: O(1) 12 string reverseWords(string s) { 13 // 反轉整個字元串 14 reverse(s.begin(), s.end()); 15 16 int n = s.size(); 17 int idx = 0;//指向剛放好並翻轉過的單詞的後一個位置 18 for (int start = 0; start < n; ++start) { 19 if (s[start] != ' ') 20 { 21 // 在剛放好的單詞後填充一個空白字元，idx前進一位指向下一個單詞該放到的起始位置 22 // 第一個單詞直接從 0 處開始放，前面不需要填充空格 23 if (idx != 0) s[idx++] = ' '; 24 //保存下一個單詞該放到的起始位置 25 int begin_tmp = idx; 26 // 循環遍歷至單詞的末尾 27 int end = start; 28 while (end < n && s[end] != ' ') s[idx++] = s[end++]; 29 30 // 反轉剛放好的單詞 31 reverse(s.begin() + begin_tmp, s.begin() + idx); 32 // 更新start，去找下一個單詞 33 start = end; 34 } 35 } 36 //刪去字元串尾部的空格 37 s.erase(s.begin() + idx, s.end()); 38 return s; 39 } 40 }; 41 42 #endif //SOLUTION_SOLUTION_H
