编码问题（Encoding）

83 阅读 0 评论 55 点赞

我是靠谱客的博主危机水壶，最近开发中收集的这篇文章主要介绍编码问题（Encoding），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

HDU 1020 Encoding

问题描述：

给定一个只包含'A'~'Z'的字符串，我们可以用如下的方法进行编码：

1、每一个包含了k个相同字符的子串，应该编码为"kX"，其中X为这个子串所包含的唯一的字符；

2、如果子串的长度为1，1应该被省略。

输入：

第一行包含一个正整数$N$，$0<N≤100$，该正整数$N$表示了有$N$组测试数据；接下来的$N$行包含了$N$个字符串，每个字符串只包含ASCII 字符A~Z，且长度不超过10000。

输出：

对于每一条测试数据，输出一行编码后的字符串。

样例输入：

ABC

ABBCCC

样例输出：

ABC

A2B3C

这道题本身而言难度不大。整体来看，只要从头至尾扫描目标字符串，找到重复的字符，计算长度即可。计算长度时，状态的转换相对要注意一下；另外，向字符串中插入数字，我使用了sprintf函数，这样能保证大整数依然能够快速准确的插入。C++实现如下

 1 #include<iostream>
 2 #include<string>
 3 int main()
 4 {
 5     using namespace std;
 6     string input, output;
 7     char buffer[255];
 8     int n;
 9     int count;        //the total count a character appears
10     char tmpc;        //the current character
11     cin >> n;
12     for (int i = 0; i < n; i++)
13     {
14         output.clear();
15         cin >> input;
16         count = 0;
17         for (unsigned int j = 0; j < input.length(); j++)
18         {
19             if (count == 0)
20             {
21                 count++;
22                 tmpc = input[j];
23             }
24             else
25             {
26                 if (input[j] == tmpc)
27                     count++;
28                 else
29                 {
30                     if (count == 1)
31                         sprintf(buffer, "%c", tmpc);
32                     else
33                         sprintf(buffer, "%d%c", count, tmpc);
34                     output.append(buffer);
35                     count = 1;
36                     tmpc = input[j];
37                 }
38             }
39         }
40         //last string to be processed
41         if (count == 1)
42             sprintf(buffer, "%c", tmpc);
43         else
44             sprintf(buffer, "%d%c", count, tmpc);
45         output.append(buffer);
46         cout << output << endl;
47     }
48     return 0;
49 }