LeetCode 443. 压缩字符串

原题链接

题目描述

给你一个字符数组 $chars$ ，请使用下述算法压缩：

从一个空字符串 $s$ 开始。对于 $chars$ 中的每组 连续重复字符 ：

如果这一组长度为 $1$ ，则将字符追加到 $s$ 中。
否则，需要向 $s$ 追加字符，后跟这一组的长度。

压缩后得到的字符串 $s$ 不应该直接返回，需要转储到字符数组 $chars$ 中。需要注意的是，如果组长度为 $10$ 或 $10$ 以上，则在 $chars$ 数组中会被拆分为多个字符。

请在修改完输入数组后，返回该数组的新长度。

你必须设计并实现一个只使用常量额外空间的算法来解决此问题。

数据范围

$1 \le chars.length \le 2000$

chars[i] 可以是小写英文字母、大写英文字母、数字或符号

样例

输入样例1：

chars = ["a","a","b","b","c","c","c"]

输出样例1:

返回 6 ，输入数组的前 6 个字符应该是：["a","2","b","2","c","3"]

样例1解释：

$aa$ 被 $a2$ 替代。 $bb$ 被 $b2$ 替代。 $ccc$ 被 $c3$ 替代。

输入样例2：

chars = ["a"]

输出样例2:

返回 1 ，输入数组的前 1 个字符应该是：["a"]

样例2解释：

没有任何字符串被替代。

输入样例3：

chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]

输出样例3:

返回 4 ，输入数组的前 4 个字符应该是：["a","b","1","2"]。

样例3解释：

由于字符 $a$ 不重复，所以不会被压缩。 $bbbbbbbbbbbb$ 被 $b12$ 替代。
注意每个数字在数组中都有它自己的位置。`

思路

给每个字符出现的次数找出来，可以用双指针来找。然后在后面接上出现的次数即可，如果出现次数等于 $1$ 就直接跳过。

在字符后接上出现次数可以参考下面两种方法

给出现次数变成字符串，然后遍历字符串，填入对应的位置即可（见C++代码）。
每次给出现次数的个位取出，填入对应的位置，然后翻转这段区间即可（见Java代码）。

代码

C++

class Solution {
public:
    int compress(vector<char>& chars) {
        int idx = 0;
        for ( int i = 0; i < chars.size(); i ++ )
        {
            int j = i + 1;
            while ( j < chars.size() && chars[j] == chars[i] ) j ++;
            chars[idx ++] = chars[i];
            if ( j - i > 1 )
                for ( auto x : to_string(j - i) )
                    chars[idx ++] = x;
            i = j - 1;
        }
        return idx;
    }
};

Java

class Solution {
    public int compress(char[] chars) {
        int idx = 0;
        for ( int i = 0; i < chars.length; i++ )
        {
            int j = i + 1;
            while ( j < chars.length && chars[j] == chars[i] ) j ++;
            chars[idx ++] = chars[i];
            int len = j - i;
            if ( len > 1 )
            {
                int t = idx;
                while ( len > 0 )
                {
                    chars[t ++] = (char) ('0' + len % 10);
                    len /= 10;
                }
                for ( int l = idx, r = t - 1; l < r; l ++, r -- )
                {
                    char c = chars[l]; chars[l] = chars[r]; chars[r] = c;
                }
                idx = t;
            }
            i = j - 1;
        }
        return idx;
    }
}