Typescript コーディングクロニクル: 文字列圧縮-jsチュートリアル-php.cn

Typescript コーディングクロニクル: 文字列圧縮

WBOY

リリース： 2024-07-17 08:48:20

オリジナル

641 人が閲覧しました

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 は配列の長さです。文字数をカウントするために配列を 1 回反復し、結果を書き込むために 1 回反復します。
スペースの複雑さ: O(n)。圧縮された配列に余分なスペースを使用するため。

制限事項:

総当りのソリューションはスペース効率が悪く、一定の追加スペースのみを使用するという制約を満たしません。

最適化されたソリューション:

最適化されたソリューションには、圧縮バージョンを保存するために入力配列を適切に変更することが含まれます。 2 つのポインターを使用します。1 つは入力配列の読み取り用、もう 1 つは圧縮出力の書き込み用です。

コード：

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 は配列の長さです。文字数をカウントするために配列を 1 回反復し、結果を書き込むために 1 回反復します。
空間複雑度: O(1)。変数には一定量の追加空間のみを使用するため。

基本的なソリューションの改善点:

最適化されたソリューションは、入力配列を適切に変更することにより、空間の複雑さを O(1) に削減します。

エッジケースとテスト:

エッジケース:

配列には 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"]

ログイン後にコピー