首页 > 试题广场 >

压缩算法

[编程题]压缩算法

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

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

输入描述:

输入第一行包含一个字符串s，代表压缩后的字符串。
S的长度<=1000;
S仅包含大写字母、[、]、|;
解压后的字符串长度不超过100000;
压缩递归层数不超过10层;

输出描述:

输出一个字符串，代表解压后的字符串。

示例1

输入

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

输出

HGBCACABCACABCACAF

说明

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

算法知识视频讲解

Java

kevin_Wang333

import java.util.*;
public class Main{
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        String str = scan.next();
            while(str.contains("]")) {
                int right = str.indexOf("]");
                int left = str.lastIndexOf("[",right);
                String tmp = str.substring(left+1,right); // 2|CA
                String[] splits = tmp.split("\\|");
                int n = Integer.parseInt(splits[0]);
                String str2 = ""; 
                for(int i = 0; i < n;i++) {
                    str2 += splits[1];
                }
                str  = str.replace("[" + tmp + "]", str2);//HG[3|BCACA]F]

            }
            System.out.println(str);
        }
}

编辑于 2020-08-20 14:53:57 回复(1)

Java

℡_KissShotナ



public static StringBuffer decode(StringBuffer s){ 
    for(int r=0;r<s.length();r++)
    {          char c=s.charAt(r); 
                    //找到第一个右括号    
                        if(c == ']'){ 
                           //开始第一次解密    
             int k=0;//记录'|’的位置  
                          //l是从右往左对应‘]’的‘[’    
             int l=r;
                         for(;s.charAt(l) !='[';l--){
                 if(s.charAt(l)=='|'){
                    k=l;
                    }
                }
            int num=Integer.parseInt(String.valueOf(s.charAt(l+1)));
            String s1=s.substring(k+1,r);
            String s2 = ""; for(int i=0;i<num;i++){
                s2+=s1;
            }
            s=s.replace(l,r+1,s2);//替换一对大括号的数据
            r=l+s2.length()-1;//将r移到被改变数据的末尾，如caca的最后一个a上
        }
    } return s;
}



思路来源于https://www.cnblogs.com/eisuto/p/12464469.html#commentform

编辑于 2020-07-01 17:52:36 回复(0)

Java

Lloris

import java.util.Scanner;
import java.util.Stack;
//有没有大佬解答下，在eclipes中能通过，但在牛客网说我只通过了百分之40，确实找不出原因
//有没有大佬能提几个测试例子，让我测试一下
public class Main {
	public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String next = scanner.next();
        scanner.close();
        System.out.println(decode(next));
    }
  
    public static String decode(String words){
        Stack<String> elem = new Stack<>();
        int flag = 0;
        while(flag < words.length()) {
            //将压缩的字符串压入栈中
            String to_stack = "";
            while(words.charAt(flag)!=']' && words.charAt(flag)!='[' && words.charAt(flag)!='|') {
                to_stack = to_stack +words.charAt(flag);
                flag++;
                if(flag>=words.length()) {
                    flag--;
                    break;
                }
            }
            if(to_stack.length()>0) {
                elem.add(to_stack);
            }
            if(words.charAt(flag) == '[' || words.charAt(flag) == '|') {
                elem.add(words.charAt(flag)+"");
            }
            if(words.charAt(flag) == ']' && elem.size()>0) {
                String s1 = elem.pop();
                elem.pop();
                int mul = Integer.parseInt(elem.pop());
                elem.pop();
                to_stack = elem.size()>0?elem.pop():"";
                for(int i=0;i<mul;i++) {
                    to_stack = to_stack+s1;
                }
                elem.add(to_stack);
            }
                flag++;
        }
        
        words ="";
        for (String x : elem) {
            words =words+x;
    }
        return words;
    }

}

编辑于 2020-05-19 18:04:48 回复(0)

Java

盐橘橙

import java.util.Scanner;
import java.util.Stack;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String encodeString = sc.nextLine();
        System.out.println(myDecode(encodeString));
    }
    
    public static String myDecode(String words){
        Stack<Integer> num_stack = new Stack<>();
        Stack<StringBuilder> str_stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < words.length(); ++i){
            if(words.charAt(i) == '['){
                int pos = words.indexOf("|", i);
                int count = Integer.valueOf(words.substring(i + 1, pos));
                num_stack.push(count);
                str_stack.push(sb);
                i = pos;
                sb = new StringBuilder();
            }else if(words.charAt(i) == ']'){
                int count = num_stack.pop();
                StringBuilder tmp = str_stack.pop();
                for(int j = 0; j < count; ++j){
                    tmp.append(sb);
                }
                sb = tmp;
            }else{
                sb.append(words.charAt(i));
            }
        }
        return sb.toString();
    }
}

发表于 2020-04-25 16:13:01 回复(0)

Java

牛客109817399号

import java.util.Scanner;

public class Main{

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

String s = sc.nextLine();

        while(s.indexOf("|")>-1){
      int a=s.lastIndexOf("[");
    int b=s.indexOf("]");
    s=s.substring(0,a)+rep1(s.substring(a+1,b))+s.substring(b+1,s.length());
}
   System.out.println(s);

}

    public static String rep1(String s){
      String result="";
      int a=s.indexOf("|");
      String b = s.substring(a+1,s.length());
      int c = Integer.parseInt(s.substring(0,a));
      for(int i=0;i<c;i++){
           result=result+b;
      }
      return result;
     }

}

发表于 2020-03-09 17:13:55 回复(0)