Typescript 編碼編年史：字串壓縮-js教程-PHP中文網

Typescript Coding Chronicles: String Compression

問題陳述：

給定一個字元數組 char，使用以下演算法對其進行壓縮：

以空字串 s 開頭。
對於 chars 中的每組連續重複字元：
- 如果組的長度為1，則將字元附加到s。
- 否則，請附加字符，後面跟著組的長度。

壓縮後的字串 s 不應單獨返回，而是儲存在輸入字元數組 chars 中。請注意，長度為 10 或更長的群組將被拆分為 chars 中的多個字元。

修改完輸入陣列後，傳回陣列的新長度。

您必須編寫一個僅使用恆定額外空間的演算法。

範例1：

輸入：chars = ["a","a","b","b","c","c","c"]
輸出：回傳6，輸入陣列的前6個字元應為：["a","2","b","2","c","3"]
解釋：這些組別是「aa」、「bb」和「ccc」。這會壓縮為“a2b2c3”。

範例2：

輸入：chars = ["a"]
輸出：回傳1，輸入陣列的第一個字元應該是：[“a”]
解釋：唯一的群組是“a”，由於它是單個字符，所以它保持未壓縮狀態。

範例3：

輸入： chars = ["a","b","b","b","b","b","b","b","b","b","b ”,“b”,“b”]
輸出：傳回4，輸入陣列的前4個字元應為：["a","b","1","2"]
解釋：這組是「a」和「bbbbbbbbbbbb」。這會壓縮為“ab12”。

限制條件：

1
chars[i] 是小寫英文字母、大寫英文字母、數字或符號。

初步思考過程：

為了解決這個問題，我們需要迭代數組，同時追蹤當前字元及其計數。當遇到新字元時，我們將目前字元及其計數（如果大於 1）新增到陣列中。我們需要確保這樣做能夠滿足空間複雜度要求。

基本解決方案（暴力）：

暴力解決方案涉及建立一個新數組來儲存輸入數組的壓縮版本。這不節省空間，但可以幫助我們理解所涉及的步驟。

代碼：

function compressBruteForce(chars: string[]): number {
    const n = chars.length;
    let compressed: string[] = [];
    let i = 0;

    while (i < n) {
        let char = chars[i];
        let count = 0;

        while (i < n && chars[i] === char) {
            i++;
            count++;
        }

        compressed.push(char);
        if (count > 1) {
            compressed.push(...count.toString().split(''));
        }
    }

    for (let j = 0; j < compressed.length; j++) {
        chars[j] = compressed[j];
    }

    return compressed.length;
}

登入後複製

時間複雜度分析：

時間複雜度： O(n)，其中 n 是陣列的長度。我們遍歷數組一次來計算字符，一次來寫入結果。
空間複雜度： O(n)，因為我們為壓縮陣列使用額外的空間。

限制：

暴力解決方案空間利用率不高，且不滿足僅使用恆定額外空間的限制。

優化方案：

最佳化的解決方案涉及修改輸入數組以儲存壓縮版本。我們使用兩個指標：一個用於讀取輸入數組，一個用於寫入壓縮輸出。

代碼：

function compress(chars: string[]): number {
    let writeIndex = 0;
    let i = 0;

    while (i < chars.length) {
        let char = chars[i];
        let count = 0;

        // Count the number of consecutive repeating characters
        while (i < chars.length && chars[i] === char) {
            i++;
            count++;
        }

        // Write the character
        chars[writeIndex] = char;
        writeIndex++;

        // Write the count if greater than 1
        if (count > 1) {
            let countStr = count.toString();
            for (let j = 0; j < countStr.length; j++) {
                chars[writeIndex] = countStr[j];
                writeIndex++;
            }
        }
    }

    return writeIndex;
}

登入後複製

時間複雜度分析：

時間複雜度： O(n)，其中 n 是陣列的長度。我們遍歷數組一次來計算字符，一次來寫入結果。
空間複雜度： O(1)，因為我們只為變數使用恆定量的額外空間。

基本解決方案的改進：

最佳化的解決方案透過修改輸入數組將空間複雜度降低到 O(1)。

邊緣情況和測試：

邊緣情況：

陣列僅包含一個字元。
陣列不包含連續的重複字元。
陣列中包含大量連續的重複字元。

測試用例：

console.log(compressBruteForce(["a","a","b","b","c","c","c"])); // 6, ["a","2","b","2","c","3"]
console.log(compressBruteForce(["a"])); // 1, ["a"]
console.log(compressBruteForce(["a","b","b","b","b","b","b","b","b","b","b","b","b"])); // 4, ["a","b","1","2"]
console.log(compressBruteForce(["a","a","a","a","a","a","a","a","a","a"])); // 3, ["a","1","0"]
console.log(compressBruteForce(["a","b","c"])); // 3, ["a","b","c"]

console.log(compress(["a","a","b","b","c","c","c"])); // 6, ["a","2","b","2","c","3"]
console.log(compress(["a"])); // 1, ["a"]
console.log(compress(["a","b","b","b","b","b","b","b","b","b","b","b","b"])); // 4, ["a","b","1","2"]
console.log(compress(["a","a","a","a","a","a","a","a","a","a"])); // 3, ["a","1","0"]
console.log(compress(["a","b","c"])); // 3, ["a","b","c"]

登入後複製