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

字符串压缩

来看题目：
根据题目所说，我们需要完成函数书写，保证返回一个相对较小的字符数组：如果压缩后比原字符串小，则返回压缩字符串，否则返回原字符串。

思路一（双指针顺畅版）

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

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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

思路二（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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

Thanks♪(･ω･)ﾉ谢谢阅读

下一篇文章见！！！