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));
}
           

注意：出棧順序是反的，要進行反轉