|
| 1 | +## 443_(压缩字符串)String Compression |
| 2 | +## 1 问题描述、输入输出与样例 |
| 3 | +### 1.1 问题描述 |
| 4 | +给定一组字符，使用原地算法将其压缩。<br> |
| 5 | +压缩后的长度必须始终小于或等于原数组长度。<br> |
| 6 | +数组的每个元素应该是长度为1 的字符（不是 int 整数类型）。<br> |
| 7 | +在完成原地修改输入数组后，返回数组的新长度。<br> |
| 8 | +__注意__：<br> |
| 9 | +所有字符都有一个ASCII值在[35, 126]区间内。 |
| 10 | +1 <= len(chars) <= 1000。 |
| 11 | +### 1.2 输入与输出 |
| 12 | +输入： |
| 13 | +* vector<char>& chars：输入的字符列表 |
| 14 | + |
| 15 | +输出： |
| 16 | +* int:原地压缩后的字符串的列表长度 |
| 17 | +### 1.3 样例 |
| 18 | +#### 1.3.1 样例1 |
| 19 | +输入：<br> |
| 20 | +["a","a","b","b","c","c","c"]<br> |
| 21 | +输出：<br> |
| 22 | +返回6，输入数组的前6个字符应该是：["a","2","b","2","c","3"]<br> |
| 23 | +说明：<br> |
| 24 | +"aa"被"a2"替代。"bb"被"b2"替代。"ccc"被"c3"替代。<br> |
| 25 | +#### 1.3.2 样例2 |
| 26 | +输入：<br> |
| 27 | +["a"]<br> |
| 28 | +输出：<br> |
| 29 | +返回1，输入数组的前1个字符应该是：["a"]<br> |
| 30 | +说明：<br> |
| 31 | +没有任何字符串被替代。<br> |
| 32 | +#### 1.3.3 样例2 |
| 33 | +输入：<br> |
| 34 | +["a","b","b","b","b","b","b","b","b","b","b","b","b"]<br> |
| 35 | +输出：<br> |
| 36 | +返回4，输入数组的前4个字符应该是：["a","b","1","2"]。<br> |
| 37 | +说明：<br> |
| 38 | +由于字符"a"不重复，所以不会被压缩。"bbbbbbbbbbbb"被“b12”替代。<br> |
| 39 | +注意每个数字在数组中都有它自己的位置。 |
| 40 | + |
| 41 | +## 2 思路描述与代码 |
| 42 | +### 2.1 思路描述（计数方法） |
| 43 | +思路很清晰，这里就不举例了，思路采用计数方法。<br> |
| 44 | +start 记录当前搜索字符的起始下标， search 记录当前搜索字符的遍历下标 ， cnt_same_char 记录当前搜索字符的相同长度<br> |
| 45 | +cmpr_len_char 记录当前压缩了的字符串的长度， len 记录输入字符串的长度<br> |
| 46 | +```cpp |
| 47 | +while( search < len ){ |
| 48 | + if(当前字符和前一个字符相同) cnt_same_char++； |
| 49 | + else{ |
| 50 | + 记录当前单词和数目 |
| 51 | + start = search; |
| 52 | + cnt_same_char = 1; |
| 53 | + } |
| 54 | + search++; |
| 55 | +} |
| 56 | +``` |
| 57 | +### 2.2 代码 |
| 58 | +```cpp |
| 59 | +int compress(vector<char>& chars) { |
| 60 | + //强行添加空格方便统一处理 |
| 61 | + chars.push_back(' '); |
| 62 | + int len = chars.size(); |
| 63 | + int start = 0, search = 1; |
| 64 | + int cnt_same_char = 1, cmpr_len_char = 0; |
| 65 | + while( search < len ){ |
| 66 | + if(chars[search] == chars[search - 1]) ++cnt_same_char; |
| 67 | + else{ |
| 68 | + chars[cmpr_len_char++] = chars[start]; |
| 69 | + //当前char计数值大于1时才压缩 |
| 70 | + if(cnt_same_char > 1){ |
| 71 | + //整形转字符串 |
| 72 | + //从高位往低位转 遇见最高位后flag = 1; |
| 73 | + int flag = 0; |
| 74 | + int msb = 1000, cnt2char = cnt_same_char; |
| 75 | + for( int i = 0; i < 4; i++ ){ |
| 76 | + int weight = cnt2char / msb; |
| 77 | + if(weight > 0 || flag) flag = 1, chars[cmpr_len_char++] = weight + '0'; |
| 78 | + cnt2char = cnt2char % msb; |
| 79 | + msb = msb / 10; |
| 80 | + } |
| 81 | + } |
| 82 | + start = search; |
| 83 | + cnt_same_char = 1; |
| 84 | + } |
| 85 | + search++; |
| 86 | + } |
| 87 | + //去除空格，恢复原始数据 |
| 88 | + chars.pop_back(); |
| 89 | + return cmpr_len_char; |
| 90 | +} |
| 91 | +``` |
| 92 | +## 3 思考与拓展 |
| 93 | +### 3.1 思考 |
| 94 | +#### 3.1.1 其他方法 |
| 95 | +无。 |
| 96 | +#### 3.1.2 复杂度分析 |
| 97 | +方法|空间复杂度|时间复杂度 |
| 98 | +--- | --- | --- |
| 99 | +计数方法|O(1)|O(n) |
| 100 | +#### 3.1.3 难点分析 |
| 101 | +1. 原地修改 |
| 102 | +2. 整形数据转字符串 |
| 103 | +### 3.2 拓展 |
| 104 | +如果给你的数链表数据呢？ |
0 commit comments