【leetcode刷题】T76-压缩字符串
【题目】
给定一组字符，使用原地算法将其压缩。
压缩后的长度必须始终小于或等于原数组长度。
数组的每个元素应该是长度为1 的字符（不是 int 整数类型）。
在完成原地修改输入数组后，返回数组的新长度。
进阶： 你能否仅使用O(1) 空间解决问题？
示例 1：
输入：
["a","a","b","b","c","c","c"]
输出：
返回，输入数组的前个字符应该是：["a","2","b","2","c","3"]
说明：
"aa"被"a2"替代。"bb"被"b2"替代。"ccc"被"c3"替代。
示例 2：
输入：
["a"]
输出：
返回，输入数组的前个字符应该是：["a"]
说明：
没有任何字符串被替代。
示例 3：
输入：
["a","b","b","b","b","b","b","b","b","b","b","b","b"]
输出：
返回，输入数组的前个字符应该是：["a","b","1","2"]。
说明：
由于字符"a"不重复，所以不会被压缩。"bbbbbbbbbbbb"被“b12”替代。
注意每个数字在数组中都有它自己的位置。
注意：
- 所有字符都有一个ASCII值在
[35, 126]区间内。 1 <= len(chars) <= 1000。
【思路】
统计连续相同字符的个数，并按要求存入数组。
注意：连续相同字符个数可能为两位数、三位数等，得一个字符一个字符地存入数组。
【代码】
python版本
class Solution(object):
def compress(self, chars):
"""
:type chars: List[str]
:rtype: int
"""
res =
if len(chars) == :
return
count =
current = chars[]
for i, c in enumerate(chars):
if c == current:
count +=
else:
chars[res] = current
# 多个重复字符，增加数字
if count > :
# 数字可能超过10，要将每一位加入数组
tmp = str(count)
for t in tmp:
res +=
chars[res] = t
res +=
count =
current = c
# 末尾字符
chars[res] = current;
if count > :
# 数字可能超过10，要将每一位加入数组
tmp = str(count)
for t in tmp:
res +=
chars[res] = t
res +=
return res
C++版本
class Solution {
public:
int compress(vector<char>& chars) {
int res=;
int count=;
string tmp="";
if(chars.size() == )
return ;
char current = chars[];
for(int i=; i < chars.size(); i++){
if(chars[i] == current){
count++;
}else{
chars[res] = current;
// 多个重复字符，增加数字
if(count > ){
// 数字可能超过10，要将每一位加入数组
tmp = to_string(count);
for(int j=; j<tmp.size(); j++)
chars[++res] = tmp[j];
}
res++;
count = ;
current = chars[i];
}
}
// 末尾字符
chars[res] = current;
if(count > ){
tmp = to_string(count);
for(int j=; j<tmp.size(); j++)
chars[++res] = tmp[j];
}
res++;
return res;
}
};
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-05-30，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读