面试题 01.06. 字符串压缩
难度简单142
字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。
示例1:
代码语言：javascript复制 输入："aabcccccaaa"
输出："a2b1c5a3"示例2:
代码语言：javascript复制 输入："abbccd"
输出："abbccd"
解释："abbccd"压缩后为"a1b2c2d1"，比原字符串长度更长。提示：
- 字符串长度在[0, 50000]范围内。
思路一：
- 用 tmp 来存储新的字符串，用 count 记录重复出现的字符。
- 一开始对字符串 s 进行遍历，然后将每次第一次出现的字符赋给 tmp，然后判断一下字符串 s[i] == s[i 1]，若相等则让 count ，不相等则将 count 运用一个函数 to_string 转化为字符串然后尾插到 tmp，
- 然后继续循环，直到遍历结束。
class Solution {
public:
string compressString(string S) {
string tmp;
int count = 1;
for(int i = 0; i < S.size(); i)
{
//只将第一次出现的那个附上去，其他的pop掉
if(count == 1)
tmp = S[i];
//若前后两个相同则直接count
if(S[i] == S[i 1])
{
count ;
}
//前后两个不同则将出现的次数尾插到tmp处
else
{
tmp = to_string(count);//使用to_string函数转化为sting类型
count = 1;
}
}
//将长度短的string返回
return tmp.size() < S.size() ? tmp : S;
}
};思路二：
- 运用双指针，让 i 指向第一次出现的字符，然后 在内层循环让 j 去遍历找到和 i 处不同的字符
- 若找到了不同的则与思路1一样，将 i 处的字符尾插到 tmp，然后将长度 j - i 转化为字符串尾插到 tmp 后面
- 然后将 i 移到 j 处，继续循环，直到遍历结束。
class Solution {
public:
string compressString(string S) {
int i = 0, j = 0;
int n = S.size();
string tmp;
// 「外层循环」i 指向每个首次出现的字符
while (i < n)
{
// 「内层循环」j 向前遍历，直到字符串末尾或找到与 s[i] 不同的字符时跳出
while (j < n && S[i] == S[j])
j ;
// 压缩字符串，添加至 tmp
tmp = S[i];
tmp = to_string(j - i);
// 令 i 指向下一个首次出现的字符
i = j;
}
// 对比「压缩字符串」和「原字符串」长度，返回较短的
return tmp.size() < n ? tmp : S;
}
};
