443. 压缩字符串

题目描述

输入字符数组 chars。把其中相同字符连续排成的每一段看作一组，从左到右逐组压缩：组长为 1 时只写这个字符；组长大于 1 时先写这个字符，再写组长的十进制数字。

组长达到两位或更多时，每一位数字各占数组中的一个位置，例如长度 12 要写成 "1"、"2" 两个元素。

压缩结果必须直接写回 chars 的开头部分（原地修改），然后返回压缩后的长度。超出这个长度的位置写什么都不影响判定。

只允许使用常数级的额外空间。

示例 1

输入：chars = ["a","a","b","b","c","c","c"]
输出：[6,["a","2","b","2","c","3"]]

解释：三组 aa、bb、ccc 压缩为 a2b2c3，长度为 6。

示例 2

输入：chars = ["a"]
输出：[1,["a"]]

解释：只有一个单字符组，原样保留，长度为 1。

示例 3

输入：chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
输出：[4,["a","b","1","2"]]

解释：分组为 a 和 12 个 b，压缩成 a、b、1、2，长度为 4。

数据范围

1 <= chars.length <= 2000
chars[i] 是小写字母、大写字母、数字或符号之一。

解题思路

用读写两个指针。read 负责扫描：记下当前组的字符 ch 和起点 start，把 read 一直向右推到第一个不等于 ch 的位置，组长就是 read - start。write 负责写入：先写 ch，组长大于 1 时再逐位写出组长的十进制字符。一组至少读了组长个字符，却最多只写 1 + 位数个，而位数总不超过组长 - 1（组长大于 1 时），所以 write 永远不会超过 read，写入不会覆盖还没读的字符。

为什么正确

每组处理完后，chars[0..write) 是 chars[0..read) 的压缩结果，且 write ≤ read。

复杂度分析

时间 O(n)，read 只向右走一遍，write 也只向右走；额外空间 O(1)（组长的字符串最多 4 位）。

易错点

组长为 1 时不要写 "1"；组长为 12 时要写两个字符 "1"、"2"，而不是一个 "12"。返回的是新长度 write，而不是原长度；也不要先写次数再写字符。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def compress(self, chars: List[str]) -> int:
        write = 0
        read = 0
        n = len(chars)
        while read < n:
            ch = chars[read]
            start = read
            while read < n and chars[read] == ch:
                read += 1
            chars[write] = ch
            write += 1
            count = read - start
            if count > 1:
                for d in str(count):
                    chars[write] = d
                    write += 1
        return write

class Solution {
    public int compress(char[] chars) {
        int write = 0;
        int read = 0;
        int n = chars.length;
        while (read < n) {
            char ch = chars[read];
            int start = read;
            while (read < n && chars[read] == ch) {
                read++;
            }
            chars[write] = ch;
            write++;
            int count = read - start;
            if (count > 1) {
                for (char d : String.valueOf(count).toCharArray()) {
                    chars[write] = d;
                    write++;
                }
            }
        }
        return write;
    }
}

class Solution {
public:
    int compress(vector<char>& chars) {
        int write = 0;
        int read = 0;
        int n = chars.size();
        while (read < n) {
            char ch = chars[read];
            int start = read;
            while (read < n && chars[read] == ch) {
                read++;
            }
            chars[write] = ch;
            write++;
            int count = read - start;
            if (count > 1) {
                for (char d : to_string(count)) {
                    chars[write] = d;
                    write++;
                }
            }
        }
        return write;
    }
};

func compress(chars []byte) int {
	write := 0
	read := 0
	n := len(chars)
	for read < n {
		ch := chars[read]
		start := read
		for read < n && chars[read] == ch {
			read++
		}
		chars[write] = ch
		write++
		count := read - start
		if count > 1 {
			for _, d := range []byte(strconv.Itoa(count)) {
				chars[write] = d
				write++
			}
		}
	}
	return write
}

var compress = function(chars) {
    let write = 0;
    let read = 0;
    const n = chars.length;
    while (read < n) {
        const ch = chars[read];
        const start = read;
        while (read < n && chars[read] === ch) {
            read++;
        }
        chars[write] = ch;
        write++;
        const count = read - start;
        if (count > 1) {
            for (const d of String(count)) {
                chars[write] = d;
                write++;
            }
        }
    }
    return write;
};

function compress(chars: string[]): number {
    let write = 0;
    let read = 0;
    const n = chars.length;
    while (read < n) {
        const ch = chars[read];
        const start = read;
        while (read < n && chars[read] === ch) {
            read++;
        }
        chars[write] = ch;
        write++;
        const count = read - start;
        if (count > 1) {
            for (const d of String(count)) {
                chars[write] = d;
                write++;
            }
        }
    }
    return write;
}

载入编辑器，自己跑一遍 →

双指针专题的其他题目

查看双指针全部题目 →