LeetCode 443. 压缩字符串

题目

给定一组字符，使用原地算法将其压缩。

压缩后的长度必须始终小于或等于原数组长度。

数组的每个元素应该是长度为1 的字符（不是 int 整数类型）。

在完成原地修改输入数组后，返回数组的新长度。

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

前言

此题要求使用原地算法求解,即将压缩结果存在原chars[]数组中.

使用双指针即可求解此题.这里我们称由相同字符组成的字符串为相同字符序列.

指针t指示已压缩的结果的末尾,指针i指示未压缩字符串的开头.

遇到相同的字符,指针i便向后滑动,直到遇到不同字符.指针i滑动的距离即为相同字符序列的长度.

具体过程及解析如下:

public int compress(char[] chars) {
        int t=0;//设置指针
        int i=0;
        while (i <chars.length && t<chars.length) {//遍历字符串
            chars[t++]=chars[i];//取相同字符序列的首字符存下
            int temp=i;//记录相同字符序列首元素位置
            while (i<chars.length &&chars[i]==chars[t-1])
                i++;//i指针滑动到相同字符序列末尾的下一个位置
            if(i-temp>1){//若相同字符序列长度大于1
                for(char c:String.valueOf(i-temp).toCharArray()){//向结果中加入相同字符序列的长度的字符形式
                    chars[t++]=c;
                }
            }
        }
        return t;//t即为已压缩的结果的长度
}