lc443. 压缩字符串
Description
给你一个字符数组 chars ，请使用下述算法压缩：
从一个空字符串 s 开始。对于 chars 中的每组 连续重复字符 ：
- 如果这一组长度为
1，则将字符追加到s中。 - 否则，需要向
s追加字符，后跟这一组的长度。
压缩后得到的字符串 s 不应该直接返回 ，需要转储到字符数组 chars 中。需要注意的是，如果组长度为 10 或 10 以上，则在 chars 数组中会被拆分为多个字符。
请在 修改完输入数组后 ，返回该数组的新长度。
你必须设计并实现一个只使用常量额外空间的算法来解决此问题。
示例 1：
输入：chars = [“a”,”a”,”b”,”b”,”c”,”c”,”c”]
输出：返回 6 ，输入数组的前 6 个字符应该是：[“a”,”2”,”b”,”2”,”c”,”3”]
解释：“aa” 被 “a2” 替代。”bb” 被 “b2” 替代。”ccc” 被 “c3” 替代。
示例 2：
输入：chars = [“a”]
输出：返回 1 ，输入数组的前 1 个字符应该是：[“a”]
解释：唯一的组是“a”，它保持未压缩，因为它是一个字符。
示例 3：
输入：chars = [“a”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”]
输出：返回 4 ，输入数组的前 4 个字符应该是：[“a”,”b”,”1”,”2”]。
解释：由于字符 “a” 不重复，所以不会被压缩。”bbbbbbbbbbbb” 被 “b12” 替代。
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
int compress(vector<char>& chars) {
string s;
int i=0;
while(i<chars.size()){
char ch=chars[i];
if(chars[i]==' '){//如果当前字符已被标记为空格字符' ',则说明前面已经有这个元素了
i++;//记得把i++再continue
continue;
}
s+=ch;
int cnt=1;
for(int j=i+1;j<chars.size();j++){
if(chars[j]==ch){
cnt+=1;
chars[j]=' ';
}else{
break;//一旦遇到了与ch不一样的字符，就中断遍历
}
}
if(cnt>1){//如果cnt=1就不用把1加入到输出字符串中
string s0=to_string(cnt);//把重复元素个数转换为字符串加入输出字符串中
s+=s0;
}
i++;
}
for (int i = 0; i < s.length(); i++) {//新建一个s字符串代替chars向量被输出
chars[i]=s[i];
}
return s.length();
}
思路
外层遍历：逐个遍历chars向量的每个元素，下标为i；
内层遍历：对每个chars[i]，遍历从chars[i+1]（即外层遍历元素的下一个元素）到向量末尾元素，用cnt记录重复元素的个数。
如果从chars[i+1]开始，存在一系列与chars[i]相同的元素，则cnt++，且==置这些多余元素为空格字符’ ‘，以标记它们被“移除”出去了==
但是仅仅把多余元素改成’ ‘，最后输出的chars向量是包括这些空格字符的，所以只能[新建]一个s字符串作为最后的输出
把数字转换为字符串：`string s0=to_string(num);”