[LeetCode] 443. String Compression

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 array chars. 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 数组中会被拆分为多个字符。
请在修改完输入数组后，返回该数组的新长度。
你必须设计并实现一个只使用常量额外空间的算法来解决此问题。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/string-compression
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

题意是给一个字符串，请按规则压缩。压缩的结果还是存在 char array 中但是最后输出的是新的 char array 的长度。
基本逻辑是要求你把连续出现多个的字母转化成字母 + 出现次数的组合。要求是不使用额外空间。这个题算是模拟，我这里解释一下我的思路吧。做一个 while 循环和一个指针，首先确保指针不能跳出 while 循环，条件自然是指针指向的 index 不能大于 input 字符串的长度。在遍历 input 的时候，如果遇到一个新的字母 c，先记下这个字母，然后往后遍历看看这个字母是否有连续出现，若有，则需要记录连续出现的次数 count。当连续出现的字符停止之后，此时可以试着将已经遍历过的部分写入 res，因为你有了 c 和他的 count，所以就可以写入 res 了。注意需要将 count 先转化成 String.valueOf 然后再转化成 charArray，才能将比如12转化成”1”, “2”这样的形式。根据题意，只要 count 不等于 1，那么这个数字（字母的出现次数）就一定要被写入最后的 char array。

复杂度

时间O(n)
空间O(1) - 题目要求

代码

Java实现

class Solution {
	public int compress(char[] chars) {
		int res = 0;
		int index = 0;
		while (index < chars.length) {
			char cur = chars[index];
			int count = 0;
			while (index < chars.length && chars[index] == cur) {
				index++;
				count++;
			}
			// write the letter
			chars[res++] = cur;
			// write the occurance
			// 如果某个字母的出现次数是不是1，就需要这样处理，因为一定要填一个数字
			if (count != 1) {
				for (char c : String.valueOf(count).toCharArray()) {
					chars[res++] = c;
				}
			}
		}
		return res;
	}
}

[LeetCode] 443. String Compression

思路

复杂度

代码

相关题目