UVa 245 Uncompress

题目分析本题要求实现一个解压缩程序根据给定的压缩文件恢复原始文件。压缩规则如下原始文件中包含单词连续的字母序列和非字母字符。对于第一次出现的单词直接输出该单词并将其放入一个列表中放在列表最前面。对于后续出现的单词不输出单词本身而是输出该单词在列表中的位置从1 11开始编号然后将该单词移动到列表最前面。非字母字符如标点符号、空格、换行等直接原样输出不进行压缩处理。输入以单独一行的一个数字0 00表示结束该0 00不参与输出。需要注意的是本题解压缩的输入文件实际上是一个压缩后的文件其中包含了数字表示单词在列表中的位置和原始的非字母字符。我们需要根据这些数字和保留的单词信息还原出原始的未压缩文本。例如在样例输入中Dear Sally, Please, please do it- - 1 would 4 Mary very, 1 much. And 4 6 8 everything in 5s power to make 14 pay off for you. Thank 2 18 18- - 0我们需要正确解析其中的数字将其替换为对应的单词并更新单词列表的顺序。解题思路核心数据结构由于单词需要频繁进行“移动到列表最前面”的操作并且需要根据位置快速访问单词我们可以选择list \texttt{list}list双向链表作为存储单词列表的数据结构。list \texttt{list}list支持O ( 1 ) O(1)O(1)时间在头部插入元素也支持在任意位置删除元素通过迭代器非常适合本题的需求。算法步骤初始化一个空的liststring words \texttt{liststring words}liststring words用于存储已经出现过的单词最新出现的单词放在链表头部。逐行读入输入直到遇到单独的一行0为止。对于每一行文本逐个字符处理如果当前字符是数字连续读取数字字符组成一个完整的数字字符串。将该数字转换为整数n nn。从words \texttt{words}words链表中找到第n nn个单词注意位置从1 11开始。将该单词输出到结果中。从链表中删除该单词。将该单词插入到链表的最前面因为单词被再次使用需要移动到列表头部。如果当前字符是字母连续读取字母字符组成一个完整的单词。将该单词输出到结果中。将该单词插入到链表的最前面因为是第一次出现或者即使之前出现过但根据规则这里实际上也是第一次出现的情况因为压缩文件中如果是重复出现的单词会用数字代替不会出现字母序列。注意根据压缩规则输入中的单词都是第一次出现的情况因为在压缩过程中只有第一次出现的单词才会被原样保留重复的单词已经被替换为数字。所以这里我们不需要检查单词是否已经存在于链表中直接插入即可。如果当前字符既不是数字也不是字母直接将该字符输出到结果中。每处理完一行输出一个换行符。关键细节单词的定义单词是连续的字母序列大小写敏感abc和Abc被视为不同的单词。因此我们直接使用字符串比较即可不需要额外处理大小写。数字的解析数字可能不止一位需要连续读取。例如样例中的18是一个完整的数字表示列表中的第18 1818个单词。边界情况当数字对应的单词被取出后原位置被删除链表的长度减1 11。然后将该单词插入头部链表长度又恢复为原长度。列表中的单词顺序会随着每次“使用”而动态变化。输入终止遇到单独一行的0时停止处理0本身不输出。复杂度分析设原始文件中的单词总数为N NN输入文件中的字符总数为M MM。每个单词插入头部是O ( 1 ) O(1)O(1)时间根据位置查找单词需要O ( N ) O(N)O(N)时间因为list \texttt{list}list不支持随机访问需要通过迭代器移动。最坏情况下总时间复杂度为O ( N × M ) O(N \times M)O(N×M)但由于本题没有给出明确的上限且数据规模通常较小该做法可以通过。如果需要优化可以使用vector \texttt{vector}vector配合哈希表记录位置但list \texttt{list}list的实现简洁且满足题目要求。代码实现// Uncompress// UVa ID: 245// Verdict: Accepted// Submission Date: 2016-05-12// UVa Run Time: 0.060s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.sync_with_stdio(false);string line;liststringwords;// 存储单词列表头部为最近使用的单词// 逐行读入直到遇到单独的 0while(getline(cin,line),line!0){// 遍历当前行的每一个字符for(inti0;iline.length();i){// 情况1遇到数字表示要解压缩为一个之前出现过的单词if(isdigit(line[i])){string number;numberline[i];// 读取第一个数字字符// 继续读取连续的数字字符while(iline.length()isdigit(line[i]))numberline[i];// 将数字字符串转换为整数得到单词在列表中的位置从1开始autoitwords.begin();advance(it,stoi(number)-1);// 移动到第 number 个单词// 取出该单词string word*it;words.erase(it);// 从原位置删除// 输出该单词解压缩结果coutword;// 将该单词移动到列表头部words.insert(words.begin(),word);i--;// 因为外层循环会自增这里回退一位}// 情况2遇到字母表示这是一个第一次出现的单词elseif(isalpha(line[i])){string word;wordline[i];// 读取第一个字母字符// 继续读取连续的字母字符while(iline.length()isalpha(line[i]))wordline[i];// 将单词插入列表头部表示最近使用words.insert(words.begin(),word);// 直接输出该单词coutword;i--;// 回退一位}// 情况3其他字符标点、空格等直接原样输出elsecoutline[i];}// 每行处理完毕输出换行符cout\n;}return0;}总结本题通过模拟压缩过程中的单词列表维护来实现解压缩核心在于正确识别输入中的数字和字母序列并利用list \texttt{list}list高效地完成单词的查询、删除和插入操作。理解压缩与解压缩的对称性是解决本题的关键即压缩时第一次出现的单词保留原词并加入列表头部重复出现的单词用列表位置编号代替解压缩时遇到数字就去列表中查找对应位置的单词并输出同时更新列表顺序。