LeetCode 443. 压缩字符串

2025-11-06 HGNULB 约 5 分钟

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

分类

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

题目描述

✅ 443. 压缩字符串

题意分析

输入是一个字符数组，要求把「连续出现的相同字符」改写成「字符 + 出现次数」的形式，并且必须写回原数组，函数只返回压缩后的有效长度，调用方只看数组的前这么多位，后面残留什么都不再关心。

有三处约束需要在读题时就抓住。其一，次数必须以十进制字符的形式写回，12 占两个格子而不是一个，所以「一组消耗几个格子」不是常数。其二，次数为 1 时只写字符、不写数字，这是压缩规则里唯一的不对称之处。其三，题目额外要求 $O(1)$ 的额外空间，也就是说不允许先拼一个结果数组再拷回去。

边界上要留意：只有一个字符的数组压缩后仍是它自己，长度 1；整串同一个字符时结果最短；而像「每个字符都只出现一次」这种输入，压缩后长度与原串相等，一个格子都省不下来——这提醒我们，压缩结果永远不会比已经读过的部分更长，这一点后面会成为原地覆盖的安全依据。

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

核心思路

题目同时要求「按连续段压缩」和「写回原数组」，因此用两个下标分工：read 找到当前连续段的右边界，write 写入压缩结果。长度为 1 的段只写字符；长度大于 1 时再写十进制次数。

原地写入是否安全，取决于一个不变量：每轮开始时，chars[0, write) 已是 chars[0, read) 的正确压缩结果，并且 write <= read。一段长度为 count 的字符最多写出 1 + digits(count) 个字符；count = 1 时写 1 个，count >= 2 时也不会超过 count。因此写指针不会追上尚未读取的数据。

次数要从高位到低位写入。为了严格保持 O(1) 额外空间，可以先用取模把数字逆序写进当前数组，再原地翻转这一小段。每轮写完后，不变量继续成立；所有连续段处理完时，[0, write) 就是完整答案。

解题步骤

初始化 read = 0、write = 0，外层循环每次处理一个连续字符段。

记下段首 start，让 read 前进到第一个不同字符，段长为 read - start。

先把段内字符写到 chars[write]；若段长大于 1，再逐位写次数。

取模得到的数字顺序是反的，因此只翻转本次写入的数字区间。

扫描结束后返回 write，数组尾部的旧内容不属于有效答案。

例如 ['a', 'b' x 12]：第一段写 a，第二段先写 b，再逆序写 2、1 并翻转为 1、2，有效前缀为 a b 1 2，返回 4。

代码实现

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
}

复杂度分析

时间复杂度：O(n)。读指针遍历原数组一次；每个输出数字至多再参与一次翻转，而输出长度不超过 n。

空间复杂度：O(1)。计数数字直接写入并在原数组中翻转，只使用常数个变量。

关键点总结

面试时先讲清 write <= read，这是原地覆盖不会破坏未读数据的依据。

外层按连续段推进，段长用右边界减左边界计算，末尾段无需额外处理。

count = 1 不写次数；多位次数必须按十进制字符逐位写入。

返回的是有效前缀长度，不需要清理 [write, n) 的残留字符。

易错点总结

把单个字符写成 a1：['a','b'] 应返回 2，而不是写成 a1b1。

逆序写数字后忘记翻转：12 个 a 会得到 a21，正确结果是 a12。

把次数强转为字符：(char) 12 不是字符 '1'、'2'，多位数必须拆位。

越界条件顺序写反：必须先判断 read < chars.length，再访问 chars[read]。

返回原数组长度：['a','a','b'] 的有效结果是 a2b、长度 3，尾部内容不参与答案。

相似题目

题目	难度	考察点
26. 删除有序数组中的重复项	简单	有序数组去重，每个值只保留首次出现
27. 移除元素	简单	按值过滤，写指针跳过所有等于目标的元素
80. 删除有序数组中的重复项 II	中等	每个值最多保留两次，靠与 `write - 2` 比较判重
283. 移动零	简单	非零元素前移后补零，需保持相对顺序不变