今天刷到了一題騰訊的算法真題构蹬，覺(jué)得比較有趣王暗，所以在這里和大家分享一下。本題的鏈接是：壓縮算法
題目
小Q想要給他的朋友發(fā)送一個(gè)神秘字符串庄敛，但是他發(fā)現(xiàn)字符串的過(guò)于長(zhǎng)了俗壹，于是小Q發(fā)明了一種壓縮算法對(duì)字符串中重復(fù)的部分進(jìn)行了壓縮，對(duì)于字符串中連續(xù)的m個(gè)相同字符串S將會(huì)壓縮為[m|S](m為一個(gè)整數(shù)且1<=m<=100)藻烤，例如字符串ABCABCABC將會(huì)被壓縮為[3|ABC]策肝，現(xiàn)在小Q的同學(xué)收到了小Q發(fā)送過(guò)來(lái)的字符串，你能幫助他進(jìn)行解壓縮么隐绵？
輸入
輸入第一行包含一個(gè)字符串s，代表壓縮后的字符串拙毫。
S的長(zhǎng)度<=1000;
S僅包含大寫(xiě)字母依许、[、]缀蹄、|;
解壓后的字符串長(zhǎng)度不超過(guò)100000;
壓縮遞歸層數(shù)不超過(guò)10層;
輸出
輸出一個(gè)字符串峭跳，代表解壓后的字符串。
輸入例子
HG[3|B[2|CA]]F
輸出例子
HGBCACABCACABCACAF
例子說(shuō)明
HG[3|B[2|CA]]F?>HG[3|BCACA]F?>HGBCACABCACABCACAF
題目分析
這題是一個(gè)字符串操作類型的題目缺前，問(wèn)題的難點(diǎn)在于中括號(hào)的范圍不確定蛀醉，中括號(hào)也能放其他的中括號(hào)，所以我們要從最里面的中括號(hào)開(kāi)始衅码，一層一層剝開(kāi)拯刁，舉例說(shuō)明：上面的例子[3|B[2|CA]]，我們很難將[3|*]直接展開(kāi)逝段，這樣會(huì)導(dǎo)致有更多的中括號(hào)[B[2|CA]B[2|CA]B[2|CA]]垛玻，從而使問(wèn)題更加復(fù)雜，就像例子說(shuō)明1里面講到的奶躯，要先從[2|CA]開(kāi)始展開(kāi)帚桩，這樣才能使得中括號(hào)個(gè)數(shù)越來(lái)越少?gòu)亩鉀Q問(wèn)題。
解題思路
思路是在遍歷字符串的過(guò)程中嘹黔，利用一個(gè)堆棧账嚎，存儲(chǔ)"["和"|"的位置，當(dāng)遇到"]"時(shí)，他必定與堆棧最上面的"["和"|"匹配郭蕉，可以將他們出棧疼邀，然后用到"["和"]"中間的值去替換待返回的字符串
代碼
public static void main(String args[]){
// 用戶輸入
Scanner scanner = new Scanner(System.in);
String s = scanner.next();
// 用StringBuilder存儲(chǔ)結(jié)果，一般字符串的拼接都用它恳不，而不是String
StringBuilder result = new StringBuilder();
// 用堆棧存儲(chǔ)[和|的下標(biāo)
Stack<Integer> stack = new Stack<>();
int right = 0;
for(char ch:s.toCharArray()){
result.append(ch);
if(ch == '[' || ch == '|')
stack.push(right);
// 當(dāng)前的字符是]檩小，就可以將堆棧里面的[和|彈出來(lái)了
if(ch == ']'){
if(stack.size() >= 2){
int shuhao = stack.pop();
int zuokuohao = stack.pop();
// 將[geshu|st]轉(zhuǎn)變成字符串的形式
String st = result.substring(shuhao+1, right);
int geshu = Integer.parseInt(result.substring(zuokuohao+1,shuhao));
StringBuilder dangqian = new StringBuilder();
while(geshu-->0){
dangqian.append(st);
}
// 將轉(zhuǎn)換后的字符串變?yōu)榻Y(jié)果的一部分
result.replace(zuokuohao,right+1,dangqian.toString());
// right下標(biāo)指向當(dāng)前result的最后一個(gè)字符
right = zuokuohao + dangqian.length() - 1;
}else{
System.out.println("您的輸入錯(cuò)誤！Ｑ萄规求！");
}
}
right++;
}
if(!stack.isEmpty())
System.out.println("不是對(duì)的哦！Ｂ训搿阻肿！");
System.out.println(result.toString());
}
