首页 > 试题广场 >

压缩算法

[编程题]压缩算法

热度指数：5843 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小Q想要给他的朋友发送一个神秘字符串，但是他发现字符串的过于长了，于是小Q发明了一种压缩算法对字符串中重复的部分进行了压缩，对于字符串中连续的m个相同字符串S将会压缩为[m|S](m为一个整数且1<=m<=100)，例如字符串ABCABCABC将会被压缩为[3|ABC]，现在小Q的同学收到了小Q发送过来的字符串，你能帮助他进行解压缩么？

示例1

输入

"HG[3|B[2|CA]]F"

输出

"HGBCACABCACABCACAF"

说明

HG[3|B[2|CA]]F−>HG[3|BCACA]F−>HGBCACABCACABCACAF

备注:

S的长度<=1000;
S仅包含大写字母、[、]、|;
解压后的字符串长度不超过100000;
压缩递归层数不超过10层;

算法知识视频讲解

Java

莫茗丶

//java 25ms
import java.util.*;


public class Solution {

    public String compress(String str) {

        char[] chars=str.toCharArray();
        return helper(chars,0,chars.length-1);
    }

    private String helper(char[] chars, int i, int j) {
        StringBuilder sb = new StringBuilder();
        while (i<=j){
            if(chars[i]!='['){
                sb.append(chars[i]);
                i++;
            }else if(chars[i]=='['){
                i++;
               //数字
                int tmp=i+1;
                int n=chars[i]-'0';
                while (chars[i]!='|'){
                    i++;
                }
                for (int k =tmp ; k < i; k++) {
                    n=n*10+chars[k]-'0';
                }
                //寻找匹配的窗口
                int p=i+1;
                int cnt=1;
                while (p<=j&&cnt!=0){
                    if(chars[p]=='['){
                        cnt++;
                    }else if(chars[p]==']'){
                        cnt--;
                    }
                    p++;
                }
                //递归
                String s=helper(chars,i+1,p-2);
               //添加【】内的字符串
                for (int k = 0; k < n; k++) {
                    sb.append(s);
                }
                i=p;
            }
        }
        return sb.toString();
    }
}

编辑于 2022-10-05 19:48:45 回复(0)

Java

万古霉素

巧用Java集合，细心递归

题目不难，直接用递归就可以。巧妙使用Java的StringBuilder和List，在这里我用List封装了两个返回值：第一个返回的是匹配的串，第二个是匹配完之后的坐标。

public class Solution {
    int len = 0;
    public String compress (String str) {
        len = str.length();
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < len; i++) {
            if(str.charAt(i) == '['){
                // 调用解析函数，返回一个列表，列表第一个是匹配到的串
                // 第二个是匹配玩后下一个坐标值
                List next = solver(str, i+1);
                sb.append(next.get(0));
                i = (Integer)next.get(1);
            } else sb.append(str.charAt(i));
        }
        return sb.toString();
    }
    
    public List solver(String str, int idx) {
        // 列表第一个返回匹配到的字符串，第二个返回最后的索引
        List ans = new ArrayList();
        StringBuilder sb = new StringBuilder();
        // 先得到数字m
        int l = idx, r = idx;
        while(r < len && str.charAt(r) != '|') {
            r++;
        }
        int m = Integer.parseInt(str.substring(l, r));
        // 递归解析后面的部分
        if(r++ < len) {
            for(int i = r;i < len;i++) {
                if(str.charAt(i) == '[') {
                    // 碰到'['就开始解析，并设置i的值
                    List next = solver(str,i+1);
                    sb.append(next.get(0));
                    i = (Integer)next.get(1);
                } else if(str.charAt(i) == ']') {// 找到右边边界，结束
                    r = i;
                    break;
                } else sb.append(str.charAt(i));// 正常字符，直接添加
            }
        }
        // 添加m串字串
        String tmp = sb.toString();
        for(int i = 0;i < m-1;i++) {
            sb.append(tmp);
        }
        // 封装结果返回
        ans.add(sb.toString());
        ans.add(r);
        return ans;
    }
}

编辑于 2021-08-23 10:04:38 回复(0)