443.压缩字符串
443.1 题目
给你一个字符数组 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 <= 2000chars[i]可以是小写英文字母、大写英文字母、数字或符号
443.2 题解
遍历记录连续重复字符的数量后更新
// 方法一：遍历记录连续重复字符的数量后更新
// 如果数组长度为1，直接返回1，不需要进行压缩。
// 从数组的第二个字符开始遍历。
// 使用指针 currentChar 记录当前字符，count 记录连续重复字符的数量，index 记录更新数组的位置。
// 如果当前字符与前一个字符相同，增加计数。
// 如果当前字符与前一个字符不同，说明出现不同字符，需要将前面的字符和计数信息更新到数组中。
// 如果计数大于1，说明有连续重复字符，将计数转换为字符并更新数组。
// 循环结束后，最后一组连续重复字符无法在循环中检测到不同字符触发更新，因此需要额外处理。
// 将最后一组字符和计数信息更新到数组中。
// 返回 index，即更新后的数组长度。
static int Compress1(char[] chars)
{
// 特判：如果数组长度为1，直接返回1
if (chars.Length == 1)
{
return 1;
}
// 记录当前字符
char currentChar = chars[0];
// 记录连续重复字符的数量
int count = 1;
// 记录更新数组的位置
int index = 0;
// 从数组的第二个字符开始遍历
for (int i = 1; i < chars.Length; i++)
{
// 如果当前字符与前一个字符相同，增加计数
if (chars[i] == currentChar)
{
count++;
}
else
{
// 如果当前字符与前一个字符不同，更新数组
chars[index++] = currentChar;
// 如果计数大于1，说明有连续重复字符，将计数转换为字符并更新数组
if (count > 1)
{
foreach (char digit in count.ToString())
{
chars[index++] = digit;
}
}
// 更新当前字符和计数
currentChar = chars[i];
count = 1;
}
}
// 处理最后一组连续重复字符
// 循环结束后，最后一组连续重复字符无法在循环中检测到不同字符触发更新，因此需要额外处理。
chars[index++] = currentChar;
if (count > 1)
{
foreach (char digit in count.ToString())
{
chars[index++] = digit;
}
}
// 返回更新后的数组长度
return index;
}
双指针遍历数组并直接更新
// 方法二：双指针遍历数组并直接更新
// 使用两个指针 index 和 start 初始化为 0。
// index 用于记录更新数组的位置。
// start 用于记录当前字符的起始位置。
// 使用单循环遍历数组，循环变量为 i，初始值为 1。
// 在每次循环中，判断当前字符是否与前一个字符不同，或者已经遍历到数组末尾。
// 如果是，表示当前连续重复字符结束，需要更新数组。
// 如果不是，继续向后遍历。
// 将当前字符直接放入数组的 index 位置，表示一个新的字符开始。
// 计算连续重复字符的数量 count，即 count = i - start。
// 如果 count 大于 1，将数量转换为字符并依次放入数组。
// 更新 start 为当前循环变量 i，表示开始统计新的连续重复字符。
// 返回 index，即更新后的数组长度。
static int Compress2(char[] chars)
{
// 特判：如果数组长度为1，直接返回1
if (chars.Length == 1)
{
return 1;
}
// 记录更新数组的位置
int index = 0;
// 记录当前字符的起始位置
int start = 0;
// 遍历数组
for (int i = 1; i <= chars.Length; i++)
{
// 如果当前字符与前一个字符不同，或者已经遍历到数组末尾
if (i == chars.Length || chars[i] != chars[i - 1])
{
// 更新数组，将当前字符直接放入数组
chars[index++] = chars[start];
// 计算连续重复字符的数量
int count = i - start;
// 如果数量大于1，将数量转换为字符并放入数组
if (count > 1)
{
foreach (char digit in count.ToString())
{
chars[index++] = digit;
}
}
// 更新当前字符的起始位置
start = i;
}
}
// 返回更新后的数组长度
return index;
}
使用StringBuilder进行压缩
// 方法三：使用StringBuilder进行压缩
// 使用StringBuilder来构建压缩后的字符串，并在最后将其拷贝回原数组
// 直接遍历整个字符数组，对于每个字符，计算其连续出现的次数，然后将字符及其计数追加到StringBuilder中
// 最后将StringBuilder中的内容拷贝回原数组，并返回更新后的数组长度
static int Compress3(char[] chars)
{
// 用于构建压缩后的字符串
StringBuilder stringBuilder = new StringBuilder();
// 遍历字符数组
for (int i = 0; i < chars.Length; i++)
{
// 初始化计数为1，表示当前字符至少出现一次
int count = 1;
// 计算当前字符连续出现的次数
for (int j = i + 1; j < chars.Length; j++)
{
// 如果下一个字符与当前字符相同，增加计数
if (chars[j] == chars[i])
{
count++;
}
else
{
// 如果遇到不同的字符，跳出循环
break;
}
}
// 将当前字符追加到StringBuilder中
stringBuilder.Append(chars[i]);
// 如果计数大于1，将计数转换为字符串并追加到StringBuilder中
if (count > 1)
{
stringBuilder.Append(count);
// 更新索引，跳过已经处理过的重复字符
i += count - 1;
}
}
// 将StringBuilder中的内容拷贝回原数组
for (int i = 0; i < stringBuilder.Length; i++)
{
chars[i] = stringBuilder[i];
}
// 返回更新后的数组长度
return stringBuilder.Length;
}
443.3 代码
using System;
using System.Collections.Generic;
using System.Text;
class Program
{
static void Main()
{
#region 题目
// 给你一个字符数组 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] 可以是小写英文字母、大写英文字母、数字或符号
#endregion
#region 测试
// 示例 1
char[] chars1 = { 'a', 'a', 'b', 'b', 'c', 'c', 'c' };
int result1 = Compress1(chars1);
Console.WriteLine($"示例1 方法1 返回长度：{result1}，修改后数组：[{string.Join(", ", chars1)}]");
// 示例 2
char[] chars2 = { 'a' };
int result2 = Compress1(chars2);
Console.WriteLine($"示例2 方法1 返回长度：{result2}，修改后数组：[{string.Join(", ", chars2)}]");
// 示例 3
char[] chars3 = { 'a', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b' };
int result3 = Compress1(chars3);
Console.WriteLine($"示例3 方法1 返回长度：{result3}，修改后数组：[{string.Join(", ", chars3)}]");
// 示例 1（方法2）
char[] chars1_2 = { 'a', 'a', 'b', 'b', 'c', 'c', 'c' };
int result1_2 = Compress2(chars1_2);
Console.WriteLine($"示例1 方法2 返回长度：{result1_2}，修改后数组：[{string.Join(", ", chars1_2)}]");
// 示例 2（方法2）
char[] chars2_2 = { 'a' };
int result2_2 = Compress2(chars2_2);
Console.WriteLine($"示例2 方法2 返回长度：{result2_2}，修改后数组：[{string.Join(", ", chars2_2)}]");
// 示例 3（方法2）
char[] chars3_2 = { 'a', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b' };
int result3_2 = Compress2(chars3_2);
Console.WriteLine($"示例3 方法2 返回长度：{result3_2}，修改后数组：[{string.Join(", ", chars3_2)}]");
#endregion
}
#region 答案
// 方法一：遍历记录连续重复字符的数量后更新
// 如果数组长度为1，直接返回1，不需要进行压缩。
// 从数组的第二个字符开始遍历。
// 使用指针 currentChar 记录当前字符，count 记录连续重复字符的数量，index 记录更新数组的位置。
// 如果当前字符与前一个字符相同，增加计数。
// 如果当前字符与前一个字符不同，说明出现不同字符，需要将前面的字符和计数信息更新到数组中。
// 如果计数大于1，说明有连续重复字符，将计数转换为字符并更新数组。
// 循环结束后，最后一组连续重复字符无法在循环中检测到不同字符触发更新，因此需要额外处理。
// 将最后一组字符和计数信息更新到数组中。
// 返回 index，即更新后的数组长度。
static int Compress1(char[] chars)
{
// 特判：如果数组长度为1，直接返回1
if (chars.Length == 1)
{
return 1;
}
// 记录当前字符
char currentChar = chars[0];
// 记录连续重复字符的数量
int count = 1;
// 记录更新数组的位置
int index = 0;
// 从数组的第二个字符开始遍历
for (int i = 1; i < chars.Length; i++)
{
// 如果当前字符与前一个字符相同，增加计数
if (chars[i] == currentChar)
{
count++;
}
else
{
// 如果当前字符与前一个字符不同，更新数组
chars[index++] = currentChar;
// 如果计数大于1，说明有连续重复字符，将计数转换为字符并更新数组
if (count > 1)
{
foreach (char digit in count.ToString())
{
chars[index++] = digit;
}
}
// 更新当前字符和计数
currentChar = chars[i];
count = 1;
}
}
// 处理最后一组连续重复字符
// 循环结束后，最后一组连续重复字符无法在循环中检测到不同字符触发更新，因此需要额外处理。
chars[index++] = currentChar;
if (count > 1)
{
foreach (char digit in count.ToString())
{
chars[index++] = digit;
}
}
// 返回更新后的数组长度
return index;
}
// 方法二：双指针遍历数组并直接更新
// 使用两个指针 index 和 start 初始化为 0。
// index 用于记录更新数组的位置。
// start 用于记录当前字符的起始位置。
// 使用单循环遍历数组，循环变量为 i，初始值为 1。
// 在每次循环中，判断当前字符是否与前一个字符不同，或者已经遍历到数组末尾。
// 如果是，表示当前连续重复字符结束，需要更新数组。
// 如果不是，继续向后遍历。
// 将当前字符直接放入数组的 index 位置，表示一个新的字符开始。
// 计算连续重复字符的数量 count，即 count = i - start。
// 如果 count 大于 1，将数量转换为字符并依次放入数组。
// 更新 start 为当前循环变量 i，表示开始统计新的连续重复字符。
// 返回 index，即更新后的数组长度。
static int Compress2(char[] chars)
{
// 特判：如果数组长度为1，直接返回1
if (chars.Length == 1)
{
return 1;
}
// 记录更新数组的位置
int index = 0;
// 记录当前字符的起始位置
int start = 0;
// 遍历数组
for (int i = 1; i <= chars.Length; i++)
{
// 如果当前字符与前一个字符不同，或者已经遍历到数组末尾
if (i == chars.Length || chars[i] != chars[i - 1])
{
// 更新数组，将当前字符直接放入数组
chars[index++] = chars[start];
// 计算连续重复字符的数量
int count = i - start;
// 如果数量大于1，将数量转换为字符并放入数组
if (count > 1)
{
foreach (char digit in count.ToString())
{
chars[index++] = digit;
}
}
// 更新当前字符的起始位置
start = i;
}
}
// 返回更新后的数组长度
return index;
}
// 方法三：使用StringBuilder进行压缩
// 使用StringBuilder来构建压缩后的字符串，并在最后将其拷贝回原数组
// 直接遍历整个字符数组，对于每个字符，计算其连续出现的次数，然后将字符及其计数追加到StringBuilder中
// 最后将StringBuilder中的内容拷贝回原数组，并返回更新后的数组长度
static int Compress3(char[] chars)
{
// 用于构建压缩后的字符串
StringBuilder stringBuilder = new StringBuilder();
// 遍历字符数组
for (int i = 0; i < chars.Length; i++)
{
// 初始化计数为1，表示当前字符至少出现一次
int count = 1;
// 计算当前字符连续出现的次数
for (int j = i + 1; j < chars.Length; j++)
{
// 如果下一个字符与当前字符相同，增加计数
if (chars[j] == chars[i])
{
count++;
}
else
{
// 如果遇到不同的字符，跳出循环
break;
}
}
// 将当前字符追加到StringBuilder中
stringBuilder.Append(chars[i]);
// 如果计数大于1，将计数转换为字符串并追加到StringBuilder中
if (count > 1)
{
stringBuilder.Append(count);
// 更新索引，跳过已经处理过的重复字符
i += count - 1;
}
}
// 将StringBuilder中的内容拷贝回原数组
for (int i = 0; i < stringBuilder.Length; i++)
{
chars[i] = stringBuilder[i];
}
// 返回更新后的数组长度
return stringBuilder.Length;
}
#endregion
}
443.4 运行结果
示例1 方法1 返回长度：6，修改后数组：[a, 2, b, 2, c, 3, c]
示例2 方法1 返回长度：1，修改后数组：[a]
示例3 方法1 返回长度：4，修改后数组：[a, b, 1, 2, b, b, b, b, b, b, b, b, b]
示例1 方法2 返回长度：6，修改后数组：[a, 2, b, 2, c, 3, c]
示例2 方法2 返回长度：1，修改后数组：[a]
示例3 方法2 返回长度：4，修改后数组：[a, b, 1, 2, b, b, b, b, b, b, b, b, b]
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com
