首页 > 试题广场 >

压缩算法

[编程题]压缩算法

热度指数：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

算法知识视频讲解

JavaScript

今天打工了吗

参考top1递归的做法，十分简洁，改用javascript实现，全ac

let line = readline()

function decode(s) {
        let i =0;
        let x = -1, y = -1, z = -1;
        let times = 0;
        let sub = "";
        let decodeStr = "";

        while(i < s.length){
            if(s[i] === '['){
                x = i;
            } else if (s[i] === '|'){
                y = i;
            } else if (s[i] === ']'){
                z = i;
                break;
            }
            i++;
        }
        if(x !== -1 && y !== -1 && z !== -1){
            times = parseInt(s.slice(x + 1, y));
            //console.log("times:", times);

            sub = s.slice(y + 1, z);
            //console.log("sub:", sub);

            decodeStr = s.slice(0, x) + sub.repeat(times) + s.slice(z + 1);
            //console.log("decodeStr:", decodeStr);
            return decode(decodeStr);
        }
        return s;
    }

console.log(decode(line));

编辑于 2020-08-24 11:04:53 回复(0)

JavaScript

准备脱非入欧

//用正则
var  a = readline();
fn(a);
function fn(str) {
            var reg = new RegExp(/\[[^\[\]]*?\]/g);
            var arr = reg.exec(str);
            while (arr != null) {
                let tmp = arr[0];
                let record = arr[0];
                tmp = tmp.split('');
                tmp.pop();
                tmp.shift();
                tmp = tmp.join('')
                tmp = tmp.split('|');
                let temp = tmp[1].repeat(Number(tmp[0]));
                str = str.replace(record, temp);
                var reg = new RegExp(/\[[^\[\]]*?\]/g);
                var arr = reg.exec(str);
                 
            }
            console.log(str)
        }

编辑于 2020-08-20 11:33:11 回复(0)

JavaScript

哈呀~😝

function decode(Ystring){

while(Ystring.lastIndexOf('[')!= -1){
   //找到要替换的整体 
	var repString1 = Ystring.substring(Ystring.lastIndexOf('['),Ystring.indexOf(']',Ystring.lastIndexOf('['))+1);
	var repString = repString1.substring(1,repString1.length-1);
	// 找到括号里的数字
	var i = Number(repString.split('|')[0]);
	//找到要替换的重复字符
	var repString2 = repString.split('|')[1];
	var repString3 = '';
    for(;i>0;i--){
    	console.log(i);
        repString3 +=repString2;
    }
    Ystring = Ystring.replace(repString1,repString3);
   }
    return Ystring;
}

发表于 2020-06-08 20:33:15 回复(0)

JavaScript

火星人再也不用种土豆了

function chongfu(arr) {
    // 将最内层的进行字符串转换
    var  count=0
    var str=''
    var num=arr[1]//得到重复次数
    if (arr[0]=='['){
        for(let j=3;j<arr.length;j++){
            str=str+arr[j]//得到字符串
            count++
        }

    }
    // 定义输出字符串，字符串重复的次数
    var restr=''
    for (var k=0;k<num;k++){
        restr = restr+str
    }
    console.log(restr)
    return restr
}

function jieya(str) {
    //双数组模拟链表，主要思想是像链表一样操作
    var arr=str.split('')//字符串转数组
    var arr2=arr//存储正向
    var arr3=[]//存储反向
    for(let i=arr.length-1;i>=0;i--){
        arr3[arr.length-1-i]=arr[i]
    }
    // 解压最内层后的字符串
    let strResult=''
    let i=0
    let j=0
    while (i<arr.length){
        //正向循环
        if (arr2[i]==='['){
            // 遇到第一个[
            console.log('i是'+i)
            while (j<arr3.length){
                console.log()
                if (arr3[j]===']'){
                    //前面的[对应的]
                    console.log('j是'+j)
                    if (arr2.slice(i+2,arr2.length-j-1).indexOf('[')<0){
                        //判断是不是最内层的[]
                        // 如果是取出来进行字符串转换
                        newarr=arr2.slice(i,arr2.length-j-1)
                        // 转化最内层的+数组后面的未经处理的
                        strResult=strResult+chongfu(newarr)+(arr2.slice(arr2.length-j)).join('')
                        // 内层转化后形成新字符串再进行递归
                        return jieya(strResult)
                    }else {
                        j++
                        break
                    }
                }
                j++
            }
        }
        strResult=strResult+arr2[i]
        i++
    }
    return strResult
}
console.log(jieya('HG[3|B[2|CA]]F'))//HGBCACABCACABCACAF

编辑于 2020-04-22 23:59:09 回复(0)

JavaScript

萌萌萌哒

JavaScript(Node) RegExp + slice 😎

const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    ouput: process.stdout
})
let inArr = []
rl.on('line', line=>{
    if(!line) return
    inArr.push(line.trim())
    if(inArr.length === 1){
        const reg1 = /\[\d+\|[A-Z]*\]/ //[num/(A-Z)*]
        const reg2 = /\|/  // |
        let str = inArr[0] //inArr str
        while(true){
            let res = reg1.exec(str)
            if(!res) {
                break
            }
            let index = res.index
            let before = str.slice(0,index)
            let midIndex = reg2.exec(res[0]).index+index
            let midNum = str.slice(index+1, midIndex)
            let midStr = str.slice(midIndex+1,index+res[0].length-1)
            let after = str.slice(index+res[0].length)
            let mid = ''
            for(let i = 0;i<midNum;i++){
                mid += midStr 
            }
            str= before+mid+after   
        }
        console.log(str)
    }
})

发表于 2020-02-18 12:30:27 回复(1)