443. 压缩字符串

🟠   🔖  双指针 字符串  🔗 力扣 LeetCode

题目

Given an array of characters chars, compress it using the following algorithm:

Begin with an empty string s. For each group of consecutive repeating characters in chars:

• If the group's length is 1, append the character to s.
• Otherwise, append the character followed by the group's length.

The compressed string s should not be returned separately , but instead, be stored in the input character arraychars. Note that group lengths that are 10 or longer will be split into multiple characters in chars.

After you are done modifying the input array, return the new length of the array.

You must write an algorithm that uses only constant extra space.

Example 1:

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

Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]

Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".

Example 2:

Input: chars = ["a"]

Output: Return 1, and the first character of the input array should be: ["a"]

Explanation: The only group is "a", which remains uncompressed since it's a single character.

Example 3:

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

Output: Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].

Explanation: The groups are "a" and "bbbbbbbbbbbb". This compresses to "ab12".

Constraints:

• 1 <= chars.length <= 2000
• chars[i] is a lowercase English letter, uppercase English letter, digit, or symbol.

题目大意

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

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

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

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

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

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

示例 1：

输入： chars = ["a","a","b","b","c","c","c"]

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

解释： "aa" 被 "a2" 替代。"bb" 被 "b2" 替代。"ccc" 被 "c3" 替代。

示例 2：

输入： chars = ["a"]

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

解释： 唯一的组是“a”，它保持未压缩，因为它是一个字符。

示例 3：

输入： chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]

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

解释： 由于字符 "a" 不重复，所以不会被压缩。"bbbbbbbbbbbb" 被 “b12” 替代。

提示：

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

解题思路

1. 初始化变量：

   • 使用 curChar 来跟踪当前字符，count 来记录当前字符的重复次数，idx 来记录写入压缩字符的位置。

2. 定义修改函数：

   • 定义 modifyChars 函数，将当前字符和它的计数写入到 chars 中。

3. 遍历数组：

   • 遍历 chars 数组，对于每个字符：
     • 如果与 curChar 相同，增加 count。
     • 如果不同，调用 modifyChars，更新 curChar 和 count。

4. 处理最后一组字符：

   • 遍历结束后，再次调用 modifyChars 处理最后一组字符。

5. 返回结果：

   • 返回 idx，表示新的长度。

复杂度分析

• 时间复杂度：O(n)，遍历一次字符数组。
• 空间复杂度：O(1)，只使用常量额外空间。

代码

/**
 * @param {character[]} chars
 * @return {number}
 */
var compress = function (chars) {
	let curChar = chars[0],
		count = 0, // // 用于记录字符重复的次数
		idx = 0; // 用于记录写入压缩字符的位置
	const modifyChars = () => {
		// 写入字符
		chars[idx++] = curChar;

		// 如果出现次数大于 1，写入次数
		if (count > 1) {
			for (let num of String(count)) {
				chars[idx++] = num;
			}
		}
	};

	for (let i = 0; i < chars.length; i++) {
		let char = chars[i];
		if (char == curChar) {
			// 计数连续重复字符
			count++;
		} else {
			modifyChars();
			curChar = char;
			count = 1;
		}
	}
	modifyChars(); // 处理最后一组字符
	return idx; // 返回新数组的长度
};

相关题目

题号	标题	题解	标签	难度
38	外观数列	[✓]	字符串
271	字符串的编码与解码 🔒		设计 数组 字符串
604	迭代压缩字符串 🔒		设计 数组 字符串 1+
1313	解压缩编码列表		数组
3163	压缩字符串 III	[✓]	字符串
3167	字符串的更好压缩 🔒		哈希表 字符串 计数 1+