原题描述
利用字符重复出现的次数，编写一个方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3，若压缩后的字符串没有变短，则返回原字符串。
算法
Ideas：
- 计算压缩后的长度newLen
- 利用newLen开辟数组
- 遍历找到重复字符，并更新新数组
Algo：
-
主压缩函数：
1. 获取压缩后长度，并判断，若≥原串长度，则返回原串。 2. 利用新长度定义压缩串的存储数组array 3. 定义中间变量index(指示压缩串的遍历位置)，last和count用于遍历重复字符 4. 遍历原串 i 若str[i] == last时，则count++计数 否则： 利用index，last，count对array进行赋值，并返回新的index，并更新 重置last，count 5. 以最后一组重复字符的index，last，count更新array，返回array -
压缩串长度计算函数
1. 异常判断(对象为空或者字符串为空串)，则返回0 2. 定义用于遍历的last，count和用于计算长度的size=0 3. 遍历原串 i 若str[i] == last时，则count++计数 否则： size += (1 + count对应串的长度) 重置last，count 4. 以最后一组重复字符的count更新size 5. 返回size -
设置新串函数（array，index，last， count）
1. 把last赋到array的[index]处，index++ 2. 把count转化成串 3. 遍历该串 i 把串[i] 复制到 array[index]处，index++ 4. 返回index
C++代码
#include<iostream>
#include<sstream>
using namespace std;
int countCompression(string str) {
if (str.empty()) {
return 0;
}
int count = 1;
char last = str[0];
int size = 0;
for (int i = 1; i < str.length(); i++) {
if (str[i] == last) {
count++;
}
else {
stringstream ss;
ss << count;
string tp = ss.str();
size += (1 + tp.length());
last = str[i];
count = 1;
}
}
stringstream ss;
ss << count;
string tp = ss.str();
size += (1 + tp.length());
return size;
}
int setArray(char *array, int index, char last, int count) {
array[index++] = last;
stringstream ss;
ss << count;
string tp = ss.str();
for (int i = 0; i < tp.length(); i++) {
array[index++] = tp[i];
}
return index;
}
string stringCompression(string str) {
int size = countCompression(str);
if (size >= str.length()) {
return str;
}
char *array = new char[size];
char last = str[0];
int count = 1;
int index = 0;
for (int i = 1; i < str.length(); i++) {
if (str[i] == last) {
count++;
}
else {
index = setArray(array, index, last, count);
last = str[i];
count = 1;
}
}
setArray(array, index, last, count);
string ret = string(array);
delete[] array;
return ret;
}
int main() {
string input;
cin >> input;
string output = stringCompression(input);
cout << output << endl;
return 0;
}