題目要求:給定一個字符串,將其中單詞順序反轉,且每個單詞之間有且僅有一個空格。
思路:因為本題沒有限制空間復雜度,所以首先想到的是用split直接分割單詞,然后將單詞倒敘相加。
但如果想讓空間復雜度為O(1)的話,可以使用快慢指針,慢指針指向的是最后實際存放的位置,快指針進行判斷實現不同處理。所以過程就應該為先去除多余空格,然后整體反轉再每個單詞反轉即可,例如:hello? world -> dlrow olleh ->world hello,但是實際實現是有些難度。
leetcode實戰:
代碼實現:
注:其中
if (s[i] != ' ')
if (slow != 0) s[slow++] = ' ';
第一個判斷用來刪除所有的空格,第二個判斷是用來在單詞之間重新增加空格。
while (i < s.size() && s[i] != ' ')
此循環用來將單詞插入,若遇到空格說明單詞結束,重新開始下次for循環。
if (i == s.size() || s[i] == ' ')
此處用來將每個單詞反轉成正確順序。