六六力扣刷題字元串之反轉字元串中的單詞

前言

之前小六六一直覺得自己的算法比較菜，算是一個短闆吧，以前刷題也還真是三天打魚，兩天曬網，刷幾天，然後就慢慢的不堅持了，是以這次，借助平台的活動，打算慢慢的開始開刷，并且自己還會給刷的題總結下，談談自己的一些思考，和自己的思路等等，希望對小夥伴能有所幫助吧，也可以借此機會把自己短闆補一補，希望自己能堅持下去呀

連結清單的合集

• 六六力扣刷題哈希表之哈希理論
• 六六力扣刷題哈希表之有效的字母異位詞
• 六六力扣刷題哈希表之兩個數組的交集
• 六六力扣刷題哈希表之快樂數
• 六六力扣刷題哈希表之贖金信
• 六六力扣刷題哈希表之三數之和

字元串

• 六六力扣刷題字元串之反轉字元串
• 六六力扣刷題字元串之反轉字元串2
• 六六力扣刷題字元串之替換空格

題目

給你一個字元串 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"

解釋：如果兩個單詞間有多餘的空格，反轉後的字元串需要将單詞間的空格減少到僅有一個。

思路

首先，這題 我們先試試用Java api寫出來，其實呢，很多語言對字元串提供了 ​

​split​

​​（拆分），​

​reverse​

​​（翻轉）和 ​

​join​

​（連接配接）等方法，是以我們可以簡單的調用内置的 API 完成操作：

Java其實也有的，是以我們來看看Java的寫法

class Solution {
    public String reverseWords(String) {
        // 除去開頭和末尾的空白字元
        s = s.trim();
        // 正則比對連續的空白字元作為分隔符分割
        List<String> wordList = Arrays.asList(s.split("\\s+"));
        Collections.reverse(wordList);
        return String.join(" ", wordList);
    }
}      

其實還是很簡單的，就是我們先去除收尾空白字元串，然後我們就用正則去分割，這個大家不知道會不會 \s+ 給大家解釋下 第一個\是轉意的意思，因為\會被認為是一個符号 然後\s在正則裡面是空格的意思，然後+代表的是一個或者多個，其實這樣翻譯下，發現就是我們要的東西了，把它變成數組，然後直接反轉數組就行了，最後在拼接一個，完美

整點難度

不要使用輔助空間，空間複雜度要求為O(1)。

不能使用輔助空間之後，那麼隻能在原字元串上下功夫了。

想一下，我們将整個字元串都反轉過來，那麼單詞的順序指定是倒序了，隻不過單詞本身也倒序了，那麼再把單詞反轉一下，單詞不就正過來了。

是以解題思路如下：

• 移除多餘空格
• 将整個字元串反轉
• 将每個單詞反轉

• 移除多餘空格 : "the sky is blue"
• 字元串反轉："eulb si yks eht"
• 單詞反轉："blue is sky the"

class Solution {
    public String reverseWords(String{
        StringBuilder sb = trimSpaces(s);

        // 翻轉字元串
        reverse(sb, 0, sb.length() - 1);

        // 翻轉每個單詞
        reverseEachWord(sb);

        return sb.toString();
    }

    public StringBuilder trimSpaces(String{
        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;
    }

    public void reverse(StringBuilder sb, int left, int{
        while (left < right) {
            char tmp = sb.charAt(left);
            sb.setCharAt(left++, sb.charAt(right));
            sb.setCharAt(right--, tmp);
        }
    }

    public 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，去找下一個單詞
            start = end + 1;
            ++end;
        }
    }
}      

結束