算法随笔_9:压缩字符串

上一篇: 算法随笔_8: 寻找重复数-CSDN博客

题目描述如下:

给你一个字符数组 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" 替代。

算法思路:

这道题的难点还是在于只能使用常量空间。如果不考虑这点的话，我们可以额外开辟一块儿数组空间m2。使用双指针解决此问题。

1. 算法一开始，两个指针p1，p2分别指向两个数组的起始点。还需要一个存储数量的变量cnt初始值为1。

2. 指针p1从原始数组m1起始处开始迭代，先把第一个字符放入数组m2的第一个位置。

3. p1右移一格。如果p1所指的元素和p2所指的元素相同，变量cnt加1，重复此步骤，直到p1所指的元素和p2所指的元素不相同或到数组末尾，去到步骤4。

4. 如果cnt大于1，通过移动指针p2，把cnt的值按位数依次放入数组m2。cnt重置为1。再移动p2一格，把p1所指元素放入m2。重复步骤3。

5. 当指针p1到达数组m1末尾时，算法结束。

================================

那如果是只使用常量额外空间，如何做呢？

其实，上面的算法是完全不需要开辟新的数组空间的。整个算法和上面是一样的。数组m2的空间，我们直接使用m1即可。此时可能有人会问，这样做的话，难道不担心会覆盖数组m1的原值吗？先说结论，不会的。

我们仔细想一下，当p1指针向右移动时，它所走过的格子已经是废弃了的，p1只负责了检查是否相同和统计重复数，这两个值，在访问过后都已经被记录，所以访问过的格子已经废弃。重复数记录在cnt里，不同的值记录在当前p1所指的格子里。

把上面的算法重新整理一下:

1. 算法一开始，两个指针p1，p2都指向数组的起始点。还需要一个存储数量的变量cnt初始值为1。

2. 指针p1从数组m1起始处开始迭代。

3. p1右移一格，p2不动。如果p1所指的元素和p2所指的元素相同，变量cnt加1，重复此步骤，直到p1所指的元素和p2所指的元素不相同或到数组末尾，去到步骤4。

4. 如果cnt大于1，通过不断移动指针p2，把cnt的值按位数依次放入p2所指的格子中。cnt重置为1。再移动p2一格，把p1所指元素放入p2所指的格子中。重复步骤3。

5. 当指针p1到达数组m1末尾时，算法结束，此时p2所指元素的前面的部分，数一下元素个数即是答案。

原文地址：https://blog.csdn.net/m0_70494097/article/details/145201687

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！