Typescript 編碼編年史：反轉字串中的單字

問題陳述：

給定一個輸入字串 s，反轉單字的順序。單字被定義為非空格字元的序列。 s 中的單字將至少由一個空格分隔。傳回由單一空格以相反順序連接的單字字串。

請注意，s 可能包含前導或尾隨空格或兩個單字之間的多個空格。傳回的字串應該只有一個空格來分隔單字。請勿包含任何額外空格。

範例1：

• 輸入：s =“天空是藍色的”
• 輸出：“藍色是天空”

範例2：

• 輸入：s =“你好世界”
• 輸出：“世界你好”
• 說明：反轉的字串不應包含前導或尾隨空格。

範例3：

• 輸入：s =“一個很好的例子”
• 輸出：“例子很好”
• 說明：您需要將兩個單字之間的多個空格減少為反轉字串中的單一空格。

限制條件：

• 1
• s 包含英文字母（大小寫）、數字和空格 ' '。
• s 中至少有一個單字。

初步思考過程：

要解決這個問題，我們需要：

1. 將字串拆分為單字。
2. 顛倒單字的順序。
3. 將單字重新連接在一起，每個單字之間有一個空格。

基本解決方案：

代碼：

function reverseWordsBruteForce(s: string): string {
    // Split the string by spaces and filter out empty strings
    let words = s.trim().split(/\s+/);

    // Reverse the array of words
    words.reverse();

    // Join the words with a single space
    return words.join(' ');
}

時間複雜度分析：

• 時間複雜度： O(n)，其中 n 是字串的長度。分裂、反轉和合併都需要線性時間。
• 空間複雜度： O(n)，其中 n 是字串的長度。我們將單字儲存在陣列中，將最終結果儲存在字串中。

限制：

考慮到限制，該解決方案是有效的。但是，它為單字數組使用了額外的空間。

優化方案：

如果字串資料類型是可變的，並且我們需要使用 O(1) 額外空間就地解決它，我們可以使用兩指標技術來反轉原始字串中的單字。

代碼：

function reverseWordsOptimized(s: string): string {
    // Trim the string and convert it to an array of characters
    let chars = s.trim().split('');

    // Helper function to reverse a portion of the array in place
    function reverse(arr: string[], left: number, right: number) {
        while (left < right) {
            [arr[left], arr[right]] = [arr[right], arr[left]];
            left++;
            right--;
        }
    }

    // Reverse the entire array of characters
    reverse(chars, 0, chars.length - 1);

    // Reverse each word in the reversed array
    let start = 0;
    for (let end = 0; end <= chars.length; end++) {
        if (end === chars.length || chars[end] === ' ') {
            reverse(chars, start, end - 1);
            start = end + 1;
        }
    }

    // Join the characters back into a string and split by spaces to remove extra spaces
    return chars.join('').split(/\s+/).join(' ');
}

時間複雜度分析：

• 時間複雜度： O(n)，其中 n 是字串的長度。每個字元都會被處理固定次數。
• 空間複雜度： O(1)，因為我們正在就地修改數組並僅使用恆定量的額外空間。

基本解決方案的改進：

• 最佳化的解決方案透過對字元數組執行就地操作來降低空間複雜度。

邊緣情況和測試：

邊緣情況：

1. 字串包含前導和尾隨空格。
2. 字串的單字之間包含多個空格。
3. 該字串僅包含一個單字。
4. 字串長度達到最小或最大限制。

測試用例：

console.log(reverseWordsBruteForce("the sky is blue")); // "blue is sky the"
console.log(reverseWordsBruteForce("  hello world  ")); // "world hello"
console.log(reverseWordsBruteForce("a good   example")); // "example good a"
console.log(reverseWordsBruteForce("singleWord")); // "singleWord"
console.log(reverseWordsBruteForce("   ")); // ""

console.log(reverseWordsOptimized("the sky is blue")); // "blue is sky the"
console.log(reverseWordsOptimized("  hello world  ")); // "world hello"
console.log(reverseWordsOptimized("a good   example")); // "example good a"
console.log(reverseWordsOptimized("singleWord")); // "singleWord"
console.log(reverseWordsOptimized("   ")); // ""

一般解決問題的策略：

1. 理解問題：仔細閱讀問題陳述，了解要求和限制。
2. 辨識關鍵操作：決定所需的關鍵操作，例如分割、反轉、連接單字。
3. 最佳化可讀性：使用清晰簡潔的邏輯來確保程式碼易於理解。
4. 徹底測試：使用各種情況（包括邊緣情況）測試解決方案，以確保正確性。

識別類似問題：

1. 字串運算：

   • 需要根據具體情況修改字串的問題。
   • 範例：顛倒句子中每個單字中的字元順序。

2. 雙指針技術：

   • 使用兩個指標有助於最佳化解決方案的問題。
   • 範例：從排序數組中刪除重複項。

3. 就地演算法：

   • 需要在有限的額外空間內進行操作的問題。
   • 範例：將陣列向右旋轉 k 步。

結論：

• 使用暴力方法和最佳化的就地方法可以有效地解決字串中單字反轉的問題。
• 理解問題並將其分解為可管理的部分至關重要。
• 使用清晰的邏輯並優化可讀性可確保解決方案易於理解。
• 使用各種邊緣情況進行測試可確保穩健性。
• 認識問題的模式有助於將類似的解決方案應用於其他挑戰。

透過練習這些問題和策略，您可以提高解決問題的能力，並為各種編碼挑戰做好更好的準備。

以上是Typescript 編碼編年史：反轉字串中的單字的詳細內容。更多資訊請關注PHP中文網其他相關文章！