leetcode-443-String Compression
leetcode-443-String Compression
题目描述：
Given an array of characters, compress it in-place.
The length after compression must always be smaller than or equal to the original array.
Every element of the array should be a character (not int) of length 1.
After you are done modifying the input array in-place, return the new length of the array.
Follow up: Could you solve it using only O(1) extra space?
Example 1:
Input:
["a","a","b","b","c","c","c"]
Output:
Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]
Explanation:
"aa" is replaced by "a2". "bb" is replaced by "b2". "ccc" is replaced by "c3".Example 2:
Input:
["a"]
Output:
Return 1, and the first 1 characters of the input array should be: ["a"]
Explanation:
Nothing is replaced.Example 3:
Input:
["a","b","b","b","b","b","b","b","b","b","b","b","b"]
Output:
Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].
Explanation:
Since the character "a" does not repeat, it is not compressed. "bbbbbbbbbbbb" is replaced by "b12".
Notice each digit has it's own entry in the array.Note:
- All characters have an ASCII value in
[35, 126]. 1 <= len(chars) <= 1000.
要完成的函数：
int compress(vector<char>& chars)
说明：
1、看完example之后才明白这道题要干嘛。要求在原本vector上面修改，然后输出最后vector的长度。空间复杂度是O(1)。
2、这道题目不难做，就是比较综合，考察多种操作。做法如下：
从vector首位开始处理，把碰到的第一个数记录下来，后续的数逐个跟它比较，如果相等就把后续的数删去，顺便记录删了几个数。
然后如果确实删去了数，那么把删去的数的个数+1，拆成一位一位的，插入在vector中，要注意插入的位置。
如果没有删去重复的后续的数，也就是记录下来的数只出现了一次，那么继续处理下一个数，仍然记录下来，覆盖掉原本的数。
直到vector所有字符都处理完毕。
有同学可能会疑惑为什么要删除和插入vector中的元素，因为题目要求要in-place处理，而且样例也有要求原vector要处理。
代码如下：
int compress(vector<char>& chars)
{
int i=0,j,count,ret=0;
char t1;
while(i<chars.size())
{
t1=chars[i];//t1记录碰到的数
count=1;//出现了一次
i++;//i指向下一个要处理的数
while(chars[i]==t1&&i<chars.size())//如果出现重复了
{
chars.erase(chars.begin()+i);//把这个重复的数删掉，删完之后i没有变，仍然指向第i个
count++;//出现了多一次
}
if(count==1)
ret++;
else
{
ret++;
j=i;//记录i的数值，i此时指向和上一个不重复的数
while(count!=0)
{
ret++;
chars.insert(chars.begin()+i,count%10+'0');
j++;//记录i之后应该要指向第几个数
count/=10;
}
i=j;//i仍然指向下一个要处理的数
}
}
return ret;
}上述代码实测8ms，beats 82.94% of cpp submissions。