ACM详解（7）——压缩与编码

有些题目会给出一些简单的压缩方法或者编码方法，让你实现具体的算法。下面通过题目分析。

1、Parencodings

Description

Let S = s1 s2...s2n be a well-formed string of parentheses. S can be encoded in two different ways:

By an integer sequence P = p1 p2...pn where pi is the number of left parentheses before the ith right parenthesis in S (P-sequence).

By an integer sequence W = w1 w2...wn where for each right parenthesis, say a in S, we associate an integer which is the number of right parentheses counting from the matched left parenthesis of a up to a. (W-sequence).

Following is an example of the above encodings:

S (((()()())))

P-sequence 4 5 6666

W-sequence 1 1 1456

Write a program to convert P-sequence of a well-formed string to the W-sequence of the same string.

Input

The first line of the input contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case is an integer n (1 <= n <= 20), and the second line is the P-sequence of a well-formed string. It contains n positive integers, separated with blanks, representing the P-sequence.

Output

The output file consists of exactly t lines corresponding to test cases. For each test case, the output line should contain n integers describing the W-sequence of the string corresponding to its given P-sequence.

Sample Input

2

6

4 5 6 6 6 6

9

4 6 6 6 6 8 9 9 9

Sample Output

1 1 1 4 5 6

1 1 2 4 5 1 1 3 9

翻译：S = s1 s2...s2n是结构正确的（有左括号和右括号组成，并且数量相等，并且对应关系正确）小括号序列，他可以使用两种方式编码：

正整数序列P = p1 p2...pn，pi表示第i个右括号之前的左括号的数量（P序列）；

正整数序列W = w1 w2...wn，wi表示第i个右括号对应的左括号的位置（从右向左数，1,2,3）（w序列）。

题目要求根据p序列求出w序列。

解题思路：

对于p序列中的每个元素pi：

循环判断之前的左括号，对于遇到的每个左括号：

判断是否已经与其他右括号配对，如果已经配对，继续向左判断；

如果没有，则记录它是第几个左括号。

以4 5 6 6 6 6为例分析，首先创建数组a表示左括号，1表示没有配对的左括号，0表示已经配对的左括号。初始情况a的值为1 1 1 1 1 1

读取p序列中的信息

P1=4 从a[3]开始判断左括号，a[3]=1，所以与a[3]括号对应，所以w1=1，a的值1 1 1 0 1 1

P2=5 从a[4]开始判断左括号，a[4]=1，所以与a[4]括号对应，所以w2=1，a的值1 1 1 0 0 1

P3=6 从a[5]开始判断左括号，a[5]=1，所以与a[5]括号对应，所以w3=1，a的值1 1 1 0 0 0

P4=6 从a[5]开始判断左括号，a[5]=0，a[4]=0,a[3]=0,a[2]=1,所以与a[2]括号对应，所以w4=4，a的值1 1 0 0 0 0

同理得到w5=5 w6=6

最后的w序列为：111456

参考代码略。

2、Encoding

描述

Given a string containing only 'A' - 'Z', we could encode it using the following method:

1. Each sub-string containing k same characters should be encoded to "kX" where "X" is the only character in this sub-string.

2. If the length of the sub-string is 1, '1' should be ignored.

输入

The first line contains an integer N (1 <= N <= 100) which indicates the number of test cases. The next N lines contain N strings. Each string consists of only 'A' - 'Z' and the length is less than 10000.

输出

For each test case, output the encoded string in a line

样例输入

2

ABC

ABBCCC

样例输出

ABC

A2B3C

翻译：把字符串中出现的连续相同的多个字符使用该字符以及出现的次数表示，例如ABBCCC中的BB可以使用2B表示，可以使用3C表示。题目要求对给定的字符串编码。

解题思路：遍历字符串，取出每个字符与之前的字符进行比较，如果相等计数加1，不相同，则从新计数。例如ABBCCC，可以处理如下。

先初始化，c表示前一个字符，count表示统计次数。c=’0’,count=0。

对于A，之前没有字符，count=1，c=’A’;

对于B，之前的字符是’A’，输出A，count=1，c=’A’；

对于B，之前的字符是’B’，count=2；

对于C，之前的字符是’B’，输出2B，count=1，c=’C’;

对于C，之前的字符是’C’，count=2;

对于C，之前的字符是’C’，count=3;

最后输出3C。

输出的结果是A2B3C

参考代码如下：

/*

* 字符串编码

*/

public static void test5(String str){

int count=1;

char c=str.charAt(0);

for(int i=1;i<str.length();i++){

if(str.charAt(i)==c){

count++;

}else{

if(count!=1)

System.out.print(count);

System.out.print(c);

count=1;

c=str.charAt(i);

}

}

if(count!=1)

System.out.print(count);

System.out.print(c);

}

李绪成 CSDN Blog：http://blog.csdn.net/javaeeteacher
CSDN学生大本营：http://student.csdn.net/space.php?uid=124362