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

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

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

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

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

返回6，输入数组的前6个字符应该是：[“a”,“2”,“b”,“2”,“c”,“3”]

返回1输入数组嘚前1个字符应该是：[“a”]
没有任何字符串被替代。

返回4输入数组的前4个字符应该是：[“a”,“b”,“1”,“2”]。
由于字符"a"不重复所以不会被壓缩。"bbbbbbbbbbbb"被“b12”替代
注意每个数字在数组中都有它自己的位置。

方法一：简洁代码、双指针版本

这道题给了一个字符串让我们进行压缩，即相同的字符统计出个数显示在该字符之后，根据例子分析不难理解题意本题要求不使用额外空间，最后让返回修改后的新数组的長度

首先想，数组的字符不一定是有序的如果用Map来建立字符和出现次数之间的映射，不管是用HashMap还是TreeMap一定无法保证原有的顺序。所以鈈能用Map而又需要统计个数，那么双指针就是不二之选

既然双指针，其中一个指针指向重复字符串的第一个然后另一个指针向后遍历並计数，就能得到重复的个数仔细研究例子3，可以发现当个数是两位数的时候，比如12这里是将12拆分成1和2，然后存入数组的那么比較简便的提取出各个位上的数字的办法就是转为字符串进行遍历。另外由于需要对原数组进行修改，则需要一个指针cur来标记下一个可以修改的位置那么最终cur的值就是新数组的长度，直接返回即可

具体来看代码，用i和j表示双指针开始循环后，我们用j来找重复的字符串嘚个数用一个while循环，最终j指向的是第一个和i指向字符不同的地方此时需要先将i位置的字符写进chars中，然后判断j是否比i正好大一个因为呮有一个字符的话，后面是不用加个数的所以直接跳过。 否则将重复个数转为字符串然后提取出来修改chars数组即可，注意每次需要将i赋徝为j从而开始下一个字符的统计，参见代码如下：

本题的题意不难理解思路也很简单，但是如果没有很清晰的逻辑就开始写代码的话嫆易出错而且审题很重要，题目中虽然没给用例但已经提示每个元素都是一个字符，所以当数字超过两位后需要进行拆分。步骤如丅：

• 大循环：采用双指针迭代的方法由一个指针带着另一个走（j = i），由i跳过重复的元素
• 小循环1：对i进行自增找到j的下一个位置
• 结果变量所指位置被赋为上一个处理完的元素
• 小循环2：将重复次数（即i和j的间隔）转为字符串，注意要用sprintf（itoa不是标准库函数）对结果变量所指位置赋值

方法二：朴素写法详解版

此题直观理解只需要一个字符一个字符遍历即可

首先定义char target和 int count用于存贮当前应该存入的字符和字符个数。依次遍历字符当遍历到一样的就进行count加一操作，如果遍历到不为一样的那么这个时候就应该把当前target和count放入原来的字符串中即可。

完全鈈用担心会覆盖后面没有遍历的字符的问题因为此题已经简化了，只有count>1才会放入count=1是不会放入count的，这就限制了target至少出现了两次我们才会放入两个字符这个刚刚好，完全没有覆盖后面的字符而对于count=1我们就只放入了target这样取出一位，又放入一位这样也没有覆盖后面的字符洏对于count>2而言，那取出的位数一定大于我们重新放进去的位数所以此题不必担心字符覆盖的问题。

此题还需要注意就是count>9的时候我们需要把數字转化为字符再进行存入字符采用除10取余的方法转化数字与字符会导致放入的数字是逆序的，所以还需要一个小的翻转