題目

給你一個(gè)字符串 s，顛倒字符串中單詞的順序。單詞是由非空格字符組成的字符串。s 中使用至少一個(gè)空格將字符串中的單詞分隔開(kāi)。返回單詞順序顛倒且單詞之間用單個(gè)空格連接的結(jié)果字符串。
注意：輸入字符串 s中可能會(huì)存在前導(dǎo)空格、尾隨空格或者單詞間的多個(gè)空格。返回的結(jié)果字符串中，單詞間應(yīng)當(dāng)僅用單個(gè)空格分隔，且不包含任何額外的空格。
例：
輸入：s = "the sky is blue"
輸出："blue is sky the"

方法一：庫(kù)函數(shù)

將字符串分割后翻轉(zhuǎn)輸出

class Solution(object):
    def reverseWords(self, s):
        record = s.split()
        return ' '.join(reversed(record))

方法二：不使用輔助空間

刪除多余空格，翻轉(zhuǎn)整個(gè)字符數(shù)組，翻轉(zhuǎn)每個(gè)單詞

• 刪除多余空格。左指針指向首部，右指針指向尾部。首先判斷首尾是否存在多余空格，若首部存在多余空格，則左指針向右移動(dòng)，直至不再存在多余空格；若尾部存在多余空格，則右指針向做移動(dòng)，直至不再存在多余空格。之后判斷中間部分是否存在多余空格，建立臨時(shí)列表存放除去多余空格后的字符數(shù)組，移動(dòng)左指針，若指向位置不為空格或指向位置為空格但是其前一位不為空格，那么將該位置所對(duì)應(yīng)的值存入列表。
• 翻轉(zhuǎn)字符數(shù)組。左指針指向首部，右指針指向尾部。循環(huán)，左右指針指向位置的對(duì)應(yīng)值交換，左指針向右移一格，右指針向左移一格
• 翻轉(zhuǎn)單詞。通過(guò)開(kāi)端和末端兩個(gè)指針尋找單詞，兩個(gè)指針的起始位置均為 0。當(dāng)末端指針指向非空格值時(shí)，向右移動(dòng)，直至指向的位置的值為空格，此時(shí)開(kāi)端指針指向某個(gè)單詞的第一個(gè)字母，而末端指針指向該單詞的最后一個(gè)字母。通過(guò)之前的反轉(zhuǎn)字符數(shù)組函數(shù)對(duì)該字符數(shù)組進(jìn)行翻轉(zhuǎn)，從而得到一個(gè)正確的單詞。之后，兩個(gè)指針移向下一個(gè)單詞的開(kāi)端，開(kāi)始新一輪尋找

class Solution(object):
    # 刪除多余空格
    def del_space(self, s):
        length = len(s)
        left, right = 0, length - 1
        temp = []

        while left <= right and s[left] == ' ':
            left += 1
        while left <= right and s[right] == ' ':
            right -= 1
        while left <= right:
            if s[left] != ' ':
                temp.append(s[left])
            elif s[left] == ' ' and temp[-1] != ' ':
                temp.append(s[left])
            left += 1
        
        return temp

    # 翻轉(zhuǎn)字符數(shù)組
    def reverse_string(self, nums, left, right):
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

    # 翻轉(zhuǎn)單詞
    def reverse_word(self, nums):
        length = len(nums)
        start, end = 0, 0
        while start < length:
            while end < length and nums[end] != ' ':
                end += 1
            self.reverse_string(nums, start, end - 1)
            start = end + 1
            end = start

    def reverseWords(self, s):
        result = self.del_space(s)
        self.reverse_string(result, 0, len(result) - 1)
        self.reverse_word(result)
        return ''.join(result)

相關(guān)知識(shí)

• split(sep, num)： str.split()
  分割字符串
  sep：分隔符。默認(rèn)為 None，表示所有空字符，包括空格、換行符“\n”、制表符“\t”等
  num：分割次數(shù)。默認(rèn)為沒(méi)有限制
  例：字符串 s = " world hello " （前后分別為兩個(gè)空格
  若使用默認(rèn)的分割方式 s.split()，結(jié)果為 ['world', 'hello']
  若使用空格進(jìn)行分割 s.split(' ')，結(jié)果為 ['', '', 'world', 'hello', '', '']
• reversed(seq)：
  翻轉(zhuǎn)。
  seq：對(duì)象?？蔀榱斜?、元組等

報(bào)錯(cuò)

• can only join in an iterable
  
  
  list.reverse() 返回值為 None，該結(jié)果需使用 print 打印出來(lái)

參考

分割：http://c.biancheng.net/view/4276.html
反轉(zhuǎn)：https://wenku.baidu.com/view/2f7e931364ec102de2bd960590c69ec3d5bbdb18.html
代碼相關(guān)：https://programmercarl.com/0151.%E7%BF%BB%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2%E9%87%8C%E7%9A%84%E5%8D%95%E8%AF%8D.html