LeetCode 443. 压缩字符串

2025-11-06 HGNULB 约 5 分钟

文章信息 13 个分类 2 个标签

分类

LeetCode CodeTop 中等未解决 20-50 LeetCode 75 腾讯字节阿里华为京东虾皮猿辅导

题目描述

✅ 443. 压缩字符串

题意分析

按连续相同字符分组，把每组改写为“字符 + 出现次数”，但只出现一次的组不写次数。次数达到多位时，需要把十进制数字逐个写入字符数组。

压缩结果必须写回原数组的前缀，函数返回这个有效前缀的长度，后面的旧内容不参与答案。相同字符如果被其他字符隔开，就属于不同组；输入中的字母、数字和符号都按相同的分组规则处理，并且只能使用常数额外空间。

解法：读写双指针原地压缩

核心思路

[!blue]

用 read 扫描尚未处理的原数据，用 write 指向结果前缀的下一个写入位置。每轮先记下组首 start，让 read 越过整段相同字符，组长就是 read - start。先把整组读完，再写结果，就不会在计数尚未结束时改动原数据。

每组先写一个字符，组长大于一时再写次数。这个编码一定不会比原组更长：长度一只写一个字符；长度至少二时，一个字符加上组长的十进制位数也不超过组长。因此处理完任意前缀后，写入位置始终不会超过已读取的位置，原地写入不会覆盖下一组尚未读取的内容。

为了不创建计数字符串，直接用 count % 10 取最低位，转换成数字字符后写入，再将 count 除以十。取出的顺序与正常读数相反，所以记住数字开始位置 digitStart，写完后只反转这一段数字，不包含前面的组字符。

每轮都会消费一个完整连续组，并在结果后追加它唯一的编码。所有组处理完后，write 就是完整压缩结果的长度；无需清理尾部残留字符，也不需要另建输出数组。

解题步骤

初始化 read = 0、write = 0，只要还有未读字符就开始处理下一组。

保存组首，让 read 前进到第一个不同字符或数组末尾，得到该组长度。

写入组字符；若组长为一，本组处理完成。

组长大于一时，记录数字起点，通过取模和除法依次写出次数的各位数字，再原地反转这段数字。

继续处理下一组，最终返回 write。

代码实现

class Solution {
    public int compress(char[] chars) {
        int read = 0;
        int write = 0;

        while (read < chars.length) {
            int start = read;

            while (read < chars.length && chars[read] == chars[start]) {
                read++;
            }

            chars[write++] = chars[start];
            int count = read - start;

            if (count > 1) {
                // 次数按低位先写，最后只反转这一段数字，不能把字符也反转。
                int digitStart = write;

                while (count > 0) {
                    chars[write++] = (char) ('0' + count % 10);
                    count /= 10;
                }

                for (int left = digitStart, right = write - 1; left < right; left++, right--) {
                    char temp = chars[left];

                    chars[left] = chars[right];
                    chars[right] = temp;
                }
            }
        }

        return write;
    }
}

func compress(chars []byte) int {
    read, write := 0, 0

    for read < len(chars) {
        start := read
        for read < len(chars) && chars[read] == chars[start] {
            read++
        }

        chars[write] = chars[start]
        write++
        count := read - start
        if count > 1 {
            // 次数按低位先写，最后只反转这一段数字，不能把字符也反转。
            digitStart := write
            for count > 0 {
                chars[write] = byte('0' + count%10)
                write++
                count /= 10
            }
            for left, right := digitStart, write-1; left < right; left, right = left+1, right-1 {
                chars[left], chars[right] = chars[right], chars[left]
            }
        }
    }
    return write
}

复杂度分析

设原数组长度为 $n$。

时间复杂度：$O(n)$。读取总共扫描 $n$ 个字符，写入长度不超过 $n$，每个输出数字最多再参与一次反转。

辅助空间复杂度：$O(1)$。只使用指针、计数和交换变量，次数也直接写在原数组中。

关键点总结

[!green]

按连续组读取，先完成计数，再写该组编码。

压缩长度不超过已消费的输入长度，保证读写指针原地操作安全。

次数逐位写出后只反转数字段，返回最终写指针。

易错点总结

[!yellow]

单个字符后不能写 1，否则违反输出规则，还可能让编码长度超过原组长度。

不能直接把整个次数强转为字符，多位次数必须拆成多个十进制数字字符。

取模从低位开始，写完后必须反转数字段，且不能把组字符一起反转。

扫描时先判断 read 是否越界，再访问数组元素；最后一组也通过同一循环处理。

返回值是新前缀长度，不是原数组长度，尾部残留内容无需再处理。

相似题目

题目	难度	关联与区别
38. 外观数列	中等	同样按连续段输出字符与次数，本题一次原地压缩，原题把描述结果反复作为下一轮输入。
604. 迭代压缩字符串	简单	原题按需展开已压缩的字符次数，本题执行相反的游程编码过程。
1531. 压缩字符串 II	困难	压缩字符串系列。压缩规则相同，II 允许先删至多 k 个字符，需要用 DP 选择最短编码；I 直接原地编码。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2025/44507116

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！