2020校招8.17日腾讯技术笔试题1

题目：

给你一个压缩字符串，让你进行解压缩，例如ABCABCABC会被压缩成[3|ABC]

输入：

压缩字符串（[2|A[2|BC]]）

输出：

解压后的字符串（ABCBCABCBC）

方法：用栈来存

思路：见到括号这些的题都应该用栈，让其一直入栈，直到‘]’有括号进栈，则让其中元素依次出栈，直到第一个‘[’左括号出栈，然后进行解压缩，解压之后继续将字符串按顺序存入栈中，然后继续此操作

代码：

public static String jieYa(String str){
    if(str==null) return "";
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i <str.length() ; i++) {
        if(str.charAt(i)==']'){//如果是右括号，则开始解压缩
            StringBuilder sb = new StringBuilder();
            while(stack.peek()!='['){//出栈直到出现左括号
                sb.append(stack.pop());
            }
            stack.pop();
            String string=sb.reverse().toString();//翻转
            int count=0;
            sb = new StringBuilder();
            for (int j = 0; j <string.length() ; j++) {//解析字符串中数字和字符串
                if(string.charAt(j)<='9'&&string.charAt(j)>='0'){
                    count=(int)(string.charAt(j)-'0');
                }
                if(string.charAt(j)<='Z'&&string.charAt(j)>='A'){
                    sb.append(string.charAt(j));
                }
            }
            string=sb.toString();
            while(count!=1){//进行解压缩
                count--;
                sb.append(string);
            }
            string=sb.toString();
            for (int j = 0; j <string.length() ; j++) {//然后将解压缩之后的字符串压进栈
                stack.push(string.charAt(j));
            }
        }else{//如果不是右括号就放入栈中
            stack.push(str.charAt(i));
        }
    }
    StringBuilder res = new StringBuilder();
    while(!stack.isEmpty()){//将最后解压缩后的答案从栈出来
        res.append(stack.pop());
    }
    return res.reverse().toString();
}

public static void main(String[] args) {
    String str="[2|B[2|ABC]]";
    System.out.println(jieYa(str));
}
           

注意：出栈顺序是反的，要进行反转