【算法】解压字符串(猿辅导笔试题)
猿辅导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
上一篇: 生鲜水果做电商面临着哪些困境?
下一篇: 浅谈母婴电商的发展与未来