程序员面试金典-面试题0106-字符串压缩

r囧r小猫 2022-12-31 12:29 190阅读 0赞

## 程序员面试金典-面试题0106-字符串压缩 ##

题目很容易理解，将字符串按照出现的次数进行压缩。但是实现过程中遇到两个bug：  
1.压缩后的字符串长度最长并不是strlen(str)+1,应该是2\*strlen(str),为这种情况"abc"->“a1b1c1”;  
2.字符出现的次数可能大于9，即可能不是个位数，不能简单地取“0123456789”

字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。
    
    示例1:
    
     输入："aabcccccaaa"
     输出："a2b1c5a3"
    示例2:
    
     输入："abbccd"
     输出："abbccd"
     解释："abbccd"压缩后为"a1b2c2d1"，比原字符串长度更长。
    提示：
    
    字符串长度在[0, 50000]范围内。
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/compress-string-lcci
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

具体解法如下：

char* compressString(char* S){
        
        int len=strlen(S);
        char * return_string = malloc(sizeof(char)*len+1); 
        //the max length of return_string may 2*len : e.g. "abc" -> "a1b1c1",
        //so len+1 may overflow 
        char * front_ptr=S;
        char * rear_ptr = S;
        char * ret = return_string;
        char * num = "0123456789";
        //the character count may > 9
        int count = 0;
        int num_len = 0;
        int temp_len=0;
        while((*rear_ptr)!='\0')
        {
        
            //printf("%c\n",(*rear_ptr));
            count = 0;
            num_len=0;
            while((*rear_ptr)!='\0' && (*rear_ptr)==(*front_ptr))
            {
        
                count++;
                rear_ptr++;
            }
            (*ret)=(*front_ptr);
            ret++;
            int t1 = count;
            while(t1!=0)
            {
        
                num_len++;
                t1=t1/10;
            }
            char str[num_len];
            int t2 = count;
            int num_len2 = num_len-1;
            while(num_len2>=0)
            {
        
                int t3 = t2%10;
                str[num_len2]=num[t3];
                t2=t2/10;
                num_len2--;
            }
            for(int i=0;i<num_len;i++)
            {
        
                (*ret)=str[i];
                ret++;
            }
            temp_len=temp_len+1+num_len;
            if(temp_len>=len)
                return S;
            front_ptr=rear_ptr;
        }
        (*ret)='\0';
        int ret_len=strlen(return_string);
        if(ret_len<len)
            return return_string;
        else
            return S;
    }