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

简介: 来看效果: 非常好!!!过啦!!!

字符串压缩

来看题目:

依据题目要求,我们必须编写一个函数,确保它能返回一个更为紧凑的字符数组:若压缩后的字符串长度小于原始字符串,则返回压缩后的字符串;反之,则返回原始字符串。本题的挑战核心在于如何有效地判定压缩是否导致了长度缩减,以及如何妥善地将处理后的数据填充进数组之中。接下来,我们将通过两种策略来攻克这一问题。

思路一(双指针顺畅版)

1.初始化检查:

  • 检查输入字符串的长度。
  • 如果字符串长度小于2,则压缩没有意义,直接返回原字符串。

2.设置指针与计数器:

  • 定义两个指针:slowfast,分别初始化在字符串的第一个字符位置。
  • 初始化一个计数器,用于记录重复字符的数量。

3.遍历字符串:

  • 使用fast指针遍历字符串,slow指针指向当前待比较的字符。
  • *fast*slow指向的字符相同时,fast指针向后移动,计数器累加。
  • *fast*slow指向的字符不同,或者fast达到字符串末尾时,进入下一步。

4.记录重复次数:

  • 计算从slowfast-1位置的字符重复次数(因为fast已经指向不同字符或字符串末尾)。
  • 将重复次数转换为字符串格式,以便与字符一同组成压缩后的字符串。

5.构建压缩字符串:

  • slow指向的字符和上一步得到的重复次数字符串拼接起来,形成压缩后的子串。
  • 将这个子串添加到结果字符串中。

6.重置计数器与指针位置:

  • 将计数器归零,准备统计下一组重复字符。
  • slow移动到fast的位置,准备开始下一轮比较。

7.循环直至结束:

  • 重复步骤3到6,直到fast指针遍历完整个字符串。、

8.返回结果:

  • 比较原字符串长度与压缩后的字符串长度。
  • 如果压缩后的字符串长度不小于原字符串长度,返回原字符串。
  • 否则,返回压缩后的字符串作为结果。

这个算法确保了字符串的压缩至少减少了长度如果压缩后没有变短,则保留原字符串。这样的实现既符合了压缩字符串的基本要求,也保证了算法的效率。

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函数可以巧妙化解这个问题

因为输入的数据都是 字符 + 数字

将格式化数据写入字符串

该函数将格式化文本组合成一个字符串,其内容与使用printf函数打印时完全一致,但并不直接输出,而是将内容存储在指向str的缓冲区中作为一个C语言风格的字符串。


请注意,缓冲区的大小应足够容纳生成的整个字符串(为了安全性考虑,请参阅snprintf函数获取更安全的版本)。


在内容后面,函数会自动附加一个终止空字符(null terminator)。


在format参数之后,函数期望至少有与format中所需数量相匹配的额外参数。就是可以格式化写入数据


就是可以格式化写入数据

1.遍历字符串并记录相同字符的次数:

  • 使用两个指针,一个指向当前正在比较的字符(slow),另一个指向待比较的字符(fast)。
  • 移动fast指针,直到遇到与slow指向的字符不同的字符,或者到达字符串的末尾。
  • 在移动fast指针的过程中,记录下相同字符出现的次数。

2.写入数据:

  • 使用sprintf函数或者其他字符串格式化方法,将当前字符及其出现的次数转换为一个字符串。
  • 将这个字符串添加到结果字符串中,这样就可以构建出压缩后的字符串。
  • 如果使用sprintf,可以先将次数转换为字符数组,然后将字符和次数连接起来。

3.重复步骤1和2直到遍历结束:

  • 重置计数器,将slow指针移动到fast的位置。
  • 继续执行步骤1和2,直到fast指针遍历完整个字符串。

4.检查压缩后的字符串长度:

  • 在完成压缩后,比较原字符串长度与压缩后的字符串长度。
  • 如果压缩后的字符串长度不小于原字符串长度,返回原字符串。
  • 否则,返回压缩后的字符串作为结果。

在实际编程中,需要考虑一些边界条件和特殊情况,比如字符串为空或者只包含一个字符时的情况。此外,还需要注意sprintf函数的使用,确保不会出现缓冲区溢出等安全问题。

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♪(・ω・)ノ谢谢阅读!!!

下一篇文章见!!!

相关文章
|
1天前
|
算法 索引 Python
二刷力扣--字符串
二刷力扣--字符串
|
3天前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
|
3天前
|
算法
【经典LeetCode算法题目专栏分类】【第8期】滑动窗口:最小覆盖子串、字符串排列、找所有字母异位词、 最长无重复子串
【经典LeetCode算法题目专栏分类】【第8期】滑动窗口:最小覆盖子串、字符串排列、找所有字母异位词、 最长无重复子串
|
6天前
|
SQL 算法 大数据
深入解析力扣181题:超过经理收入的员工(自连接方法详解及模拟面试问答)
深入解析力扣181题:超过经理收入的员工(自连接方法详解及模拟面试问答)
|
6天前
|
存储 算法 搜索推荐
深入解析力扣179题:最大数(自定义排序法详解及模拟面试问答)
深入解析力扣179题:最大数(自定义排序法详解及模拟面试问答)
|
6天前
|
SQL 大数据 数据挖掘
深入解析力扣178题:分数排名(DENSE_RANK详解及模拟面试问答)
深入解析力扣178题:分数排名(DENSE_RANK详解及模拟面试问答)
|
6天前
|
SQL 算法 大数据
深入解析力扣176题:第二高的薪水(子查询与LIMIT详解及模拟面试问答)
深入解析力扣176题:第二高的薪水(子查询与LIMIT详解及模拟面试问答)
|
6天前
|
存储 算法 数据挖掘
力扣174题动态规划:地下城游戏(含模拟面试)
力扣174题动态规划:地下城游戏(含模拟面试)
|
6天前
|
存储 算法 数据挖掘
力扣173题:二叉搜索树迭代器(含模拟面试)
力扣173题:二叉搜索树迭代器(含模拟面试)
|
6天前
|
SQL 算法 大数据
深入解析力扣177题:第N高的薪水(SQL子查询与LIMIT详解及模拟面试问答)
深入解析力扣177题:第N高的薪水(SQL子查询与LIMIT详解及模拟面试问答)