跳转至

LeetCode: 443. 压缩字符串

1、题目描述

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

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

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

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

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

示例 1:

输入:
["a","a","b","b","c","c","c"]

输出:
返回6,输入数组的前6个字符应该是:["a","2","b","2","c","3"]

说明:
"aa"被"a2"替代。"bb"被"b2"替代。"ccc"被"c3"替代。

示例 2:

输入:
["a"]

输出:
返回1,输入数组的前1个字符应该是:["a"]

说明:
没有任何字符串被替代。

示例 3:

输入:
["a","b","b","b","b","b","b","b","b","b","b","b","b"]

输出:
返回4,输入数组的前4个字符应该是:["a","b","1","2"]。

说明:
由于字符"a"不重复,所以不会被压缩。"bbbbbbbbbbbb"被“b12”替代。
注意每个数字在数组中都有它自己的位置。

注意:

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

2、解题思路

char *numToString(int num) {
    int digits = 1;

    int temp = num;
    while (temp / 10) {
        digits++;
        temp /= 10;
    }

    char *result = (char *) calloc(digits + 1, sizeof(char));

    sprintf(result, "%d", num);

    return result;

}


int compress(char *chars, int charsSize) {

    int pos = 0;
    char cur_ch = chars[0];

    int ch_count = 1;
    char *count;

    for (int i = 1; i < charsSize; i++) {
        if (chars[i] == cur_ch) {
            ch_count++;

        } else {
            chars[pos++] = cur_ch;
            cur_ch = chars[i];
            if (ch_count >= 2) {
                count = numToString(ch_count);
                for (int j = 0; j < strlen(count); j++) {
                    chars[pos++] = count[j];
                }
            }
            ch_count = 1;
        }

    }

    chars[pos++] = cur_ch;

    if (ch_count >= 2) {
        count = numToString(ch_count);
        for (int j = 0; j < strlen(count); j++) {
            chars[pos++] = count[j];
        }
    }

    return pos;


}