微軟面試題: 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