解压字符串_猿辅导笔试题

猿辅导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）

注意：数字可能出现多位数即A11B或者(AB)10C或者A02这种情况。

A11B = AAAAAAAAAAAB

(AB)10C = ABABABABABABABABABABC

A02 = AA

数据分布：

对于60%的数据，括号不会出现嵌套，即不会有 ((AB)2C)2这种结构。

对于80%的数据，括号最多只嵌套一层，即不会有 (((AB)2C)2D)99 这种结构。

对于100%的数据，括号可以嵌套任意层。

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

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

import java.util.*; public class Main { private static int idx; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); sc.nextLine(); List<String> input = new ArrayList<>(); while(sc.hasNextLine()) { input.add(sc.nextLine()); } for (int i = 0; i < input.size(); i++) { idx = 0; String res = helper(input.get(i)); System.out.println(res); } } private static String helper(String str) { StringBuilder sb = new StringBuilder(); int len = str.length(); if (len == 0) return ""; char[] array = str.toCharArray(); while (idx < len) { if (array[idx] >= '0' && array[idx] <= '9') { int num = 0; while (idx < len && array[idx] >= '0' && array[idx] <= '9') { num = num*10 + array[idx++]-'0'; } char prev = sb.charAt(sb.length()-1); for (int j = 0; j < num-1; j++) { sb.append(prev); } } else if (array[idx] == '(') { idx++; sb.append(helper(str)); } else if (array[idx] == ')') { idx++; int num = 0; while (idx < len && array[idx] >= '0' && array[idx] <= '9') { num = num*10 + array[idx++]-'0'; } String cpy = sb.toString(); for (int i=0; i < num-1; i++) { sb.append(cpy); } return sb.toString(); } else { sb.append(array[idx]); idx++; } } return sb.toString(); } }

解压字符串

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题