[C language brush leetcode] 443. Compressed string (m)

【

Give you an array of characters chars , Please use the following algorithm to compress ：

From an empty string s Start . about chars Each group in Consecutive repeating characters ：

If the length of this group is 1 , Append characters to s in .
otherwise , You need to s Append character , Followed by the length of this group .
Compressed string s Should not return directly to , Need to dump to character array chars in . It should be noted that , If the group length is 10 or 10 above , It's in chars The array will be split into multiple characters .

Please be there. After modifying the input array , Returns the new length of the array .

You must design and implement an algorithm that uses only constant extra space to solve this problem .

Example 1：

Input ：chars = ["a","a","b","b","c","c","c"]
Output ： return 6 , Before input array 6 The characters should be ：["a","2","b","2","c","3"]
explain ："aa" By "a2" replace ."bb" By "b2" replace ."ccc" By "c3" replace .
Example 2：

Input ：chars = ["a"]
Output ： return 1 , Before input array 1 The characters should be ：["a"]
explain ： The only group is “a”, It remains uncompressed , Because it's a character .
Example 3：

Input ：chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
Output ： return 4 , Before input array 4 The characters should be ：["a","b","1","2"].
explain ： Due to character "a" No repetition , So it's not compressed ."bbbbbbbbbbbb" By “b12” replace .
 

Tips ：

1 <= chars.length <= 2000
chars[i] It can be lowercase English letters 、 Capital letters 、 Numbers or symbols

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/string-compression
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

】

1. I understand the meaning of the wrong question again , The compressed string needs to be transferred to the character array chars in , I thought as long as I returned the length
2. 123->'1','2','3', Use a temporary array to save , And then reverse the order +'0' Deposit in newarr in , This operation is a little cumbersome
3. Don't miss the number of the last character
4. frequency 1 It's a trap

int idx;

int Getcntnum(int cnt, char *newarr)
{
    int ret = 0;
    int arr[2000] = {0};
    int ti = 0;

    if (cnt == 1) { //  If it is 1, immediate withdrawal 
        return 0;
    }

    while(cnt) {
        int tmp = cnt % 10;
        arr[ti++] = tmp; //  Disassemble the numbers and store them in the array in reverse order 
        cnt = cnt / 10;
        ret++;
    }

    for (int i = ti - 1; i >= 0; i--) {
        newarr[idx++] = arr[i] + '0'; //  Change to character save newarr
    }

    return ret;
}

int compress(char* chars, int charsSize){
    int i;
    int ret = 1;
    int cnt = 1;
    int num;
    char *newarr = (char *)malloc(sizeof(char) * charsSize);
    
    idx = 0;
    memset(newarr, 0, sizeof(char) * charsSize);

    newarr[idx++] = chars[0];
    for (i = 1; i < charsSize; i++) {
        if (chars[i] == chars[i - 1]) {
            cnt++; //  Number of characters 
        } else {
            num = Getcntnum(cnt, newarr); //  Get the number of times 
            newarr[idx++] = chars[i];
            cnt = 1; //  The number of initializations is 1;
        }
    }

    num = Getcntnum(cnt, newarr); //  Don't miss the number of the last character 
    memcpy(chars, newarr, sizeof(char) * charsSize);

    return idx;
}

/*
 Summary point ：
1.  Understand the wrong meaning , The compressed string needs to be transferred to the character array chars in , I thought as long as I returned the length 
2. 123->'1','2','3', Use a temporary array to save , And then reverse the order +'0' Deposit in newarr in 
3.  Don't miss the number of the last character 
4.  frequency 1 It's a trap 
*/