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

2023-12-13 12:32:59

其他系列文章导航

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)

文章来源:https://blog.csdn.net/kologin/article/details/134965110
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。