【数据结构和算法】压缩字符串

其他系列文章导航

Java基础合集
数据结构与算法合集

设计模式合集

多线程合集

分布式合集

ES合集

---

文章目录

其他系列文章导航

文章目录

前言

一、题目描述

二、题解

2.1 方法一：双指针

三、代码

3.1?方法一：双指针

四、复杂度分析

---

前言

这是力扣的443题，难度为中等，解题方案有很多种，本文讲解我认为最奇妙的一种。

---

一、题目描述

题目有点小坑，在下面提到了。

给你一个字符数组?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]?可以是小写英文字母、大写英文字母、数字或符号

注：这个题是要求修改原数组，即在原空间，然后，返回新的长度，在测试机中的是根据我们计算出来的新长度来输出而不是使用chars.length或者char ch:chars之类的控制输出。

---

二、题解

2.1 方法一：双指针

思路与算法：

首先我们要令输入数组 chars 长度为 n。

使用两个指针 i 和 j 分别指向「当前处理到的位置」和「答案待插入的位置」：

1. 当字符一样的时候，i 指针一直往后处理，每次找到字符相同的连续一段 [i,idx)，令长度为 cnt；
2. 将当前字符插入到答案，并让 j 指针后移：chars [j++] = chars [i]；
3. 检查 cnt 的长度是否大于 1，如果大于 1，需要将数字拆分存储。由于简单的实现中，我们只能从个位开始处理 cnt，因此需要使用 start 和 end 记录下存储数字的部分，再处理完 cnt 后，将 [start,end) 部分进行翻转，并更新 j 指针；
4. 最后我们更新 i 为 idx，代表循环处理下一字符。

---

三、代码

3.1?方法一：双指针

Java版本（带注释）：

class Solution {
    public int compress(char[] chars) {
        int len = chars.length;
        int i = 0; //当前处理下标
        int j = 0; //当前被替换下标

        while(i < len) {
            int idx = i;
            //找连续相同字符
            while(idx < len && chars[idx] == chars[i]) idx++; 
            int cnt = idx - i; //连续相同字符长度
            chars[j++] = chars[i];//要替换的下标对准 连续字符串 的第一个下标
            if(cnt > 1) {
                int start = j, end = start;
                //替换cnt
                while(cnt != 0) {
                    chars[end++] = (char)(cnt % 10 + '0');
                    cnt /= 10;
                }
                //由于从个位开始替换, 需要将数字翻转
                reverse(chars, start, end-1);
                //替换完成后, 更新j
                j = end;
            }
            i = idx;//处理完一串, 移动下标
        }
        return j;
    }

    //翻转chars 下标start .. 下标end 之间的字符
    void reverse(char[] chars, int start, int end) {
        while(start < end) {
            char tmp = chars[start];
            chars[start] = chars[end];
            chars[end] = tmp;
            start++;
            end--;
        }
    }
}

C++版本：

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    int compress(vector<char>& cs) {
        int n = cs.size();
        int i = 0, j = 0;
        while (i < n) {
            int idx = i;
            while (idx < n && cs[idx] == cs[i]) idx++;
            int cnt = idx - i;
            cs[j++] = cs[i];
            if (cnt > 1) {
                int start = j, end = start;
                string cnt_str = to_string(cnt);
                for (char c : cnt_str) {
                    cs[end++] = c;
                }
                reverse(cs, start, end - 1);
                j = end;
            }
            i = idx;
        }
        return j;
    }

    void reverse(vector<char>& cs, int start, int end) {
        while (start < end) {
            char t = cs[start];
            cs[start] = cs[end];
            cs[end] = t;
            start++; end--;
        }
    }
};

C++简洁版：?

class Solution {
public:
    int compress(vector<char>& chars) {
        int i=0,j=0,n=chars.size();
        while(i<n){
            int idx=i;
            while(idx<n && chars[idx]==chars[i]) idx++;
            int cnt=idx-i;
            chars[j++]=chars[i];
            if(cnt>1){
                string s=to_string(cnt);
                for(auto c:s) chars[j++]=c;
            }
            i=idx;
        }
        return j;
    }
};

Python版本：

def compress(cs):
    n = len(cs)
    i, j = 0, 0
    while i < n:
        idx = i
        while idx < n and cs[idx] == cs[i]:
            idx += 1
        cnt = idx - i
        cs[j] = cs[i]
        j += 1
        if cnt > 1:
            start = j
            end = start
            cnt_str = str(cnt)
            for c in cnt_str:
                cs[end] = c
                end += 1
            cs[start:end] = cs[start:end][::-1]
            j = end
        i = idx
    return j

---

四、复杂度分析

没有用到除常量以外额外的空间，满足题目的要求！

• 时间复杂度：O(n)
• 空间复杂度：O(1)

---