LeetCode 443. String Compression

题目

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.

Follow up:
Could you solve it using only O(1) extra space?

Example 1:
Input:["a","a","b","b","c","c","c"]
Output:Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]

Explanation:
"aa" is replaced by "a2". "bb" is replaced by "b2". "ccc" is replaced by "c3".

Example 2:
Input:["a"]
Output:Return 1, and the first 1 characters of the input array should be: ["a"]

Explanation:
Nothing is replaced.

Example 3:
Input:["a","b","b","b","b","b","b","b","b","b","b","b","b"]
Output:Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].

Explanation:
Since the character "a" does not repeat, it is not compressed. "bbbbbbbbbbbb" is replaced by "b12".
Notice each digit has it's own entry in the array.

Note:

1. All characters have an ASCII value in [35, 126].
2. 1 <= len(chars) <= 1000.

解析

注意此题不仅要统计结果长度，而且还要修改传入参数的chars数组内容，这样output数组结合return的值来输出chars内容。
另外，在修改chars数组的时候，有两种触发条件：最后一个字符和后面的不等于前面字符。可以经过推算，直接修改是可以的，
（1）如果字符只出现一次，即ab这种形式，则不需要修改，题目中规定1次的字符不需要添加count的数量；
（2）当大于1次后，需要将字符拆分，如12需要拆分成"1"和"2"，还需要添加当前的character，这种情况和为1+count的位数。
处理好以上两种情况，便可以仅用O(1)空间。

代码（C语言）

int compress(char* chars, int charsSize) {
    char* digits = (char*)calloc(200, sizeof(char));
    int totalCount = 0, currentCount = 0;
    
    for (int i = 0; i < charsSize; ++i) {
        ++currentCount;
        
        if (i == charsSize - 1 || chars[i + 1] != chars[i]) {
            chars[totalCount] = chars[i];
            
            if (currentCount > 1) {
                // digit
                int digit = -1;
                
                while (currentCount != 0) {
                    digits[++digit] = currentCount % 10 + '0';
                    currentCount /= 10;
                }
                
                for (int j = digit; j >= 0; --j)
                    chars[++totalCount] = digits[j];
            }
            
            // add the character count
            ++totalCount;
            currentCount = 0;
        }
    }
    
    free(digits);
    
    return totalCount;
}

笔者参考了题目的discuss中帖子而编写的代码，其中有两处处理的比较巧妙，一是i == charsSize - 1 || chars[i + 1] != chars[i]，此处的判断其实是两处判断；另外一处在判断中最后再进行++totalCount操作，这里主要是加上character的1，无论是否出现过1次，都需要加上这个长度。
此题可以训练逻辑思维和编码能力，忘读者身体力行之。