欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

【算法】解压字符串(猿辅导笔试题)

程序员文章站 2022-04-15 19:12:40
猿辅导APP需要下发一些宣传文本给学生,工程师们使用了一种字符压缩算法,为简单起见,假设被压缩的字符全部为大写字母序列,A,B,C,D…Z,压缩规则如下:1.AAAB可以压缩为A3B (单字符压缩不加括号)2.ABABA可以压缩为(AB)2A (多字符串压缩才加括号)输入数据保证不会出现冗余括号,且表示重复的数字一定合法且大于1,即不会出现:1.(A)2B ------- (应为:A2B)2. ((AB))2C,-----(应为:(AB)2C )3. (A)B ----- (应为:AB...

猿辅导APP需要下发一些宣传文本给学生,工程师们使用了一种字符压缩算法,为简单起见,假设被压缩的字符全部为大写字母序列,A,B,C,D…Z,压缩规则如下:
1.AAAB可以压缩为A3B (单字符压缩不加括号)
2.ABABA可以压缩为(AB)2A (多字符串压缩才加括号)

输入数据保证不会出现冗余括号,且表示重复的数字一定合法且大于1,即不会出现:
1.(A)2B ------- (应为:A2B)
2. ((AB))2C,-----(应为:(AB)2C )
3. (A)B ----- (应为:AB)
4. A1B,(AB)1C,(应为 AB,ABC)

输入描述

第一行是正整数C(C <= 100),表示下面有C组数据。之后C行,每行为一组数据,每组数据为一个字符串。

每个字符串由A-Z,数字0-9和(,)组成表示一个压缩后的串,保证输入数据一定合法且字符串长度小于50。

输出描述

输出C行,每行对应一个数据的输出结果,表示压缩前的字符串,保证每个字符串展开后的长度不超过10^6。

输入示例

5
A11B
(AA)2A
((A2B)2)2G
(YUANFUDAO)2JIAYOU
A2BC4D2

输出示例

AAAAAAAAAAAB
AAAAA
AABAABAABAABG
YUANFUDAOYUANFUDAOJIAYOU
AABCCCCDD

解法思路
对于有数字的位,其操作依赖于紧邻的前项,比较容易想到用栈来解决,针对栈中出现括号和非括号来进行判断分类求解,然后将解压后的字符串重新压入栈中,因为有嵌套的括号情况。
由于题中已说明输入数据均为合法的,不会出现冗余括号,实现上更加简单,但仍需要注意栈的逆序特点。

Java实现
注:这里简化了一下,没有写输入输出语句,实际牛客考试中需要自己写输入和输出。

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

class Solution{

    public String solve(String source){
        StringBuilder sb = new StringBuilder();
        Deque<Character> stack = new ArrayDeque<>();
        for(int i=0;i<source.length();i++){
            char c = source.charAt(i);
            if(c>='0' && c<='9'){
                if(stack.peek() == ')'){
                    stack.pop();
                    List<Character> list = new ArrayList<>();
                    while(stack.peek()!='('){
                        list.add(stack.pop());   // 逆序
                    }
                    stack.pop();
                    for(int j=0;j<c-'0';j++){
                        for(int k=list.size()-1;k>=0;k--){
                            stack.push(list.get(k));
                        }
                    }
                }else{
                    char repeatChar = stack.pop();
                    for(int j=0;j<c-'0';j++){
                        stack.push(repeatChar);
                    }
                }
            }else stack.push(c);
        }
        while(!stack.isEmpty()){
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }
    
	// 以下是测试代码,可忽略
    public static void main(String[] args) {
    	System.out.println(new Solution().solve("A3B2C6"));
    	System.out.println(new Solution().solve("(A3B2)3A"));
        System.out.println(new Solution().solve("((AC)2B2)3D"));
    }
}

本文地址:https://blog.csdn.net/Steven_L_/article/details/107660617