题目描述
给定一组字符，使用原地算法将其压缩。
压缩后的长度必须始终小于或等于原数组长度。
数组的每个元素应该是长度为1 的字符（不是 int 整数类型）。
在完成原地修改输入数组后，返回数组的新长度。
进阶：
你能否仅使用O(1) 空间解决问题？
示例 1：
输入：
["a","a","b","b","c","c","c"]
输出：
返回 6 ，输入数组的前 6 个字符应该是：["a","2","b","2","c","3"]
说明：
"aa" 被 "a2" 替代。"bb" 被 "b2" 替代。"ccc" 被 "c3" 替代。
示例 2：
输入：
["a"]
输出：
返回 1 ，输入数组的前 1 个字符应该是：["a"]
解释：
没有任何字符串被替代。
示例 3：
输入：
["a","b","b","b","b","b","b","b","b","b","b","b","b"]
输出：
返回 4 ，输入数组的前4个字符应该是：["a","b","1","2"]。
解释：
由于字符 "a" 不重复，所以不会被压缩。"bbbbbbbbbbbb" 被 “b12” 替代。
注意每个数字在数组中都有它自己的位置。
算法1
使用了双指针，测算出相同的字母和字母的个数
放入新的字符串中
C++ 代码
class Solution {
public:
int compress(vector<char>& chars) {
int l = 0; int r = 0;
string ans;
while (l < chars.size() && r < chars.size()) {
if (chars[l] == chars[r]) {
r++;
}
else {
int count = r - l ;
ans+= (chars[l]);
if (count != 1)
ans += to_string(count);
l = r;
}
}
int count = r - l;
ans += (chars[l]);
if(count != 1)
ans += to_string(count);
l = r;
for(int i =0;i <ans.size();i++){
chars[i]=ans[i];
}
return ans.size();
}
};
算法2
题目考虑到额外空间只有O(1)
只添加了一个当前长度的变量
然后原地修改
C++ 代码
class Solution {
public:
int compress(vector<char>& chars) {
int l = 0; int r = 0;
int currChar = chars[l];
int currlen = l;
while (l < chars.size() && r < chars.size()) {
if (chars[l] == chars[r]) r++;
if (r >= chars.size() || chars[l] != chars[r]) {
string count = to_string(r - l);
chars[currlen] = chars[l]; currlen++;
if(count != "1"){
for (int i = 0; i < count.size(); i++) {
chars[currlen] = count[i]; currlen++;
}
}
l = r;
}
}
return currlen;
}
};
