443-压缩字符串（String Compression）

我会带着你远行 2022-04-25 10:10 235阅读 0赞

**题目描述**  
**中文**

给定一组字符，使用原地算法将其压缩。
    
    压缩后的长度必须始终小于或等于原数组长度。
    
    数组的每个元素应该是长度为1 的字符（不是 int 整数类型）。
    
    在完成原地修改输入数组后，返回数组的新长度。

**英文**

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.

**示例**

["a","a","b","b","c","c","c"]
    
    输出：
    返回6，输入数组的前6个字符应该是：["a","2","b","2","c","3"]
    
    说明：
    "aa"被"a2"替代。"bb"被"b2"替代。"ccc"被"c3"替代。

**提示**

所有字符都有一个ASCII值在[35, 126]区间内。
    1 <= len(chars) <= 1000。

**进阶**

你能否仅使用O(1) 空间解决问题？

**解题过程**

*  解题过程不难思考，可是怎么**原地**修改数组。。看了题解，发现大家采用的是双指针策略，下面的代码来自于题解。

class Solution {
        public int compress(char[] chars) {
            int s = 0;
            int e = 0;  //设置两个指针,s:未压缩字符串开头，e:已压缩的末尾
            while(s < chars.length && e < chars.length){
                chars[e++] = chars[s];      //这句话是要将非重复的字符记录下来
                int temp = s;               //记录下开始位置
                while(s < chars.length && chars[e - 1] == chars[s]){
                    //判断如果下一个字符和首字符相同
                    s++;
                }
                if(s - temp > 1){
                    //如果相同字符大于1
                    char[] flag = String.valueOf(s - temp).toCharArray();
                    for(char x: flag){
                        chars[e++] = x;
                    }
                }
            }
            return e;
        }
    }

**这道简单题让我有点受挫。。。。关于怎么原地修改数组，还需要在看一下。**

**补下python代码**

class Solution:
        def compress(self, chars: List[str]) -> int:
            s = 0
            e = 0
            while s < len(chars) and e < len(chars):
                chars[e] = chars[s]     # 记录非重复字符
                temp = s
                e += 1
                while s < len(chars) and chars[e-1] == chars[s]:    # 如果s 等于e - 1，说明重复
                    s += 1      # 继续往下搜索
                if s - temp > 1:       # 如果长度大于1，则需要将e+1后位置放入压缩字符的长度
                    flat = list(str(s - temp))
                    for x in flat:
                        chars[e] = x
                        e += 1
            return e