Medium

题目描述

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

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

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

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

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

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

注意： 超出返回长度的数组元素不重要，可以忽略。

示例 1：

输入：chars = ["a","a","b","b","c","c","c"]
输出：6
解释：groups 是 ["aa", "bb", "ccc"]。压缩后变为 "a2b2c3"。

示例 2：

输入：chars = ["a"]
输出：1
解释：唯一的组是 "a"，它保持未压缩，因为它是一个字符。

示例 3：

输入：chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
输出：4
解释：groups 是 ["a", "bbbbbbbbbbbb"]。压缩后变为 "ab12"。

提示：

  • 1 <= chars.length <= 2000
  • chars[i] 可以是小写英文字母、大写英文字母、数字或符号

解题思路

这道题要求我们对字符数组进行原地压缩，核心思路是使用双指针技巧。

解题思路：

  1. 双指针遍历：使用读指针 read 遍历原数组，写指针 write 记录压缩后的位置
  2. 分组统计：对于每个字符，统计连续出现的次数
  3. 原地写入：将字符和计数（如果大于1）写入到 write 位置
  4. 数字处理：当计数大于等于10时，需要将数字拆分成多个字符

算法步骤：

  • 初始化读写指针都为0
  • 遍历数组，对每个字符进行分组：
    • 记录当前字符并统计连续出现次数
    • 将字符写入write位置
    • 如果计数大于1，将计数转换为字符串并逐位写入
  • 返回最终的写指针位置

关键点：

  • 计数为1时只写字符，不写数字
  • 计数大于等于10时需要逐位写入数字
  • 原地操作，空间复杂度O(1)

这种方法时间复杂度为O(n)，空间复杂度为O(1)，是最优解法。

代码实现

class Solution {
public:
    int compress(vector<char>& chars) {
        int write = 0, read = 0;
        int n = chars.size();
        
        while (read < n) {
            char currentChar = chars[read];
            int count = 0;
            
            // 统计连续相同字符的数量
            while (read < n && chars[read] == currentChar) {
                read++;
                count++;
            }
            
            // 写入字符
            chars[write++] = currentChar;
            
            // 如果count > 1，写入数字
            if (count > 1) {
                string countStr = to_string(count);
                for (char c : countStr) {
                    chars[write++] = c;
                }
            }
        }
        
        return write;
    }
};

class Solution:
    def compress(self, chars: List[str]) -> int:
        write = 0
        read = 0
        n = len(chars)
        
        while read < n:
            current_char = chars[read]
            count = 0
            
            # 统计连续相同字符的数量
            while read < n and chars[read] == current_char:
                read += 1
                count += 1
            
            # 写入字符
            chars[write] = current_char
            write += 1
            
            # 如果count > 1，写入数字
            if count > 1:
                count_str = str(count)
                for c in count_str:
                    chars[write] = c
                    write += 1
        
        return write

public class Solution {
    public int Compress(char[] chars) {
        int write = 0, read = 0;
        int n = chars.Length;
        
        while (read < n) {
            char currentChar = chars[read];
            int count = 0;
            
            // 统计连续相同字符的数量
            while (read < n && chars[read] == currentChar) {
                read++;
                count++;
            }
            
            // 写入字符
            chars[write++] = currentChar;
            
            // 如果count > 1，写入数字
            if (count > 1) {
                string countStr = count.ToString();
                foreach (char c in countStr) {
                    chars[write++] = c;
                }
            }
        }
        
        return write;
    }
}

var compress = function(chars) {
    let write = 0, read = 0;
    const n = chars.length;
    
    while (read < n) {
        const currentChar = chars[read];
        let count = 0;
        
        // 统计连续相同字符的数量
        while (read < n && chars[read]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)遍历一遍字符数组，每个字符访问一次
空间复杂度O(1)只使用常量额外空间，原地修改数组

相关题目