数据结构 Day11

╰半夏微凉° 2023-05-28 15:48 50阅读 0赞

### 1、字符串压缩 ###

> 字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。

> 示例1:  
> 输入：“aabcccccaaa”  
> 输出：“a2b1c5a3”

> 示例2:  
> 输入：“abbccd”  
> 输出：“abbccd”  
> 解释：“abbccd"压缩后为"a1b2c2d1”，比原字符串长度更长。 提示字符串长度在\[0, 50000\]范围内。

int Trans(char *S, int a)
    { 
        int len = log10(a)+1;
        int j=len;
        while(len)
        { 
            S[len-1] = a%10 + '0';
            a /= 10;
            len--;
        }
        return j;
    }
    
    char* compressString(char* S){ 
        int len = strlen(S);
        if(len<=2)   return S;
    
        char temp;
        int i, j=0, cnt=0;
        char *result = (char *)malloc( sizeof(char) * (len+2) );
        memset(result, 0, len+2);
        
        for(i=0; i<=len; i++)
        { 
            if(cnt==0)
            { 
                temp = S[i];
                result[j++] = S[i];
                cnt++;
            }
            else
            { 
                if(temp != S[i])
                { 
                    j += Trans(&result[j], cnt);
                    cnt=0;
                    temp = S[i];
                    result[j++] = S[i];
                    cnt++;
                }
                else
                { 
                    cnt++;
                }
            }
            if(j>len)   return S;
        }
        j += Trans(&result[j], cnt);
        
        return result;
    }

![在这里插入图片描述][20200316145019371.png]  
**总结**：这个题目里面主要的逻辑不是很复杂，先考虑最简单的情况，即个数小于10，遍历每一个数据，当是重复的数的时候，将Cnt不断累加，当出现了非重复的字符时，将Cnt又重新置零，因此通过判断Cnt是否为0,作为一个判断条件，判断是否为重复条件作为一个判断条件。之后再考虑个数大于10的时候，则需要至少2位，不可以再直接+‘0’，这种时候就需要一个函数去实现十进制转字符串的转化函数，在这里参考了一个log10()的函数，便于函数的实现。其实这个函数相对来说时间也比较长，可以改成不断地对10000相除，然后求余的方式实现。

[20200316145019371.png]: /images/20230528/1252d82622a74b7591380063bb434027.png