【刷题】 leetcode 面试题 01.06 字符串压缩

发布时间:2024年01月24日

在这里插入图片描述

字符串压缩

在这里插入图片描述
来看题目:
根据题目所说,我们需要完成函数书写,保证返回一个相对较小的字符数组:如果压缩后比原字符串小,则返回压缩字符串,否则返回原字符串。

思路一(双指针顺畅版)

本思路一步一步操作,逐步完成任务

  1. 先确认字符串长度是否小于 2 ,小于直接返回(因为压缩字符串长度至少是2
  2. 然后定义双指针和计数位
  3. 开始遍历 : *fast 与 *slow 不相等 则 fast向后移动
  4. 然后记录重复次数
  5. 重复次数分位数进入数组
  6. slow 到 fast 位置 , 计数归零
  7. 重复 3 - 6 直到遍历结束
char* compressString(char* S){
    int len1 = strlen(S);
    if(len1<=2) return S;
	// 双指针
    char* slow = S;
    char* fast = S;
    //记录次数 每个字母至少出现 1 次
    int count = 1;
	//开辟一个足够大的数组空间
    char* ret = (char*)malloc(sizeof(char) * 100001);
    int i = 0;
    //开始遍历
    while(*fast !='\0'){
    	//快指针 后移
        fast = fast + 1;
        //向后移动 直到不同
        while(*fast == *slow){
            fast++;
            count++;
        }

        //计算位数 方便下面的赋值操作
        int n = 0;
        int num = count ;
        while(num){
            num /=10;
            n++;
        }
        int n2 = n;
        // ret 数组赋值
        ret[i++] = *slow;
        while(n--) {
            ret[i + n] = count % 10 + '0' ;
            count /= 10;
        }    
        // 下标后移   
        i += n2;
        // 慢指针移动到快指针位置
        slow = fast;
        //计数重置
        count = 1;
    }

	//结尾 ‘\0’不能忘记
    ret[i] = '\0';

    int len2 = strlen(ret);
    //返回较小的 字符串 
    if(len2 < len1) return ret;
    else return S;
}

思路二(sprintf函数巧解版)

上一步的写入计数的步骤十分繁琐,而使用sprintf函数可以巧妙化解这个问题
因为输入的数据都是 字符 + 数字
在这里插入图片描述
就是可以格式化写入数据

  1. 遍历字符串 记录相同次数
  2. 写入数据
  3. 重复 1 - 2 直到遍历结束
char* compressString(char* S){
	//字符串长度小于 2 直接返回
    int len1 = strlen(S);
    if(len1<=2) return S;
    
    char* ret = (char*)malloc(sizeof(char) * 100001);
    int  count = 1;

    memset( ret, 0x00, sizeof( ret ));
    for ( int i = 0; i < strlen( S ); i++ ) {
        if ( S[i] == S[i+1] ) {
            //前后相等,计数加1 
            count++;
        }
        else {
            //若前后不相等,写入数据, 计数器重置
            sprintf( ret + strlen(ret), "%c%d", S[i], count );
            count = 1;
        }
    }
	//返回较小字符串
    int len2 = strlen(ret);
    if(len2 < len1) return ret;
    else return S;
}

Thanks?(・ω・)ノ谢谢阅读

下一篇文章见!!!

文章来源:https://blog.csdn.net/JLX_1/article/details/135817078
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。