String Compression

443. 压缩字符串

分析

遍历字符数组：
- 使用两个指针，一个 i 遍历原数组，另一个 k 表示压缩后字符存储的位置
记录连续重复字符：
- 每次找到一组连续重复的字符，记录其长度 len
压缩字符组：
- 将字符写入结果数组。
- 如果长度 len > 1，将其转为字符串形式逐个写入，需要使用 std::reverse 处理因低位数字先写入导致的顺序问题
更新指针：
- 将指针 i 移动到下一个未处理的字符位置
返回结果：
- 最终返回数组新长度 k

时间复杂度

遍历整个数组一次，时间复杂度为 O(n)

总时间复杂度 O(n)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


class Solution {
public:
    int compress(vector<char>& s) 
    {
        int k = 0; // 压缩后存储字符的位置
        for (int i = 0; i < s.size(); ++i)
        {
            int j = i + 1;
            // 找到连续重复字符的结尾位置
            while (j < s.size() && s[i] == s[j])
                ++j;

            // 写入当前字符
            s[k++] = s[i];

            // 计算连续字符的长度
            int len = j - i;

            // 如果长度大于 1，将其转为字符串写入数组
            if (len > 1)
            {
                int t = k; // 用于临时存储数字的开始位置
                while (len)
                {
                    s[t++] = '0' + len % 10;
                    len /= 10;
                }
                // 将数字部分反转以正确顺序写入
                std::reverse(s.begin() + k, s.begin() + t);
                k = t; // 更新压缩后的位置
            }

            // 更新 i 到当前字符组的结束位置
            i = j - 1;
        }    
        return k; // 返回压缩后的数组长度
    }
};