443.压缩字符串

LeetCode LeetCode 双指针 字符串
发布时间 :
字数:4.1k 阅读 : 评论:
  1. 443.压缩字符串
    1. 443.1 题目
    2. 443.2 题解
      1. 遍历记录连续重复字符的数量后更新
      2. 双指针遍历数组并直接更新
      3. 使用StringBuilder进行压缩
    3. 443.3 代码
    4. 443.4 运行结果

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 <= 2000
  • chars[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

赏

©2016-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏