题目给一个压缩格式的字符串格式是 XXXX[0xFF, L, O]XXXX代表a-z的普通字符。[0xFF, L, O] 是压缩标记: 0xFF是固定的tagO表示要从当前位置往回数O个字符(包含当前位置)L表示从那个位置开始往后取L个字符append到已经解压出来的结果末尾。例子:abcd[0xFF, 1, 2]xy → abcdcxy解释: 已解压abcdO2表示从d往回数2个字符(包含d)落在cL1取1个字符就是c。拼接结果: abcd c xy abcdcxyabcd[0xFF, 1, 2]xy[0xFF, 3, 3] → abcdcxycxy解释: 第一段同上得到abcdcxy第二段在此基础上O3从y往回数3个字符落在cL3取3个字符 c,x,yappend上去得到abcdcxycxy要求: O(n)时间复杂度n是压缩字符串的长度解法整体思路维护一个动态增长的输出buffer(因为压缩可能引用自己刚生成的内容实际长度可能远超输入长度)扫描输入字符串:普通字符 → 直接append到buffer遇到 [ → 调用一个helper函数解析出这个标记里的L和O同时让扫描指针跳过整个[0xFF, L, O]这一段用L和O从buffer(不是从原始输入!)里回头取字符append到buffer末尾最容易踩的坑是把回退、取字符这件事错误地放在原始输入字符串上做而不是放在已经解压出来的buffer上做——L和O描述的是已解压结果内部的相对位置跟原始压缩字符串的位置毫无关系。我最初的几次尝试一直在试图直接在原始输入字符串s上做指针回退、原地修改——这条路走得很别扭原始字符串里压缩标记[0xFF, L, O]占用的字节数和它展开后实际代表的字符数完全不是一回事在同一块内存里一边读取压缩格式、一边原地展开会不断和自己已经读过/还没读过的部分打架逻辑越写越绕。后来才想清楚这类解压/展开问题更通用的写法是开一块独立的输出buffer只管往后写不去碰原始输入——原始字符串只负责被读扫描解析所有的回退、取值、拼接都发生在这块新的输出buffer里。这是这类题目的一个常见模式不只是这一道题。完整代码#include stdbool.h #include stddef.h #include stdlib.h #include string.h bool parse_marker(const char **s, size_t *l, size_t *o){ // 期望格式: [0xFF, L, O] const char *ch *s; if (*ch ! [) return false; ch; if (ch[0] ! 0 || ch[1] ! x || ch[2] ! F || ch[3] ! F) return false; ch 4; if (*ch ! ,) return false; while (*ch ) ch; if (*ch 9 || *ch 0) return false; int digit 0; while (*ch 9 *ch 0) { digit digit * 10 (*ch - 0); ch; } *l digit; if (*ch ! ,) return false; while (*ch ) ch; if (*ch 9 || *ch 0) return false; digit 0; while (*ch 9 *ch 0) { digit digit * 10 (*ch - 0); ch; } *o digit; if (*ch ! ]) return false; *s ch; // 把解析完的最终位置写回调用者的指针 —— 这正是本文要讲的核心机制 return true; } char *decompress(const char *s){ if (s NULL) return NULL; int n strlen(s); size_t capacity 2 * n 16; char *buf malloc(capacity); if (!buf) return NULL; size_t i 0 size_t length 0; size_t offset 0; while (*s ! \0){ if (*s [){ if (!parse_marker(s, length, offset)){ free(buf); return NULL; } if (i offset) { free(buf); return NULL; // 非法输入: offset超出了已解压内容的范围 } if (i length 1 capacity) { capacity (i length 1) * 2; buf realloc(buf, capacity); } int start i - offset; while (length){ buf[i] buf[start]; // 注意: 每次都重新从buf读取 // 这样能正确处理引用自己刚生成的内容这种自重叠情况 length--; } } else { if ((size_t)i 2 capacity) { capacity * 2; buf realloc(buf, capacity); } buf[i] *s; } } buf[i] \0; return buf; }几个值得注意的设计点1. 用动态buffer不用固定大小数组压缩内容可以引用自己刚生成的部分比如a[0xFF, 3, 1]会展开成aaaa理论上解压后的长度可以远大于输入长度固定大小的buffer不安全必须支持realloc扩容。2. 数字解析要支持多位数[0xFF, L, O]里的L长度和O偏移量不能假设是单个数字字符——必须循环读取连续的数字字符按digit digit*10 (ch-0)这种标准方式累加否则遇到两位数的偏移量就会出错。3.buf[i] buf[start];这一行要逐个执行不能批量复制如果L和O的关系导致要复制的范围和目标写入位置有重叠自引用用memcpy一次性复制是不安全的memcpy不保证处理重叠区域。逐字节复制、每次都重新读取buf当前内容才能正确得到复制时引用了刚写入的字符这种语义。4.parse_marker(s, ...)—— 传入s的地址而不是s本身这是这道题里最容易写错、也是这篇笔记接下来要深入拆解的部分为什么必须传s传s为什么不行。指针到底在干什么从这道题里的一个bug说起写这道题的过程中我最初是这样写parse_marker的bool parse_marker(const char *s, size_t *l, size_t *o){ s; // 我以为这样能让调用者的指针往前移动 ... }结果调用方decompress里的s的指针函数返回后完全没变——decompress陷入死循环反复处理同一个压缩标记最终因为buffer写溢出而崩溃。问题的根源是没分清楚指针能做的两件完全不同的事。指针能做的两件事是不一样的void func(int *p) { *p 100; // Case A: 修改 p 指向的内容 p p 1; // Case B: 修改 p 自己(让它指向别处) }Case A 会按直觉生效——调用者能看到这个改动。Case B 不会传回去——调用者的指针完全不受影响。int x 5; int *ptr x; func(ptr); // *p 100 这一步x 真的会变成 100 // p p 1 这一步ptr 还是指向 x没有变为什么会这样C语言函数传参永远是传值——传指针也不例外传进去的是指针这个值的一份拷贝。*p 100 → p拷贝过来的值恰好和ptr一样都是x的地址 → 通过这个地址写100写的是x所在的那块内存 → 调用者和函数内部操作的是同一块内存所以能看到变化 p p 1 → 改的是p这个局部变量自己让它存的地址变成另一个值 → 这只发生在p自己的那份拷贝上 → 函数返回后这份拷贝直接消失ptr从头到尾没被碰过从内存布局看这件事的本质抽象地说传值还是有点空——具体在内存里发生了什么才是真正讲清楚这件事的关键。把内存想象成一排连续编号的格子每个变量都占着某个具体的地址int x 5; int *ptr x;地址0x1000: [x的内容 5] 地址0x2000: [ptr的内容 0x1000] ← ptr自己也是一个变量存在地址0x2000 它存的内容恰好是x所在的地址(0x1000)ptr不是某种抽象的指向x的魔法关联——它就是一个普通变量占着0x2000这块内存内容恰好是数字0x1000。调用func(ptr)时C把ptr的值0x1000这个数字复制一份放进函数自己新分配的内存里func()内部参数p存在地址0x3000(全新分配的内存跟ptr的0x2000完全不同): 地址0x3000: [p的内容 0x1000] ← 从ptr复制过来的值执行*p 100*p 的意思: 去p里存的那个数字(0x1000)当成地址写入100 → 真正写入的是地址0x1000也就是x所在的位置 → p和ptr是两个不同的变量(0x3000 vs 0x2000)但它们存的数值碰巧一样 所以*p和*ptr最终都落在了同一块内存(0x1000)上执行p p 1这是在改p自己这块内存(地址0x3000)里存的内容 → 把p的内容从0x1000改成0x1004 main()里的ptr存放在完全不同的地址0x2000从头到尾没被碰过: 地址0x2000: [ptr的内容 0x1000] ← 还是原来的值没变核心区别*p 100操作的地址是p里存的那个数字0x1000——这碰巧等于x的地址所以能改到x。p p 1操作的地址是p自己所在的那个地址0x3000——这是p自己的内存跟ptr0x2000毫无关系。s属于后一种情况——只是移动了s这个局部拷贝自己存的数字调用者那个s存在完全不同的内存地址完全不知道发生过什么。解决方案用指针的指针要让函数真正改变调用者的指针需要传入指向那个指针的指针bool parse_marker(const char **s, size_t *l, size_t *o){ const char *ch *s; // 先复制一份用ch去试探性地解析 ... *s ch; // 解析成功后把最终位置写回调用者的s —— 这是Case A会生效 return true; } parse_marker(s, length, offset); // 传s的地址不是s本身同样从内存布局的角度看一遍s意思是s这个变量自己所在的地址不是s存的那个值假设是0x2000。这个地址被复制一份传给函数内部的参数在parse_marker里也叫s但类型是const char **parse_marker()内部: 地址0x4000: [s的内容 0x2000] ← 这次存的是调用者那个s变量的地址不是字符串的地址了 *s ch 的意思: 去s里存的那个数字(0x2000)当成地址写入ch的值 → 真正写入的是地址0x2000也就是decompress里那个s变量自己所在的位置 → 这次真正改写到了调用者的s*s ch这一步本质上跟前面*p 100是同一回事——都是修改指针指向的内容只是这次指针指向的恰好是调用者那个s变量本身所以改动能真正传回去。一句话总结*p ... → 改的是 p 指向的东西 → 调用者能看到 p ... → 改的是 p 自己 → 调用者看不到想让函数挪动调用者手里的指针就要再包一层传指针的地址让函数操作的指向的东西正好是调用者那个指针本身。