LeetCode: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?
Example1 :
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".
Example2 :
Input:
["a"]
Output:
Return 1, and the first 1 characters of the input array should be: ["a"]
Explanation:
Nothing is replaced.
Example3:
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:
1.All characters have an ASCII value in [35, 126].
2.1 <= len(chars) <= 1000.
思路
整体思路:从头开始,比对前后字符是否相同,如果相同,就删除后边的字符,计数+1;如果不同,判断前一个字符的计数值,如果大于1就在后一个字符前插入计数值。
该题考察是对矢量类型的删除和插入操作,分别对应erase和insert函数。
需要注意的是,对于删除操作,迭代器指向的地址会被删除,而erase会返回被删除元素的后一个元素地址,因此利用erase返回值给迭代器更新地址:Iter=chars.erase(Iter);
。
这里还设置了一个考点是将十进制数按位以char类型存储,因此在插入计数值时,需要对10取余按位插入同时需要记录插入的位数,最后让迭代器移动对应位数,回到插入前对应的位置。
代码
class Solution {
public:
int compress(vector<char>& chars) {
int n=chars.size();
if(n==0||n==1)
return n;
vector <char>::iterator Iter;
int m=0;
char temp;
for(Iter=chars.begin();Iter!=chars.end();)
{
if(m==0)
{
temp=*Iter;
m++;
}
else
{
if(temp==*Iter)
{
m++;
Iter=chars.erase(Iter);
}
else
{
if(m==1)
{
temp=*Iter;
Iter++;
continue;
}
while(m%10||m/10)
{
chars.insert(Iter,m%10+'0');
m/=10;
}
Iter++;
}
continue;
}
Iter++;
}
if(m>1)
{
Iter=chars.end();
while(m%10||m/10)
{
chars.insert(Iter,m%10+'0');
m/=10;
Iter=chars.end()-1;
}
}
return chars.size();
}
};
推荐阅读
-
【leetcode 简单】 第一百题 压缩字符串
-
LeetCode题解 => 443.压缩字符串(七十六)
-
leetcode 443.压缩字符串
-
【LeetCode】周赛纪录(八)第199场周赛20200726 重新排列字符串 灯泡开关 IV 好叶子节点对的数量 压缩字符串 II
-
LeetCode 面试题 01.06. 字符串压缩
-
【leetcode 简单】 第一百题 压缩字符串
-
LeetCode - 1221 - 分割平衡字符串(split-a-string-in-balanced-strings)
-
【leetcode刷题】[简单]443. 压缩字符串(string compression)-java
-
Codeforces 825F String Compression 字符串,dp
-
LeetCode——443. 压缩字符串(String Compression)[中等]——分析及代码(Java)